Finger trees

Ralf Hinze and Ross Paterson’s 2-3 finger trees (2006) keep one to four elements in a “digit” at each end, called fingers, and a deeper finger tree of 2-3 nodes in the middle. Adding or removing at either end takes amortized O(1) time, and concatenating or splitting takes time logarithmic in the size of the smaller piece. They grew out of the implicit deques in Okasaki’s book: replacing pairs with 2-3 nodes makes concatenation efficient.

The general part is the measurement. Each internal node caches a value from a monoid: the size of its subtree gives an indexed sequence, the maximum priority gives a priority queue, the largest key gives an ordered sequence, so one split function serves all of them. Earlier structures by Kaplan and Tarjan reach the same bounds, some in the worst case, but are much more complex.

Haskell’s Data.Sequence is a size-annotated finger tree: O(1) at both ends, O(log n) concatenation, splitting and indexing, with bounds that hold even when sequences are shared. It is slower than a list when you only need a stack, and its memory use is high: Stucki and colleagues measured finger trees an order of magnitude larger than RRB vectors.