Immutability in Elixir: Tuples and Lists

03/24/20191 Min Read — In Elixir

Let's talk about what I learned about immutability and Elixir today.

This is from the book Elixir in Action, Second Edition by Saša Jurić. So far, the book has been a great tour of Elixir and its features.

Elixir's data structures are immutable. You can't change data. You can only make a new version of the original thing and switch out what you wanted to change. But the original data still exists.

Elixir has a data structure called tuples. Tuples are "untyped structures, or records".

{"Elixir", 1}

Elixir also has lists and keyword lists.

If you use a list of 2-item tuples, it's a keyword list.

From the documentation:

iex> list = [{:a, 1}, {:b, 2}]
[a: 1, b: 2]
iex> list == [a: 1, b: 2]
true

"[...] keyword lists are used in Elixir mainly for passing optional values."

Lists on the other hand, are singly linked lists - not dynamic arrays like in JavaScript. That makes sense, as they are naturally recursive data structures where each node has a pointer to the next node. A head and a tail.

Immutability with tuples and lists

As Saša Jurić explains:

A modified tuple is always a complete, shallow copy of the old version.

Lists are quite interesting:

When you modify the nth element of a list, the new version will contain shallow copies of the first n-1 elements, followed by the modified element. After that, the tails are completely shared [...]

To append a new element at the tail, you have to iterate and (shallow) copy the entire list.

So it is cheaper to prepend a new item to the start of the list, instead of adding it to the end.
When writing Elixir, you should rather build up a list by add items as the head (first item) and then reversing the complete list at the end.

The same applies to keyword lists, as keyword lists are lists.

Further Reading