THE FOLD / RESPAWN / THE CONTINUE / THE PERSISTENT STRUCTURE
THE PERSISTENT STRUCTURE
versions that never overwrite the past
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Persistent data structures never overwrite the past: every update returns a new version while all older versions remain readable, unchanged. The trick is path copying. Store the data in a balanced tree; to change one element, copy only the O(log n) nodes on the path from the root to that leaf, and let the new root share every untouched subtree with the old one. So an update costs O(log n) time and space, yet the whole history stays alive — the basis of undo, versioned databases, and functional programming.
LIT verified live: after a long sequence of updates, reading any old version returns exactly the values it had at the time, and every update allocates only O(log n) new nodes (window.__persistent). FIG no framing; the versioned reads and the node-count are measured in-browser.
LIT verified live: after a long sequence of updates, reading any old version returns exactly the values it had at the time, and every update allocates only O(log n) new nodes (window.__persistent). FIG no framing; the versioned reads and the node-count are measured in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-continue — a save point you can always return to: the past versions persist, ready to continue from any of them. AVAN (AI) built the instrument: a path-copying persistent array, a version-by-version read check against snapshots, and a new-node counter.
Credit as content: Driscoll, Sarnak, Sleator & Tarjan (1986), “Making data structures persistent.” The weave: David names the continue; I confirm old versions read their original values and that each update copies only a logarithmic path.
Credit as content: Driscoll, Sarnak, Sleator & Tarjan (1986), “Making data structures persistent.” The weave: David names the continue; I confirm old versions read their original values and that each update copies only a logarithmic path.
3 ONE DIMENSION
An update copies only the root-to-leaf path (new nodes); the new version shares every other subtree with the old one.
4 TWO DIMENSIONS · INTERACTIVE
Update elements to make new versions; read back any old version and its values are exactly as they were — the past is intact.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the shared subtrees every version reuses.
AVAN’s addition (the inverse-companion): don’t mutate in place — copy the path and share the rest. The inverse of ‘overwrite and lose the old’ is ‘a new root over O(log n) fresh nodes, pointing back into the unchanged past.’ Magenta are the few new nodes on the path; green are the shared subtrees. Change nothing you can reuse.
LIT Genuine persistence via path copying (Driscoll, Sarnak, Sleator & Tarjan, 1986, 'Making data structures persistent'). Verified live: over 400 update histories, every old version reads its original values (window.__persistent.versionsIntact) and each update allocates only O(log n) new nodes (.logSharing).
FIG No framing: a path-copying persistent array, a version-by-version read check against snapshots, and a new-node counter all run in-browser. The AVAN inverse is honest — copying only the root-to-leaf path and sharing all untouched subtrees (rather than mutating in place) is exactly what keeps the past intact at O(log n) cost; magenta are the few new path nodes, green the shared subtrees. Change nothing you can reuse.
FIG No framing: a path-copying persistent array, a version-by-version read check against snapshots, and a new-node counter all run in-browser. The AVAN inverse is honest — copying only the root-to-leaf path and sharing all untouched subtrees (rather than mutating in place) is exactly what keeps the past intact at O(log n) cost; magenta are the few new path nodes, green the shared subtrees. Change nothing you can reuse.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE CONTINUE · David Lee Wise (ROOT0), with AVAN