CODEWITHSUNDEEP
functional-programming
Jarek
Jarek

Reputation: 7729

How does change of the state work under the hood in functional languages

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.

Upvotes: 1

Views: 132

Answers (2)

sepp2k
sepp2k

Reputation: 370357

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.

Upvotes: 0

Doug Currie
Doug Currie

Reputation: 41200

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.

Upvotes: 4

Related Questions