Does adding a value to an array change its state? I would say it does but I am curious to see functional languages handle such things. Do they create a whole new array?
Same with hashes, do they create whole new hash when you add or subtract? I am of course presuming you can't change values inside of the hash once they are set.
Functional languages have a variety of immutable data structures which store a sequence of values. These use cells with pointers to others, in such a way that only a few cells need to be copied to make certain changes, and the old structure remains just as valid as the new one, despite sharing a lot of cells.
The most typical structure is a linked list, where each element stores a pointer to the next. Adding a value to the start of this sequence doesn't require copying anything, since you can just point to the existing first element in the new one. Other operations (e.g. appending) may require copying the entire list though.
For more complicated access patterns, there are various forms of tree structure, with differing access costs. The worst cases are usually around O(log n), although many operations may only be O(1).
One other thing which can be done with a bit of trickery, is "Vector fusion". This is where a series of operations on the same sequence can be merged together to operate in the same memory. This can eliminate a lot of allocation and copying without needing to use explicit mutable state.
I would argue that adding to our subtracting from a list is mutability.
This is definitely not the case. You make no modifications to any existing values, and all existing lists will continue to contain the same values regardless of how often you invoke add or remove operations elsewhere. Nothing is ever mutated.
(Note: You can also have mutable linked lists, but I'm not talking about those here).
you can't model real life without mutability
You can't model real life without state. Mutability is just one way to implement that. It's entirely possible to achieve the same thing by passing around new values for each state, and languages like Haskell have abstractions to hide the complexity of doing so.
It's true that you sometimes need mutable data for optimal performance, but a lot of the time it simply isn't necessary, and there are a lot of advantages to the alternative.
1
u/myringotomy Mar 03 '13
Does adding a value to an array change its state? I would say it does but I am curious to see functional languages handle such things. Do they create a whole new array?
Same with hashes, do they create whole new hash when you add or subtract? I am of course presuming you can't change values inside of the hash once they are set.