For ages, I’ve been promising to write about finger trees. Finger trees are
an incredibly elegant and simple structure for implementing sequence-based
data structures. They’re primarily used in functional languages, but there’s nothing
stopping an imperative-language programmer from using them as well.

In functional programming languages, lists are incredibly common. They show up everywhere; they’re just so easy to use for recursive iteration that they’re ubiquitous. I can’t think of
any non-trivial program that I’ve written in Haskell, Lisp, or OCaml that doesn’t use lists. (Heck, I’ve wound up using cons-cell libraries a couple of times in C++.)

Of course, lists aren’t perfect. In fact, for some things, they absolutely suck. Suppose I’ve got a really long list – like a list of names and phone numbers from a telephone book. My local phone book has 600 pages of names; and the pages are incredibly dense – there’ve got to be at least a couple of hundred names per page. So in a phone book for a suburban region of New York City, the list of phone numbers will have 120,000 names. Now imagine that I want to look
up one name in that list – on average, I’m going to have to chase through 60,000 pointers. 60,000 isn’t a huge number for a computer, but still, chasing 60,000 pointers is a pretty big deal. If I stored them in an array, it would be a lot less convenient for some tasks, but I could use
binary search to find names, and I could find any name in no more than 16 comparisons – and the whole shebang would be contiguous, so I wouldn’t even be chasing pointers.

What finger trees do is give me a way of representing a list that has both the convenience
of the traditional cons list, and the search efficiency of the array based method.

The basic idea of the finger tree is amazingly simple. It’s a balanced tree where you store
all of the data in the leaves. The internal nodes are just a structure on which you can hang
annotations, which you can use for optimizing search operations on the tree. What makes
the finger tree so elegant is the way that some very smart people have generalized the idea of
annotations to make finger trees into a single, easily customizable structure that’s useful for so
many different purposes: you customize the annotations that you’re going to store in the internal nodes according to the main use of your tree.

Let’s look at a simple example – a sorted list, like the phone book. Below is a two-three tree
with values in the leafs. The list is the sequence of leafs from left to right.

In a finger tree, we label the internal nodes of the tree with a count: the number of
values stored in the subtree rooted at an internal node is stored in the node – like in the image below. So, now, to look up
the seventh element of the list, we look at the left child of the root: it’s got five children. So
we know that the 7th element is in the right subtree. Then we search the right subtree: the left
child has 2 values – so the leaf we want is going to be in the left subtree: since that node has
leaves as children, it’s the second child of the leaf.

By doing that labeling, we’ve got a list where an array-like index operator takes O(lg n) steps. It’s also O(lg n) for arbitrary inserts. And the time to maintain the counts doesn’t change the algorithmic complexity, and it’s extremely fast in practice.

But there’s more to like about it than that. It’s downright easy to keep every version of the list that ever occurred in the history of the program. If you think about it, each operation to modify the list of values has a bubble-up effect, changing the internal nodes of the tree above it. Those internal nodes are very small and simple: if you copy them instead of mutate them, then you get very lightweight persistence. A great example of how this works is: if you use a finger tree to represent the text buffer of an editor, you don’t need to implement undo: you just keep the old versions of the text buffer! You can do that by just copying a small number of internal nodes as things change; the text itself, you never change – so the total memory for text is the size of the original buffer plus whatever you inserted. In terms of memory use, the
memory performance of a finger-tree based persistent history is roughly the same as the amount of memory needed to create an undo history. (Depending on your exact implementation, and the particular usage pattern of the editor, either one can come out ahead.)

But we still haven’t even gotten to the most beautiful thing about finger trees!

The idea of a finger tree is that the internal nodes store some kind of data that makes it
possible for you to find a particular desired value very quickly. In the example we looked at, the
thing we wanted to be able to quickly was array style indexing. But finger trees are good for much
more than that. Another canonical example is a priority queue. In a priority queue, you’ve got a
collection of tasks that need to be performed. Each task has a priority, representing how
important it is. Whenever a processor becomes available, the highest priority task should be
executed. Priorities are generally handled in reverse order: priority 1 is the highest, 2 is lower
priority than 1; 3 is lower than 1 and 2, and so on. (It’s done that way so that it’s always easy
to add something at a lower priority.) The way priorities are handled, the highest priority always
goes first; you should never start a priority 2 when there’s a priority 1 in the queue; but if
you’ve got two priority 2 tasks, they should be executed in the order in which they were
inserted.

We can create a priority queue as a list of tasks, using a finger-tree based list, just like we did for the array indexing. When we add a new task to the queue, we’ll always add it at the
end of the list. What we want to do is to try to pick the leftmost high-priority task in the
list.

How can we annotate the tree to make it easy to quickly find the leftmost highest priority
task? We just label each internal node with the highest priority containing in any of its
children. Then we search the tree, looking for the highest-value child at each level; if there’s a
tie, we go to the leftmost. Presto: O(lg n) to find and remove the highest priority task; O(lg n)
to insert a new task.

Now, the real question is: what do these two have in common? That is, if we wanted to
implement a generic finger tree, what do the annotations have in common?

The annotations are monoids over some kind of number. If you remember abstract
algebra, a monoid is a set of values with an associative operation and an identity element.
As long as the annotations are a monoid, you can make a finger tree based on the annotations.
(Actually, you don’t even strictly need them to be monoids over numbers; you need to be able
to do an ordered comparison between the annotation values – so what you really need is
just a monoid over ordered values.)

In the list of integers, the set of annotation values are natural numbers, the operation
is addition, and the identity is (obviously) 0. In the priority queue, the set of annotations are also natural numbers, but the operation is min; identity is the maximum priority value – which will be the maximum size of the integer type used for priority.

If you parameterize your finger-tree implementation on the monoid, you can use
exactly the same finger-tree code for both the indexable list and the priority queue. How
can that be? This is where things get subtle: we need to dive in a bit more and see just what the
fact that the annotation is a monoid really means.

As I said above, a monoid is a set of values with a single, associative operation. (For
this discussion, I’m going to use ♦ for the monoid operation.) What associativity
means is that given any sequence of values (v₁, …, v_n),
if you apply ♦ to the set, any way of parenthesizing it will produce the
same result: you can group the list any way you want.

v₁ ♦ v₂ ♦ v₃ ♦ v₄ ♦ v₅ ♦ v₆ ♦ v₇ ♦ v₈ ♦ v₉ =
((v₁ ♦ v₂) ♦ (v₃ ♦ v₄)) ♦ ((v₅ ♦ v₆) ♦ ((v₇ ♦ v₈) ♦ v₉)) =
((((((((v₁ ♦ v₂) ♦ v₃) ♦ v₄) ♦ v₅) ♦ v₆) ♦ v₇) ♦ v₈) ♦ v₉)

What that means in terms our finger tree is that the value at the root of any
subtree is a measure of its subtree – and that the grouping of the children
of that subtree doesn’t matter. You can structure a tree any way that you like: so long as you preserve the order of the leaves, it doesn’t affect the annotation value of its root; and the annotation value of the root of any subtree tells you a crucial bit of information
about what’s in the subtree.

And there’s the key: what does it tell you?

When we go to search a finger tree for some value, we’re searching for a
value with a particular measure. What the monoid does is allow us to describe
that measure not just in terms of the measure of individual nodes, but
in terms of sets of nodes. And the tree gives us a natural way of
dividing the list into a set of candidates, and not-candidates. Put the two
together, and you’ve got a structure that is custom designed for enabling binary
search (or, rather, tree based search; if you use a 2/3 tree as the basis of
your finger tree, you’ve got a 2/3 tree search; if you use a balanced binary
tree, then you’ve got binary search.)

Let’s look at a couple of examples. First, let’s pull out our array tree.
Look back at the example tree towards the top of the post. We’re going to look
for the seventh element of the list. We start at the root: the measure of the
root is
((1♦1♦1)♦(1♦1))♦((1♦1)♦(1♦1)) –
or (1♦1♦1♦1♦1♦1♦1♦1♦1) – which
is 9.

This tells us that the entire tree has 9 leafs. Doesn’t matter how they’re
arranged: every tree with 9 leaves will produce the same measure.

We want to find the 7th value. But we don’t know where it is. So we take the
sequence of values represented by the tree, and split it, and then use the
monoid measure of the two subtrees to compute the measures for the sets
of values contained by their leafs. We split according to the tree: we could
take either the left half, or the right half. To figure out which, we look at
the measures. The combined measure of the nodes on the left is 5; the combined
measure on the right is 4. So we know that our target is on the right, and we’re
looking for element 2 on the right. And again, we want to split the
remaining set of values, and only search the half that might contain
our target. We again look at subtrees, and find that our
target is on the left. We then have a subtree whose measure is 1♦1=2, so
the target is on the right. And we’ve narrowed it to one node.

If you look at that process – it’s precisely a binary search of the list.

Now, let’s try looking at a priority queue. Here’s a binary tree priority
queue, which contains a set of tasks A (pri 3), B (pri 9), C(pri 4), D(pri 3),
E(pri 1), F(pri 3), and G (pri 4). As a finger tree, that would look like the
following:

The monoid set for the priority queue is the set of possible priority
values; the operation is natural-number minimum. So for this queue, it’s
3♦9♦4♦3♦1♦3♦4 – or min(3, 9, 4, 3, 1, 3, 4) =
1.

Now, we want to to split the queue into two subqueues, and only search the
subqueue that contains the highest priority task. We do that using the tree:
we look at the measure of the left subtree (which is annotated with the measure of the left subset), and the right subtree (which is annotated with the measure of the right subset). The left subset has measure 1, the right has measure 4. So the highest priority task is in the left subset (or subtree).

Again, we want to divide the set of tasks into two subsets, and only search
the subset that contains the highest priority task. The measure of the left
subtree-subset is 3; the right is 1. So it’s in the right subtree. And so on,
until we wind up at E.