Hello,
I would like to know how could functional languages implement "under the hood" creation of new state of for example Vector. When I have a Vector and I add another element to that particular Vector the old one is still there unchanged and new Vector containing the old one is created containing one more element.
How is this handled internally? Could someone try to explain it? Thank you.
If you prepend an element to a linked list, a new linked list is created with the new element as its head and a pointer to the old list as its tail.
If you add an item to an array, the whole array is usually copied (making it quite inefficient to build up an immutable array incrementally).
However if you only add to the end of each array once, like so:
arr1 = emptyArray()
arr2 = add(arr1, 1)
arr3 = add(arr2, 2)
arr4 = add(arr3, 3)
The whole thing could be optimized, so that arr1, arr2, arr3 and arr4, all have pointers to the same memory, but different lengths. Of course this optimization can only be performed the first time you add to any given array. If you have arr5 = add(arr4, 4) and arr5prime = add(arr4, 42) at least one of them needs to be a copy.
Note that this isn't a common optimization, so you shouldn't expect it to be there unless explicitly stated in the documentation.
Conceptually, a new Vector is created each time the Vector is extended or modified. However, since the original Vector is unmodified, clever techniques may be used to share structure. See ropes for example.
Also see Okasaki's Purely Functional Data Structures.