Comparison
Persistent data structurevsStructural sharing
Persistent data structure
you added an item and got a new list back, and the old one is still there and still valid.
A structure that preserves its previous versions when modified, so every update yields a new value and the old one remains usable. The naive implementation copies everything and is unusable at scale; real ones share the unchanged parts, which is what makes immutability affordable. It is what underpins undo stacks, time-travel debugging and the change detection in several frontend frameworks.
Full entry →Structural sharing
the new version copied five nodes rather than ten thousand elements, because everything unchanged is the same objects.
The technique that makes persistent data structures practical: an update copies only the path to the changed node and reuses every untouched subtree. It turns an apparent full copy into something logarithmic in the size of the structure. It only works because the shared parts are immutable, which is the clearest illustration of why immutability buys performance rather than only costing it.
Full entry →