Immutability simplified

iex(5)> list1 = [1,2,3]
[1, 2, 3]
iex(6)> list2 = [4 | list1]
[4, 1, 2, 3]

I am trying to imagine how immutability works in Elixir (and in other functional languages).
When line 6 is executed there will be no new list data structure created but both list1 and list2 will refer to the same underline data structure. Is it correct assumtion???

Yes. In your example you’ll have a single linked list in memory, but the different variables will point to different head elements of it. Since it is a singly linked list there is no way from the list1 variable to ever go “backwards” and see element “4”.

In a general hand-wavey sense, this is how a lot of data structures work in immutable languages. You basically have one large/combined structure and different variables have different visibility to parts of it.


However, ignoring the under-the-hood implementation, the end user of the language should be under the impression that a brand new copy of the list is created. The particular implementation shown is just a trick for the sake of efficiency.


I’m not so sure that it’s about copying as much as it is that immutability gives us the effect that it’s like copying. As you say, it’s like that underneath for efficiency, but the interesting thing is that if we have immutable data then we don’t have to copy underneath: we know that pointing to different parts of the data (from different variables) won’t give us a different value at different times.