Looking Out To Sea

I’ve seen a lot of references to FingerTrees around but not much explanation of what they are or where they should be used. The common reference is to 2-3 Fingertrees suggested by Ralph Hinze and Ross Paterson in Finger Trees: A Simple General-purpose Data Structure, so that seemed the best place to look.

There is also a working implementation published of 2-3 Fingertrees on Hackage (version 0.0 at time of writing), so between the two I should be able to work out the details for this structure and glean some idea of where to use it.

For the non-programmers, I include a video of Radiohead’s Treefingers, which I was sure was called Fingertrees when I started writing this post. If you search for “radiohead fingertrees” you’ll see I’m not the only one!

Preliminaries

Section 1 of the paper discusses the ubiquity of singly-linked lists in functional programming and highlights the things which lists make difficult — constant-time appends and catenation, for example.

Section 2 goes over monoids and a generalised reduction/folding framework. (In the paper the typeclass they use is called Reduce but the implementation on Hackage imports Data.Foldable to do the same thing.)

These are both fairly standard ideas used in functional programming and they both have standard Haskell implementations now. I think monoids are particularly elegant abstractions so it’s a shame that they have such ugly names in the standard libraries: mempty and mappend. Oh well.

2-3 Trees and Fingertrees

Initially the authors present 2-3 Trees, which are a bit like binary trees, except each internal node can have 2 or 3 children. Not quite as liberal as rose trees, but not as restricted as standard binary trees.

data Tree a = Leaf a
            | Branch (Tree (Node a))
 
data Node a = Node2 a a
            | Node3 a a a

This 2-3 tree ensures that the leaves of the tree are all at the same level. Each tree is either some value contained in a leaf, or a branching point containing further trees.

The task the authors set themselves is to augment such a tree to make an efficient sequence structure. To do this they place “fingers” at the start and end points, where new values would be added or removed.

The final data type looks like this. It’s rather complex to explain all in one go, so we’ll pare it back and build it back up again. But this is what we’re working towards:

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

Initially it helps to imagine that Digit is just a list, and to ignore the v type variable for now. So think of this as our starting point:

data FingerTree a
    = Empty
    | Single a
    | Deep [a] (FingerTree a) [a]

The last line looks very much like the zipper for a list:

data Zipper a = Zipper [a] a [a]

These zippered lists have a unique “fingered” value and a left and right context. It’s like having two stacks to transfer values between. But the overall structure is just a list.

3     5
2     6   ==  1 2 3 4 5 6 7
1  4  7             ^

So you can move left and right along the list by pushing and popping the stacks:

4
3     
2     6   ==  1 2 3 4 5 6 7
1  5  7               ^

You can see there’s a “left stack” and a “right stack” and in the middle some “interesting value”, the one we’re pointing to. In an impure language we would approach this scenario with just a pointer. Zippers provide speedy access without the pain of mutable structures. Now before I digressed, we had a simplified example which I asserted looked like the list zipper:

data FingerTree a
    = Empty
    | Single a
    | Deep [a] (FingerTree a) [a]

The last line clearly shows the “left stack” ([a]) and the “right stack” surrounding an “interesting value” (FingerTree a). (The other two lines are trivial examples, or dead-end implementations. If we were dealing with ordinary lists they would be the empty list, [] and a singleton [a].) The interesting part here is that instead of just a single item as our “interesting value” we’ve got a whole new data structure. How does this work?

Let’s think about what we have, first. Some tree with left and right values stored in lists. And in the middle a something:

3     7
2     8  ==  1 2 3 * 7 8 9
1  *  9

But what’s that *? It’s another fingertree! We’ll expand the * and abstract the other values as [ and ], the left and right stacks:

  5        ==  [ 4 5 * 6 ] == 1 2 3 ( 4 5 * 6 ) 7 8 9
[ 4 * 6 ]

We can replace the final * with an empty tree, as follows:

3        7
2        8
1  5     9  ==  [ 4 5 * 6 ] == 1 2 3 ( 4 5 _ 6 ) 7 8 9
[  4 _ 6 ]

I hope that diagram makes some sort of sense… the general idea is that the start and end of every sequence is store at the top level, and the middle is stored further down. At each level there’s another chunk of the start of the list and another chunk of the end of the list.

This means prepend and append operations are amortised constant-time operations. Every so often the length of the start and end sequences need to be trimmed, and the excess pushed into the middle, so it’s not proper constant-time.

Every time values are attached to the front or back the excess is squeezed into the middle, trickling down until it reaches its right level.

Annotating and making useful

The structure as outlined above isn’t very useful. It’s the skeleton of a system, but the paper advertises a “general purpose data structure” which isn’t apparent yet. The next stage the authors carry out is to annotate the structure with useful values at each branch point, to specialise the general structure to particular applications.

Each branching point contains an annotation value which can be used to implement useful data structures — priority queues for example. We’ll add the annotations back to our simplified data type next.

data FingerTree v a
    = Empty
    | Single a
    | Deep v [a] (FingerTree v a)) [a]

The value v is a summary of everything below it in the tree. Notice that only the Deep constructor takes an annotation value, because it should be trivially calculable for Empty and Single.

Let’s imagine we’re using a fingertree as a string representation. In this case v can be used to represent the number of characters in the fingertree. When you catenate strings it’s really easy to just add together annotations to get the new total length. It’s a string that knows its own length — how revolutionary! :-) (I think that the Yi text editor written in Haskell uses fingertees of bytestrings to represent text internally.)

The annotation values (and their combining operations) can be chosen with more interesting applications in mind. Ordered values combined with max or min operations produce quite elegant priority queues. There are more examples in the paper, and more detail about the implementation that I have glossed over.

Really getting your head around fingertrees is quite difficult. The concept is quite easy to explain but the implementation is a little baffling, especially the “bush” design which enforces balanced trees. But don’t let me put you off.