Cloud Parts

Purely functional data structures

Collections that are never changed in place: every update returns a new version that shares most of its memory with the old one, and every old version stays valid.

6 technologies on this page ↓

How it works

An ordinary, ephemeral data structure is destroyed by an update: after you insert, the old version is gone. A persistent one keeps every version usable; it is partially persistent if only the newest version can be updated, fully persistent if any version can. In a functional language every structure is persistent automatically, because nothing is ever overwritten. The trick that makes this cheap is structural sharing. To insert into a balanced tree, you copy only the nodes on the path from the root to the change and point the copies at the untouched subtrees, so an update costs O(log n) new nodes instead of a copy of the whole collection. Wide trees push this further: Clojure and Scala use 32-way nodes, so updating one element of a large vector copies between one and five nodes. Persistence breaks one classic tool, amortization. A two-list queue is cheap on average because one expensive reverse pays for many cheap operations, but if a program keeps an old version and pops from it again and again, it pays for that same reverse every time. Chris Okasaki’s fix (1996) is lazy evaluation with memoization: the expensive work is set up as a suspension, the first version to need it runs it, and every other version reuses the cached result. Scheduling those suspensions turns many amortized bounds into worst-case ones. The costs are real: each update allocates new nodes, every lookup follows pointers through several levels instead of indexing one array, and a garbage collector or reference counts must free the versions nobody holds any more.

Think of it as

Correcting a printed report by reprinting only the pages that changed and stapling them to the untouched old pages. Both the old and the new report are complete, and together they use little more paper than one.

Reach for it when

  • Data read by many threads while one updates it: each reader holds a snapshot that can never change underneath it, with no locks
  • Undo, redo and history: keeping an old version costs only the nodes that changed since
  • Cheap change detection: if two references are identical nothing inside changed, which is how React’s memo and Immutable.js skip work
  • Backtracking, speculative edits and versioned trees, where you branch from an old state and keep both

Think twice when

  • Small collections owned by one piece of code: a plain array wins below a few hundred elements
  • Tight loops of random reads: an RRB vector is 2 to 3.5 times slower at random access than a mutable array
  • Amortized structures used persistently without memoization (strict code, no lazy values): the bounds no longer hold

A real example

An editor keeps a 100,000-line file as a persistent vector with 32-way nodes. Because 32³ is 32,768 and 32⁴ is about a million, the tree is four levels deep. Typing in one line replaces that line and copies the four nodes above it: about 128 pointers instead of 100,000. Undo is free: the editor keeps the root of every earlier version, and 1,000 undo steps cost about 4,000 small nodes rather than 1,000 copies of the file. The UI compares the old and new line references and redraws only the line whose reference changed.

Kinds of purely functional data structures

Specific products, and what each does differently.

Queues and deques →

First-in-first-out queues and double-ended queues built from immutable lists, from the two-list trick to deques that concatenate in constant time.

Priority queues →

Heaps built from trees instead of arrays, where merging two heaps is the core operation and every version stays valid.

Balanced search trees →

Sorted maps and sets as balanced binary trees, where an update copies the path from the root to the change and shares everything else.

Finger trees →

A general-purpose persistent sequence with cheap access at both ends and logarithmic concatenation and splitting, which also works as a priority queue or search tree.

Haskell containersOpen sourceHaskell’s standard package of persistent containers: `Data.Sequence` (finger trees), `Data.Map` and `Data.Set` (weight-balanced trees), `Data.IntMap` (Patricia trees), plus trees and graphs.

RRB vectors →

Immutable vectors built as wide trees whose nodes may be slightly underfull, so they concatenate, slice and insert in the middle in O(log n) while indexing stays nearly as fast as a plain radix tree.

im (Rust)ArchivedOpen sourcePersistent collections for Rust: an RRB-tree `Vector`, a hash array mapped trie `HashMap` and B-tree `OrdMap`, with O(1) cloning and copy-on-write updates. Unmaintained since 2022.imblOpen sourceThe maintained fork of Rust’s `im` crate: persistent collections with an RRB-tree `Vector`, a hash array mapped trie `HashMap` and a B+ tree `OrdMap`, with O(1) cloning and copy-on-write updates.immerOpen sourceA header-only C++ library of persistent, immutable containers, including an RRB-tree `flex_vector` with O(log n) concatenation and slicing and policy-based memory management.

Zippers →

A tree or list held by a cursor: the focused subtree plus the path back to the root, turned inside out so edits at the cursor are cheap and purely functional.

Why amortization breaks when old versions live on#

The textbook functional queue: a front list and a reversed rear list. Used once, each reverse is paid for by the pushes before it. Pop the same old version three times and the program pays for the same reverse three times.

ts
type List<T> = { head: T; tail: List<T> } | null;
type Queue<T> = { front: List<T>; rear: List<T> }; // rear is kept reversed

let steps = 0; // cells copied by reverse

function reverse<T>(xs: List<T>): List<T> {
  let out: List<T> = null;
  for (; xs !== null; xs = xs.tail) { out = { head: xs.head, tail: out }; steps++; }
  return out;
}

// invariant: front is empty only when the whole queue is empty
const check = <T>(front: List<T>, rear: List<T>): Queue<T> =>
  front === null ? { front: reverse(rear), rear: null } : { front, rear };

const push = <T>(q: Queue<T>, x: T): Queue<T> => check(q.front, { head: x, tail: q.rear });

function pop<T>(q: Queue<T>): [T, Queue<T>] {
  if (q.front === null) throw new Error("empty queue");
  return [q.front.head, check(q.front.tail, q.rear)];
}

let q: Queue<number> = { front: null, rear: null };
for (let i = 1; i <= 1000; i++) q = push(q, i);
// now front = [1] and rear = [1000, 999, ..., 2]

steps = 0;
let [, rest] = pop(q); // pays for reversing 999 cells
[, rest] = pop(rest);
[, rest] = pop(rest);
console.log(steps); // 999: used once, the reverse is paid for by the 999 pushes

steps = 0;
pop(q); pop(q); pop(q); // the same old version, three times
console.log(steps); // 2997: every logical future pays for the same reverse

Okasaki’s fix: let laziness pay once#

The banker’s queue from Okasaki’s thesis, in Haskell. It rotates as soon as the rear grows longer than the front, so the lazy f ++ reverse r is set up long before anyone needs it. Haskell runs a suspended computation at most once and caches the result, so every version that shares the rotated front shares the work too.

haskell
-- front length, front, rear length, rear (kept reversed)
data Queue a = Queue !Int [a] !Int [a]

empty :: Queue a
empty = Queue 0 [] 0 []

snoc :: Queue a -> a -> Queue a
snoc (Queue lf f lr r) x = check (Queue lf f (lr + 1) (x : r))

uncons :: Queue a -> Maybe (a, Queue a)
uncons (Queue _ [] _ _) = Nothing
uncons (Queue lf (x : f) lr r) = Just (x, check (Queue (lf - 1) f lr r))

-- keep |rear| <= |front|; the rotation is a lazy, memoized suspension
check :: Queue a -> Queue a
check q@(Queue lf f lr r)
  | lr <= lf = q
  | otherwise = Queue (lf + lr) (f ++ reverse r) 0 []

toList :: Queue a -> [a]
toList q = maybe [] (\(x, q') -> x : toList q') (uncons q)

main :: IO ()
main = do
  let q = foldl snoc empty [1 .. 1000 :: Int]
      first = fmap fst . uncons
  -- pop the same old version twice: the second pop reuses the memoized rotation
  print (first q, first q) -- (Just 1,Just 1)
  print (take 5 (toList (snoc q 1001))) -- [1,2,3,4,5]
  print (length (toList q)) -- 1000: q itself is unchanged

Which structure for which job#

Bounds as the papers and library docs state them. They hold even when old versions are shared, which is the point of these designs.

StructureGood atBoundsWhere you meet it
Banker’s and real-time queuesFIFO queuessnoc, head, tail O(1) amortized (banker’s) or worst case (real-time)Okasaki’s thesis and book
Finger treeSequences: both ends, concatenation, splittingEnds O(1) amortized; concatenate and split O(log n) of the smaller pieceHaskell Data.Sequence
RRB vectorIndexed sequences that also concatenate and sliceIndex and update effectively constant (32-way); concatenate, split and insert-at O(log n)im (Rust), immer (C++)
Hash array mapped trieUnordered maps and setsLookup and update in about log₃₂ n hopsClojure maps, Scala HashMap, Immutable.js Map
Balanced search treeSorted maps and sets, range queriesO(log n) lookup, insert and delete; each update copies one pathHaskell Data.Map, Scala TreeMap
Brodal–Okasaki heapPriority queues that mergefindMin, insert, meld O(1), deleteMin O(log n), all worst caseOkasaki’s thesis (section 7.2.2) and book
ZipperEditing near a cursor in a tree or listMoving and editing at the focus O(1), except moving upStructure editors, clojure.zip

Since Okasaki#

Okasaki’s book (1998) collected the field. These are the main results since, most of them from the answers to the cstheory.stackexchange question “What’s new in purely functional data structures since Okasaki?”, each checked against the paper itself.

Ideal Hash Trees (Phil Bagwell)

2001

The hash array mapped trie: hash the key, then use 5 bits of the hash per level to choose among 32 children, with a bitmap so empty slots cost one bit each. Bagwell built it as a mutable hash table; Rich Hickey made a persistent version the core of Clojure’s maps in 2007.

Priority search queues (Ralf Hinze)

2001

A blend of a finite map and a priority queue: logarithmic access by key and constant access to the binding with the smallest priority, enough for a purely functional Dijkstra’s shortest paths.

Catenable deques (Radu Mihaescu and Robert Tarjan)

2003

A simpler take on Kaplan and Tarjan’s 1999 deques, which do push, pop, inject, eject and catenation in worst-case O(1). Their constant-time version is written for pure Lisp, with no lazy evaluation.

Maxiphobic heaps (Chris Okasaki)

2005

Proposed as an easier-to-teach alternative to leftist heaps: merge compares subtree sizes and combines the two smaller of the three leftover subtrees, so each step keeps at most two thirds of the elements and merge stays O(log n).

Finger trees (Ralf Hinze and Ross Paterson)

2006

2-3 finger trees give amortized O(1) access to both ends and O(log n) concatenation and splitting. Caching a monoid in each node turns the same tree into a sequence, priority queue or search tree.

Catenable sorted lists (Brodal, Makris and Tsichlas)

2006

A purely functional search tree with O(log n) search and update that joins two trees in worst-case O(1) time, answering an open question from Kaplan and Tarjan.

Persistent union-find (Conchon and Filliâtre)

2007

A union-find that is persistent from the outside and as fast as the imperative one, by hiding mutation inside persistent arrays. A Coq proof checks that the side effects can’t be observed.

Confluently persistent tries (Demaine, Langerman and Price)

2008

Motivated by version control: directory trees where subtrees can be copied between any two versions. Their structures beat plain path copying for many deep but nearby edits, and some are purely functional.

Red-black delete (Matt Might)

2010

Okasaki’s red-black trees left deletion as an exercise. Might’s version adds two temporary colours, double black and negative black, and splits delete into remove, bubble and balance.

RRB-Trees (Phil Bagwell and Tiark Rompf)

2011

Relaxed radix-balanced trees let the 32-way vectors of Clojure and Scala concatenate, insert at any index and split in O(log n), while keeping their fast indexing and updates.

RRB Vector (Stucki, Rompf, Ureche and Bagwell)

2015

A practical RRB vector for Scala that caches the most recently used branch: memory on par with arrays, and a parallel speedup of at least 7 times on 4 CPUs with 8 cores each.

Persistence for the Masses (Juan Pedro Bolívar Puente)

2017

RRB vectors in C++ with unboxed elements, pluggable memory management and in-place “transient” updates. The paper behind the immer library.

In code · ts

type Tree = { key: number; left: Tree; right: Tree } | null;

// insert copies only the nodes on the path from the root to the new key
function insert(t: Tree, key: number): Tree {
  if (t === null) return { key, left: null, right: null };
  if (key < t.key) {
    const left = insert(t.left, key);
    return left === t.left ? t : { ...t, left };
  }
  if (key > t.key) {
    const right = insert(t.right, key);
    return right === t.right ? t : { ...t, right };
  }
  return t; // already present: share the whole tree
}

const keys = (t: Tree): number[] =>
  t === null ? [] : [...keys(t.left), t.key, ...keys(t.right)];

let v1: Tree = null;
for (const k of [50, 30, 70, 20, 40, 60, 80]) v1 = insert(v1, k);
const v2 = insert(v1, 65);

console.log(keys(v1)); // [20, 30, 40, 50, 60, 70, 80]: the old version still works
console.log(keys(v2)); // [20, 30, 40, 50, 60, 65, 70, 80]
console.log(v1!.left === v2!.left); // true: the whole left half is shared
console.log(v1!.right!.right === v2!.right!.right); // true: so is the 80 leaf
console.log(v1!.right === v2!.right); // false: only 50, 70 and 60 were copied
console.log(insert(v2, 65) === v2); // true: no change, no copy

Often confused with

Functional programmingData structuresPersistence: state, events and replay
Where it came from1986–2015

Persistence was studied first as an algorithms problem. Driscoll, Sarnak, Sleator and Tarjan presented “Making Data Structures Persistent” in 1986 (journal version 1989), naming ephemeral, partially and fully persistent structures and giving general methods for linked structures with O(1) amortized space per update step. They noted the simpler rival, found independently by several researchers: copy the whole access path on each update, at O(log n) space per change. In functional languages that path copying happens by itself, because nothing is ever overwritten.

What functional programmers lacked was a toolbox. In 1996 Chris Okasaki’s thesis at Carnegie Mellon observed that most textbook data structures depend on assignment, and that amortized structures break when old versions are reused. Okasaki showed that lazy evaluation with memoization reconciles amortization with persistence, and published numerous new structures; the 1998 book with Standard ML and Haskell code became the field’s reference. Kaplan and Tarjan meanwhile solved catenable deques in worst-case O(1) time without laziness.

The ideas reached mainstream programmers through engineering rather than theory. Rich Hickey found Okasaki’s structures too slow for Clojure and their amortized costs hard to explain, so in 2006–07 Hickey built persistent 32-way trees on Phil Bagwell’s hash array mapped tries and shipped them as Clojure’s default collections. Scala, Haskell and Erlang adopted persistent HAMTs, Facebook’s Immutable.js (2014) brought them to JavaScript and React apps, and Bagwell and Rompf’s RRB-Trees added fast concatenation to the same vectors.

Why it’s built this way

Copy the path, share the rest
Copying the whole structure on every change costs O(n). Copying only the nodes on the path to the change costs O(log n) in a balanced tree, and the copies can point at the untouched subtrees because those will never change.
Pay for expensive work with laziness, not saved credits
Classic amortization banks savings that only one future can spend; with persistence, many futures compete for them. A memoized suspension can be shared by every version that needs it, so Okasaki accounted for debt instead of savings.
Wide 32-way nodes instead of binary trees
Bagwell’s tries and Hickey’s vectors branch 32 ways, so trees are only a few levels deep and each lookup touches a handful of compact arrays. Hickey found the result performed more like O(1) than its O(log n) bound.
An immutable interface, not necessarily a pure implementation
Hickey wrote that it mattered only that consumers saw immutable, persistent values; Hickey’s nodes are built with mutation and never changed afterwards. Conchon and Filliâtre’s persistent union-find likewise hides side effects behind a persistent interface.

Timeline

  1. 1986

    Driscoll, Sarnak, Sleator and Tarjan present “Making Data Structures Persistent”

  2. 1996

    Okasaki’s thesis reconciles amortization and persistence with lazy evaluation

  3. 1999

    Kaplan and Tarjan publish deques with worst-case O(1) catenation

  4. 2001

    Bagwell publishes “Ideal Hash Trees”

  5. 2006

    Hinze and Paterson publish finger trees

  6. 2007

    Clojure ships persistent hash maps and vectors as its default collections

  7. 2015

    Stucki and colleagues present the RRB vector at ICFP

Sources27

Improve this page on GitHub