Eric Campbell 7 min read Engineering

Finger Tree: Versatile Functional Data Structure

Finger trees are a purely functional data structure introduced by Ralf Hinze and Ross Paterson in 2006. They solve a problem that plagues most functional data structures: how do you get efficient...

Key Insights

  • Finger trees provide O(1) amortized access to both ends and O(log n) concatenation, making them the Swiss Army knife of functional data structures
  • The “measured” abstraction lets you build sequences, priority queues, and interval trees from the same underlying structure by swapping out a monoid
  • While theoretically elegant, finger trees carry real memory overhead—use them when you need their specific combination of operations, not as a default choice

What Are Finger Trees?

Finger trees are a purely functional data structure introduced by Ralf Hinze and Ross Paterson in 2006. They solve a problem that plagues most functional data structures: how do you get efficient access to both ends of a sequence while maintaining immutability?

Linked lists give you O(1) access to the head but O(n) to the tail. Balanced trees give you O(log n) everywhere but nothing better. Finger trees give you the best of both worlds: O(1) amortized access to either end, O(log n) access to the middle, and O(log n) concatenation.

The name comes from the idea of “fingers” pointing to the ends of the structure. Imagine holding a rope with both hands—you have immediate access to what’s under your fingers, but reaching the middle requires more work.

The Anatomy of a Finger Tree

A finger tree is a recursive structure with three possible shapes:

  1. Empty - contains nothing
  2. Single - contains exactly one element
  3. Deep - contains a prefix digit, a spine, and a suffix digit

The key insight is the “digit” concept. A digit holds 1 to 4 elements, providing a buffer that absorbs operations before they propagate deeper into the tree. The spine is itself a finger tree, but of nodes rather than elements—each node groups 2 or 3 elements together.

data FingerTree a
    = Empty
    | Single a
    | Deep (Digit a) (FingerTree (Node a)) (Digit a)

data Digit a
    = One a
    | Two a a
    | Three a a a
    | Four a a a a

data Node a
    = Node2 a a
    | Node3 a a a

This recursive structure creates a fascinating property: as you descend into the spine, each level contains elements that are exponentially farther from the ends. The first level of the spine contains nodes representing positions 5-8 from either end. The second level represents positions roughly 13-24. This logarithmic layering is what enables efficient middle access.

Think of it like a nested Russian doll, where each inner doll holds progressively more elements bundled together.

Amortized Complexity and Lazy Evaluation

The O(1) amortized bound for end operations relies critically on lazy evaluation. When you push an element onto a full digit (one with four elements), you need to convert three elements into a node and push that node onto the spine. This push might cascade further up.

In a strict language, this cascade could cost O(log n) in the worst case. But with laziness, the cascade is suspended—you build up a “debt” of deferred computations. The amortization argument shows that this debt is paid off gradually over subsequent operations.

-- The cost of this push is deferred
cons :: a -> FingerTree a -> FingerTree a
cons a Empty = Single a
cons a (Single b) = Deep (One a) Empty (One b)
cons a (Deep (Four b c d e) spine suffix) =
    -- This recursive call is lazy!
    Deep (Two a b) (cons (Node3 c d e) spine) suffix
cons a (Deep prefix spine suffix) =
    Deep (consDigit a prefix) spine suffix

The laziness means that even if you perform n consecutive pushes that all cascade, the actual work is spread across future operations that force the evaluation. This is the banker’s method of amortized analysis applied to persistent data structures.

Core Operations: Push, Pop, and Concatenation

Finger trees support the full deque interface with excellent performance:

-- Add to the left
cons :: a -> FingerTree a -> FingerTree a

-- Add to the right  
snoc :: FingerTree a -> a -> FingerTree a

-- View from the left (returns head and tail)
viewl :: FingerTree a -> ViewL a
data ViewL a = EmptyL | a :< FingerTree a

-- View from the right
viewr :: FingerTree a -> ViewR a
data ViewR a = EmptyR | FingerTree a :> a

The viewl operation is where the structure shines:

viewl :: FingerTree a -> ViewL a
viewl Empty = EmptyL
viewl (Single x) = x :< Empty
viewl (Deep (One x) spine suffix) =
    x :< deepl (viewl spine) suffix
viewl (Deep prefix spine suffix) =
    headDigit prefix :< Deep (tailDigit prefix) spine suffix

-- Helper to reconstruct when prefix becomes empty
deepl :: ViewL (Node a) -> Digit a -> FingerTree a
deepl EmptyL suffix = digitToTree suffix
deepl (node :< spine') suffix = 
    Deep (nodeToDigit node) spine' suffix

When the prefix runs out of elements, we pull a node from the spine and convert it back into a digit. This maintains the invariant that a Deep tree always has non-empty digits.

Concatenation is where finger trees truly distinguish themselves. Most functional sequences require O(n) for concatenation, but finger trees achieve O(log n):

(><) :: FingerTree a -> FingerTree a -> FingerTree a
Empty >< tree = tree
tree >< Empty = tree
Single x >< tree = cons x tree
tree >< Single x = snoc tree x
Deep pr1 sp1 sf1 >< Deep pr2 sp2 sf2 =
    Deep pr1 (addDigits sp1 sf1 pr2 sp2) sf2

The addDigits function handles the middle elements—combining the suffix of the left tree with the prefix of the right tree, bundling them into nodes, and recursively concatenating the spines.

The Power of Monoidal Annotations

Here’s where finger trees become genuinely powerful. By annotating each node with a monoidal “measure,” you can build radically different data structures from the same skeleton.

class Monoid v => Measured a v where
    measure :: a -> v

data FingerTree v a
    = Empty
    | Single a
    | Deep v (Digit a) (FingerTree v (Node v a)) (Digit a)

Each Deep node caches the combined measure of all its elements. This cache is maintained during operations and enables O(log n) splitting based on any monotonic predicate over the measure.

Example 1: Indexed Sequences

newtype Size = Size Int
    deriving (Semigroup, Monoid) via Sum Int

instance Measured (Element a) Size where
    measure _ = Size 1

-- Now we can split at any index in O(log n)
splitAt :: Int -> Seq a -> (Seq a, Seq a)
splitAt i tree = split (\(Size s) -> s > i) tree

Example 2: Priority Queues

newtype Priority a = Priority (Maybe a)

instance Ord a => Semigroup (Priority a) where
    Priority Nothing <> p = p
    p <> Priority Nothing = p
    Priority (Just x) <> Priority (Just y) = 
        Priority (Just (min x y))

instance Ord a => Monoid (Priority a) where
    mempty = Priority Nothing

-- Extract minimum in O(log n) by splitting where 
-- the cached minimum equals the element's priority

Example 3: Interval Trees

data Interval = Interval Int Int

data IntervalMeasure = IM 
    { low :: Int
    , high :: Int 
    }

instance Semigroup IntervalMeasure where
    IM l1 h1 <> IM l2 h2 = IM (min l1 l2) (max h1 h2)

The same split operation that gives you indexed access also gives you interval queries—you just change the monoid.

Practical Applications

Text Editor Buffers: Finger trees make excellent rope data structures. Each leaf holds a chunk of text, measured by character count. Cursor movement, insertion, and deletion all become O(log n) operations, and you get efficient undo through persistence.

Sequences in Haskell: The Data.Sequence module in Haskell’s containers library is a finger tree. It’s the go-to choice when you need both random access and efficient concatenation.

import qualified Data.Sequence as Seq

-- O(log(min(i, n-i))) indexing
element = seq `Seq.index` 1000

-- O(log(min(n, m))) concatenation  
combined = seq1 Seq.>< seq2

-- O(1) access to ends
first = Seq.viewl seq
last = Seq.viewr seq

Search Trees: By measuring elements with their keys and using an ordered monoid, finger trees can implement search trees with O(log n) lookup and the bonus of O(log n) merge operations.

Trade-offs and When to Use Finger Trees

Finger trees aren’t free. They carry significant memory overhead—each element is wrapped in node structures with cached measures, and the tree structure itself consumes space. For small collections, a simple list or vector will outperform them.

The constant factors are also substantial. An array-backed vector will beat a finger tree for random access in practice, even though both are O(log n) or better. The finger tree wins when you need the combination of operations: efficient ends, efficient concatenation, and persistence.

Use finger trees when:

  • You need a persistent sequence with efficient concatenation
  • You’re building a text editor or similar buffer structure
  • You want one data structure that adapts to different access patterns via measures
  • You’re in a lazy functional language where the amortization works correctly

Avoid finger trees when:

  • You’re in a strict language without careful thunk management
  • You only need stack or queue operations (use simpler structures)
  • Memory is constrained
  • You need cache-friendly sequential access (use arrays)

In Haskell, reach for Data.Sequence when you outgrow lists. In Scala, the standard library’s Vector uses a related structure (relaxed radix balanced trees) that offers similar trade-offs. In other languages, you’ll likely need a third-party library or your own implementation—and you should carefully consider whether the complexity is worth it for your use case.

Finger trees represent a beautiful intersection of theory and practice. They’re not always the right choice, but when you need their specific combination of properties, nothing else comes close.

Liked this? There's more.

Every week: one practical technique, explained simply, with code you can use immediately.