Timeline for How are entities with an identity and a mutable persistent state modelled in a functional programming language?
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 25, 2012 at 9:11 | history | edited | AProgrammer | CC BY-SA 3.0 | Added the obvious. |
| Nov 25, 2012 at 2:44 | comment | added | singpolyma | A normal association list [(Int, v)] will let you replace the value at any index in constant time by simply consing the new value. Downsides: the old value is still taking RAM and search is linear. | |
| Sep 6, 2012 at 20:57 | comment | added | C. A. McCann | Incidentally, a trie is technically O(1) under the same simplifying assumptions often used when discussing such things, being a variable-size collection with insert/delete operations whose time complexity does not depend on the number of elements present. They're not really comparable to a mutable array, though. | |
| Aug 14, 2012 at 12:05 | comment | added | AProgrammer | @Giorgio, yes. I know how to do this in O(log n), but not O(1) -- and then the constant factor is also an hit. Note that I've used data structures designed for pure functional language as a way to implement undo in state-full languages. | |
| Aug 14, 2012 at 11:57 | comment | added | Giorgio | +1. Yes I was referring to modelling a stateful entity like an object (which has an identity and a history of subsequent states) in a stateless language. What would be the counterpart of your example (marked with (*)) in a language like Java? An array? An array of objects? | |
| Aug 13, 2012 at 20:22 | history | answered | AProgrammer | CC BY-SA 3.0 |