F2 · Functional Programming
Immutability & persistent data
Immutable data never changes in place. An “update” returns a new value and leaves the old one intact. The obvious worry is cost — but the new value shares almost everything with the old, so copying is cheap.
F2.01 needed immutability for purity: if a function could mutate your data, calling it would be an effect. F1.04 introduced binding without mutation. Here is the mechanism that makes it affordable. A persistent data structure preserves its previous versions; updating one builds only the parts that change and shares the rest. Prepending to a list is one new cell; updating a map rebuilds one path through a tree. The old version stays valid, which is why immutable values can be passed freely between functions and processes.
Sharing a list
An Elixir list is a chain of cons cells: each holds a value and a reference to the rest. Because the rest
is only a reference, prepending is cheap — [0 | list] makes one new cell that
points at the existing chain, sharing the entire tail. Appending is the opposite: to reach the end you
must rebuild every cell along the way.
Compare the two operations on the same list.
- immutable
- a value never changes in place; an update produces a new value.
- structural sharing
- the new value reuses the unchanged parts of the old one.
- persistent
- previous versions stay valid and accessible after an update.
- cons cell
- one link of a list: a value and a reference to the rest.
Prepend vs append · what gets built
Idea
A new version need not copy what it shares with the old one.
Elixir
[head | tail] shares the whole tail — prepending is constant time.
Prepend builds one cell and shares the rest; append rebuilds the spine. The data structure’s shape decides which operations are cheap.
Updating a map
A map is held as a tree. Updating one key does not copy the whole tree — it rebuilds only the nodes on the path from the root to that key and points the new path at the existing, unchanged subtrees. The number of rebuilt nodes is the depth of the tree, which grows as the logarithm of its size.
Pick a key to update and watch which nodes are rebuilt.
Map.put · rebuild the path, share the rest
Idea
Change one leaf; rebuild only the branch above it; keep every other branch.
Elixir
Map.put/3 returns a new map sharing all subtrees it did not touch.
A map update rebuilds a path, not a tree. The cost is the depth — logarithmic in the number of keys — and everything off the path is shared.
Why copying is cheap
Put the two costs side by side. Copying a structure of size n on every update is linear — n cells each time. Structural sharing rebuilds only what changed: about log₂ n cells for a tree, one for a list prepend. As the structure grows, the gap widens fast.
Move the slider and compare.
One update · cells built
F0.2 · the BEAM
Processes share nothing and pass immutable data — safe because no one can mutate it.
F2 · Functional
Cheap copies make immutability the default, not a luxury you pay for.
Linear versus logarithmic: at small sizes the difference is minor, but it grows without bound. Sharing is what lets a language make every value immutable.
What this lands
Immutability and structural sharing are two halves of one idea. Values never change in place, so an update returns a new version; that version shares its unchanged parts with the old one, so the update is cheap and the old version survives. A list prepend is one cell; a map update is one path through a tree. This is what makes purity (F2.01) practical and what lets the BEAM (F0.2) hand immutable data between processes without locks. With values settled, F2.03 turns to the verbs that act on them: higher-order functions.
Next: F2.03 — Higher-order functions — functions as arguments and return values. The full chapter path is on the F2 overview.