Persistent data structures

A persistent data structure preserves every previous version of itself. When you "update" a Clojure vector or map, you get a new value back; the original is still around, unchanged. Naively that would be expensive, but Clojure uses structural sharing: the new value reuses almost all of the old one and only stores what's different.

The result is the best of both worlds: the safety of immutability with operations that are effectively O(log32 n) — close enough to constant for practical purposes.

Minimal example

assoc returns a new map without disturbing the old one. The old binding is still valid, and the two values can coexist:

conj on a vector gives the same guarantee — xs stays the same, ys is a fresh value:

Structural sharing, by intuition

Under the hood, Clojure vectors are trees of branching factor 32. To "update" an element, the runtime copies the path from the root to the leaf and shares every other branch with the original. For 1,000,000 elements, that's only ~4 levels of copying.

You can observe a side effect of sharing with identical? — when the changed portion is small, deep structural pieces are reused:

The "wrapper" is never the same, but the data on either side of the change typically is.

Practical example

Because every prior version still exists, you can keep a full undo history without any explicit copying:

reductions returns every intermediate value of the reduce. With mutable structures you'd have to deep-copy at each step; here it's free.

Check yourself

Exercise

Use assoc-in and update-in to navigate nested data immutably. Given the state below, produce a new state where :players[1].score is 100 and the original state is untouched.