Structural Sharing: Cloning Without Copying Everything

When you fragment a coral and glue it to a new plug, you’re not rebuilding the organism cell by cell—you’re creating a clone that still shares the original’s calcium carbonate skeleton, symbiotic zooxanthellae lineage, and growth template. The fragment diverges only where new polyps bud.

Persistent data structures work the same way. When you “modify” an immutable list or tree, the implementation doesn’t copy the entire structure. It reuses every node that didn’t change and only allocates new memory for the path from root to the modified element.

Here’s a TypeScript example that fragments an array by replacing one element:

const parent = [1, 2, 3, 4, 5];
const fragment = [...parent.slice(0, 2), 99, ...parent.slice(3)];

console.log(parent);    // [1, 2, 3, 4, 5]
console.log(fragment);  // [1, 2, 99, 4, 5]
console.log(parent[0] === fragment[0]);  // true (same reference)

The unchanged elements aren’t copied—both arrays point to the same underlying values in memory. Only the modified element allocates new space.

OCaml’s list type makes structural sharing explicit because cons cells are immutable:

let parent = [1; 2; 3; 4; 5];;
let fragment = 99 :: (List.tl (List.tl parent));;

List.hd parent == List.hd (List.tl (List.tl fragment))  (* true *)

When you cons 99 onto the tail of parent, you’re building a new spine that shares the unchanged suffix. The memory addresses of 3, 4, and 5 are identical in both lists.

This is why cloning in functional languages is cheap: you’re not duplicating the organism, just creating a new entry point into shared structure. The fragment and the parent diverge only where growth occurs, just like coral polyps budding from a glued fragment.