Persistent Data Structures: Structural Sharing Across Versions

Glass blowing has a point of no return. Once the piece enters the annealer and starts its 18-hour cooldown, the shape is locked. If you want something different, you don’t reheat and modify—you gather fresh glass and blow again. The original remains unchanged.

Persistent data structures work the same way. When you “modify” one, you don’t mutate it. You create a new version that shares most of its structure with the old one, reusing unchanged parts. Both versions exist simultaneously. This became central to functional programming in the 1980s when researchers realized you could have efficient immutability through structural sharing.

Here’s a persistent stack in JavaScript—each push creates a new version without destroying the old:

class PersistentStack {
  constructor(value, prev) { this.value = value; this.prev = prev; }
  push(v) { return new PersistentStack(v, this); }
  pop() { return this.prev; }
  peek() { return this.value; }
}

const v1 = new PersistentStack(1, null).push(2);
const v2 = v1.push(3);
console.log(v1.peek(), v2.peek()); // 2 3 — both versions exist

Erlang makes this the default. All data is immutable, so every “modification” produces a new structure:

-module(glass).
-export([shape/0]).

shape() ->
    Original = [gather, blow, shape],
    V1 = [punty_transfer | Original],
    V2 = [jack_rim | V1],
    {v1, hd(V1), v2, hd(V2)}.

Running glass:shape() returns {v1, punty_transfer, v2, jack_rim}. Both lists exist. The tail of V2 is literally the same memory as V1—structural sharing. You don’t copy the entire list, just add a new head node.

This is why functional programs can maintain version history cheaply. Like a shelf of cooled glass pieces, each version persists without interfering with the others.