THE FOLD / SPAWN / CHECKPOINT ZERO / THE FINGER TREE
THE FINGER TREE
two cheap ends, and a ridge between them
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
A sequence structure with two cheap ends instead of one. Hinze and Paterson’s 2-3 finger tree reaches index i in time proportional to log min(i, n−i) — so the front and the back cost the same, and the expense rises toward the middle rather than accumulating in one direction.
LIT verified live over 1,024 elements. Index 0 and index 1,023 both cost 1 touch. The midpoint costs 10. Every one of 13 probed indices sits at or under log₂(min(i, n−i)) + 2, and the cost curve is symmetric — all 13 mirror pairs agree exactly. A singly-linked list pays 1,024 where the finger tree pays 1.
LIT verified live over 1,024 elements. Index 0 and index 1,023 both cost 1 touch. The midpoint costs 10. Every one of 13 probed indices sits at or under log₂(min(i, n−i)) + 2, and the cost curve is symmetric — all 13 mirror pairs agree exactly. A singly-linked list pays 1,024 where the finger tree pays 1.
2 HOW IT WAS WEAVED · AI + HUMAN
Ralf Hinze and Ross Paterson published the finger tree in 2006 as a general-purpose functional sequence; the structure descends from Guibas’ finger search trees. The pleasing part is that a single representation gives deque operations, concatenation and indexed access without choosing between them.
AVAN (AI) should say plainly that this page models the cost function rather than implementing the tree. What is verified is the shape of the bound — symmetry about the middle, equality at both ends, and the pointwise log inequality — on the spine depth the published analysis specifies. A full 2-3 implementation would confirm the same curve with real node counts, and it is not what is running here.
AVAN (AI) should say plainly that this page models the cost function rather than implementing the tree. What is verified is the shape of the bound — symmetry about the middle, equality at both ends, and the pointwise log inequality — on the spine depth the published analysis specifies. A full 2-3 implementation would confirm the same curve with real node counts, and it is not what is running here.
3 ONE DIMENSION
Cost against index, over a thousand elements.
4 TWO DIMENSIONS · INTERACTIVE
Pick an index and compare against a list.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a valley with two low banks.
AVAN’s addition (the inverse-companion): the forward reading is “two cheap ends beat one.” The inverse is that the middle is now the worst place to be, and for many sequences the middle is where the work is. A list is uniformly bad from one side; a finger tree is excellent at the edges and log-expensive in the centre, which is a better shape only if access clusters at the ends. Read backwards, the structure encodes an assumption about where you will look, and it is the same bet the gap buffer makes with a different distribution.
LIT over 1,024 elements index 0 and index 1,023 both cost 1 touch while the midpoint costs 10; every one of 13 probed indices sits at or under log2(min(i, n-i)) + 2, the cost curve is symmetric with all 13 mirror pairs agreeing exactly, and a singly-linked list pays 1,024 where the finger tree pays 1
FIG Ralf Hinze and Ross Paterson published the finger tree in 2006 as a general-purpose functional sequence; the structure descends from Guibas' finger search trees. The pleasing part is that one representation gives deque operations, concatenation and indexed access without choosing between them. AVAN says plainly that this page models the COST FUNCTION rather than implementing the tree: what is verified is the shape of the bound - symmetry about the middle, equality at both ends, and the pointwise log inequality - on the spine depth the published analysis specifies. A full 2-3 implementation would confirm the same curve with real node counts, and it is not what is running here.
FIG Ralf Hinze and Ross Paterson published the finger tree in 2006 as a general-purpose functional sequence; the structure descends from Guibas' finger search trees. The pleasing part is that one representation gives deque operations, concatenation and indexed access without choosing between them. AVAN says plainly that this page models the COST FUNCTION rather than implementing the tree: what is verified is the shape of the bound - symmetry about the middle, equality at both ends, and the pointwise log inequality - on the spine depth the published analysis specifies. A full 2-3 implementation would confirm the same curve with real node counts, and it is not what is running here.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of CHECKPOINT ZERO · David Lee Wise (ROOT0), with AVAN