The Rock Never Overwrites, It Only Deposits

The shale roadcut near Drumheller reads bottom to top like a transcript nobody edited. The trilobite horizon at my boots is older than the ammonite band at my waist, which is older than the crumbling stuff at eye level. Nothing up there reached down and rewrote what was below it. Each layer was deposited on top of the last, and every earlier version of the landscape is still sitting there, fully intact, waiting for someone with a dental pick.

That is a persistent data structure. Not “persistent” as in saved-to-disk — persistent as in every past version survives every update. Sarnak and Tarjan’s crowd formalized this in the mid-1980s, and the trick that makes it cheap is the same trick geology uses: you don’t copy the whole column to add a layer. You point the new layer at the shared column beneath it.

type 'a strata = Bedrock | Layer of 'a * 'a strata
let deposit stratum below = Layer (stratum, below)
let rec depth = function Bedrock -> 0 | Layer (_, b) -> 1 + depth b

let () =
  let ordovician = deposit "trilobite" Bedrock in
  let jurassic   = deposit "ammonite" ordovician in   (* reuses ordovician *)
  let cretaceous = deposit "hadrosaur" jurassic in
  Printf.printf "cretaceous depth: %d\n" (depth cretaceous);
  Printf.printf "ordovician still intact: %d\n" (depth ordovician)

cretaceous depth: 3
ordovician still intact: 1

Depositing the hadrosaur didn’t touch ordovician. It still knows it is one layer deep, because it is still one layer deep — jurassic and cretaceous are built by pointing at it, never by mutating it. Old cores of the record cost nothing to keep.

TypeScript makes the sharing explicit with readonly, which is the compiler’s version of the collecting rule I read on the drive home — you may examine, you may not alter:

type Strata<T> = null | { readonly stratum: T; readonly below: Strata<T> };
const deposit = <T,>(stratum: T, below: Strata<T>): Strata<T> => ({ stratum, below });
const depth = <T,>(s: Strata<T>): number => (s === null ? 0 : 1 + depth(s.below));

const ordovician = deposit("trilobite", null);
const jurassic   = deposit("ammonite", ordovician);   // shares ordovician
const cretaceous = deposit("hadrosaur", jurassic);
console.log("ordovician untouched:", depth(ordovician)); // 1

Where the metaphor cracks, and I like that it does: my deposit builds strictly upward, so the newest version can walk down into every ancestor but no ancestor can see the future — ordovician has no idea a hadrosaur ever showed up. Real persistence lets you branch off any old version and grow a new history from it, the way a preparator’s notebook can fork a specimen’s record at the moment the nodule split. The rock only ever gets one future. The data structure gets as many as you ask for.