Finger Tree

Finger tree is a purely functional, persistent data structure within computation and algorithms introduced by Ralf Hinze and Ross Paterson in 2006 as a unified representation for sequences, double-ended queues (deques), priority queues, search trees, and interval trees. By placing structural "fingers" (direct access buffers called affixes) at the left and right extremities of a polymorphic 2–3 tree spine, a 2–3 finger tree achieves amortized O(1) insertion and removal at both ends while supporting concatenation and positional splitting in O(log min(k, n − k)) time for a sequence of n elements split at index k.

Unlike imperative pointer-mutating structures or specialized balanced binary search trees such as the red-black tree and AVL tree, a finger tree is immutable and naturally persistent: structural updates share unmodified subtrees with previous versions without copying the entire collection. Furthermore, by parameterizing internal nodes with an arbitrary associative monoid measure—a technique mirroring the algebraic aggregation of a segment tree—a single polymorphic finger tree implementation specializes into random-access sequences, min-heaps, order-statistic trees, and one-dimensional interval trees without altering the underlying balancing invariants.

The concept of a finger in a search tree originated with Leonidas J. Guibas, Edward M. McCreight, Michael F. Plass, and Janet R. Roberts in 1977, who augmented imperative B-tree structures with parent and sibling pointers near frequently accessed leaves so that searches starting at a known finger position execute in O(log d) time, where d is the rank distance between the finger and the target key. In 1989, S. Rao Kosaraju and Arthur L. Delcher, alongside Robert E. Tarjan and Kurt Mehlhorn, refined finger search trees to support fast splitting and concatenation in imperative settings.

Translating finger search trees into a purely functional setting posed a fundamental challenge within computational complexity theory: upward parent pointers create cyclic references that require path reallocation whenever an immutable node is updated. Chris Okasaki resolved purely functional amortization in 1998 using lazy evaluation and implicit recursive slowdown, in which a polymorphic data type recursively instantiates its own spine at deeper nesting levels. Building on Okasaki's implicit catenable deques, Ralf Hinze and Ross Paterson (2006) replaced binary nodes with 2–3 nodes along the recursive spine and augmented every node with a cached monoidal annotation, creating the 2–3 finger tree that powers the sequence library in the Glasgow Haskell Compiler (Data.Sequence).

A 2–3 finger tree is defined via non-regular (nested) polymorphic recursion, in which the element type parameter a at level d of the spine is instantiated as a 2–3 node Node(a) at level d + 1. At any depth d ≥ 0 (where d = 0 holds user elements of type a and depth d holds balanced 2–3 trees of height d storing 2^d to 3^d elements), a finger tree FingerTree(a) takes one of three forms:

1. Empty: An empty tree containing 0 elements at depth d.
2. Single(x): A singleton wrapper holding one element x of type a at depth d.
3. Deep(v, prefix, spine, suffix): A composite level containing a cached monoidal measure v ∈ M, a left affix (prefix) of 1 to 4 elements of type a, a deeper recursive spine of type FingerTree(Node(a)) suspended via a lazy thunk, and a right affix (suffix) of 1 to 4 elements of type a, where each Node(a) is either Node2(v, x₁, x₂) or Node3(v, x₁, x₂, x₃).

Safe vs. Dangerous Affix States and Amortized O(1) Deque Operations

Restricting each prefix and suffix digit to 1–4 elements (while internal spine nodes have degree 2 or 3) mirrors redundant 2–3 number systems. Affixes with 2 or 3 elements are safe (green) states, whereas affixes with 1 element (underflow) or 4 elements (overflow) are dangerous (red) states:

• Push (Cons / Snoc): Inserting onto the left prefix (or right suffix) increments the affix size in O(1) time if it holds 1, 2, or 3 elements. When a 4-element affix overflows to 5 elements (x₁, x₂, x₃, x₄, x₅), the outer two (x₁, x₂) remain in the affix (a safe size of 2), while the inner three are packed into Node3(x₃, x₄, x₅) and recursively pushed onto the lazy child spine.
• Pop (Uncons / Unsnoc): Removing from an affix of size 2, 3, or 4 takes O(1) time. When a 1-element affix becomes empty, the tree inspects the child spine: if empty, the tree collapses to Single or Empty using the opposite affix; otherwise, it pops one Node2 or Node3 from the child spine and unpacks its 2 or 3 children into the depleted affix, restoring a safe size of 2 or 3.

Because both overflow (4 → 2) and underflow (1 → 2 or 3) leave the current level in a safe state requiring at least two subsequent deque operations before another cascade can propagate deeper, at most 1/2^d of operations reach depth d, yielding O(1) amortized time per deque operation.

Concatenation via Middle-Element Packing

To concatenate two finger trees T₁ = Deep(v₁, pr₁, sp₁, sf₁) and T₂ = Deep(v₂, pr₂, sp₂, sf₂), the outer affixes pr₁ and sf₂ are retained as the new left and right affixes of the combined tree. The inner affixes sf₁ (1–4 elements) and pr₂ (1–4 elements), together with a small bridge list of 0–4 elements accumulated during recursion, contain between 2 and 12 elements at depth d. These 2 to 12 elements are grouped greedily into between 1 and 4 balanced Node2 and Node3 packages of depth d + 1 and passed recursively to the spine concatenation function on sp₁ and sp₂. Because the recursion terminates as soon as the shallower spine reaches Empty or Single, concatenating trees of sizes n₁ and n₂ executes in O(log min(n₁, n₂)) time.

Monoidal Annotations and Monotonic Predicate Splitting

Rather than hard-coding subtree sizes or keys, Hinze and Paterson parameterized every node and affix by a monoid (M, ⊕, e) and a measurement function ‖·‖ : a → M satisfying the homomorphism law ‖*Node*(x₁, ..., x_m)‖ = ‖x₁‖ ⊕ ... ⊕ ‖x_m‖. Each Node2, Node3, and Deep constructor caches its precomputed measure v ∈ M in O(1) space so that querying the total measure of any subtree takes O(1) time.

Given any monotonic predicate p : M → {false, true} satisfying p(e) = false and the property that once p(x) becomes true for a prefix accumulation, p(x ⊕ y) remains true for all extensions y, the generic operation splitTree(p, i, T) locates the unique element x where the accumulated measure transitions from false to true. Starting with accumulator i at depth 0, splitTree first checks whether the transition occurs inside the left prefix pr (4 elements), then checks whether p(i ⊕ ‖*pr*‖ ⊕ ‖*spine*‖) is true (in which case it recurses down the spine to unpack the target Node2 or Node3), and otherwise locates the transition inside the right suffix sf. Because a tree of n elements has depth d for the k-th element from the nearer end proportional to log min(k, n − k), both positional indexing and splitting run in O(log min(k, n − k)) time.

By varying only the monoid (M, ⊕, e) while reusing the same 2–3 finger tree structure, four classic data structures emerge directly:

1. Random-Access Sequences (Data.Sequence): Choosing the additive size monoid (ℕ, +, 0) with ‖x‖ = 1 turns monotonic splitting with p(s) = (s > k) into O(log min(k, n − k)) random-access indexing, slicing, and splice updates.
2. Min/Max Priority Queues: Choosing the tropical min-monoid (ℝ ∪ {+∞}, min, +∞) with ‖x‖ = priority(x) caches the global minimum priority at the root. Extracting the minimum tests p(m) = (m ≤ ‖T‖) in O(log n) time while supporting O(1) insertion and O(log min(n₁, n₂)) heap melding.
3. Ordered Search Trees and Rope Strings: Choosing the right-last key monoid Key ∪ {−∞} with a ⊕ b = b (for b ≠ −∞) stores the maximum key of each subtree, turning splitTree with p(k) = (k ≥ target) into an ordered dictionary or rope structure supporting substring extraction and dynamic programming state maintenance.
4. Interval Trees: Combining the ordered key monoid (left endpoints low) with the max-monoid (maximum right endpoints high) into a product monoid yields a functional interval tree reporting an overlapping query interval in O(log n) time and all m overlapping intervals in O(m log(n/m)) time.

Why do finger tree affixes allow between 1 and 4 elements while spine nodes only allow 2 or 3 children?

In a standard 2–3 tree, inserting into a 3-node or deleting from a 2-node can trigger a cascade of node splits or merges up the spine in O(log n) time on alternating updates. Permitting outer affixes to hold 1 to 4 elements while keeping internal spine nodes at degree 2 or 3 ensures that an overflow at size 5 splits into a 2-element affix and a 3-node pushed to the spine, and an underflow at size 0 borrows a 2- or 3-node from the spine to become a 2- or 3-element affix. Both operations leave the affix in a safe state (size 2 or 3), guaranteeing at least two subsequent deque operations before the spine is accessed again.

Why is lazy evaluation required for persistent O(1) amortized bounds in a finger tree?

In a strict language without lazy suspensions, if a user creates a finger tree state T whose prefix is in a dangerous state (size 4) and then repeatedly pushes an element onto the same historical snapshot T across m independent branches, each branch would trigger the O(log n) spine cascade without having paid for the preceding safe insertions. Wrapping the recursive spine pointer in a lazy memoized thunk ensures that the O(log n) cascade work is evaluated at most once and shared across all persistent consumers of T.

1. Guibas, L. J., McCreight, E. M., Plass, M. F., & Roberts, J. R. (1977). "A new representation for linear lists." Proceedings of the 9th Annual ACM Symposium on Theory of Computing (STOC), 49–60. https://doi.org/10.1145/800105.803395
2. Kaplan, H., & Tarjan, R. E. (1999). "Purely functional, real-time deques with catenation." Journal of the ACM, 46(5), 577–603. https://doi.org/10.1145/324133.324139
3. Okasaki, C. (1998). Purely Functional Data Structures. Cambridge University Press. https://doi.org/10.1017/CBO9780511530104
4. Hinze, R., & Paterson, R. (2006). "Finger trees: a simple general-purpose data structure." Journal of Functional Programming, 16(2), 197–217. https://doi.org/10.1017/S0956796805005769
5. Claessen, K. (2004). "Finger trees explained anew, and slightly simplified (functional pearl)." Proceedings of the 2004 ACM SIGPLAN Workshop on Haskell, 31–38. https://doi.org/10.1145/1017472.1017483