Saturday, April 2, 2011

2-3 finger trees in ASCII

2-3 finger trees are a wonderful general-purpose data structure described in a paper by Hinze and Paterson. Recently, I wanted to find out how finger trees "work" so I figured that it would be easier to get started by reading some more informal material on finger trees first, instead of just diving into the paper and a couple of existing implementations. I expected to see some examples of operations being performed on a finger tree, but I could not find any suitable material that was sufficiently detailed but not overly technical (like the paper, arguably). So I decided to write it up myself. And here it is: basic finger tree operations in ASCII.

In this article I discuss three basic types of operations on finger trees:
  1. adding elements
  2. deconstructing trees into head and tail
  3. appending two finger trees
I don't discuss reductions, monoid caching, splitting, and the usefulness of finger trees and their applications in general. That may be for a follow-up article.  The intention is just to give a feeling of how basic operations on finger trees are carried out, and to explain the mechanisms behind them that keep returning in one form or another. Therefore, these mechanism carry over to other operations as well, including (and most importantly) splitting. In fact, when I understood the three operations listed above, I was able to implement the details of the split operation with only a little guidance provided by the paper. My goal is that you are able to do so as well.

There are three kinds of finger trees:

F = <>                (Empty)
  = <a>               (Single)
  = <[1-4], F, [1-4]> (Deep)
The Empty finger tree is, well, empty. The Single finger tree stores exactly one item. The Deep finger tree consists of three parts. The middle part is another finger tree, so it is recursive. The first and last part are called the prefix and suffix respectively, and they contain so-called digits. An important invariant of both prefixes and suffixes in Deep finger trees is that they always contain between 1 and 4 digits, inclusive.

You can think of a finger tree as a structure that defines a sequence of elements of any type, say type T. The Empty tree represents the empty sequence, a Single tree represents one single element, and a Deep tree represents at least two elements in a sequence starting at its prefix, ranging over the middle tree, ending in its suffix.

The first simple operation we can perform on finger trees is adding elements to the right using the addRight operation, also called snoc (inverse of cons).

We start with an Empty finger tree <>. If we push an element onto its right side, we end up with a Single finger tree. 

<>.addRight(a) = <a>

If we add yet another element on the right, it becomes a Deep finger tree. 

<a>.addRight(b) = <[a], <>, [b]>

This Deep tree has an Empty tree in the middle, a prefix consisting of one digit (element a) and a suffix consisting of one digit (element b).

We add another three elements on the right. 

<[a], <>, [b]>.addRight(c).addRight(d).addRight(e) 
    = <[a], <>, [b, c, d, e]>

The additional elements are simply appended to the suffix. Now, if we add another element on the right side, we cannot simply add it to the suffix as before because this would break our invariant that states that a suffix can have a maximum of 4 digits. Therefore, to add another element we have to split the suffix and move a part of it into the middle tree. 

<[a], <>, [b, c, d, e]>.addRight(f) 
    = <[a], <(b, c, d)>, [e, f]>

In the middle of the resulting tree we have a Single finger tree that contains a single node consisting of three elements. This is another important characteristic of a finger tree: if digits in a Deep tree have type T, the elements and digits in the middle tree are of type Node<T>. A Deep tree at level 0 has elements as digits, but its middle tree has nodes of elements. If that middle tree is another Deep tree, it has nodes of nodes of elements in its middle tree, and so on.

We will represent nodes as elements between parentheses. There are two type of nodes: 2-nodes and 3-nodes. When splitting the suffix in the previous example, we could also have opted for a 2-node in the middle, leaving 3 digits in the suffix of the resulting Deep tree.

Adding to the left of a finger tree (addLeft or cons) is a mirror of the addRight operation. Starting with an Empty tree, and adding elements a..l we end up with the following finger tree: 

<[l, k], <[(j, i, h), (g, f, e)], <>, [(d, c, b)]>, [a]>

When adding elements to a Deep tree, we have only have to protect the 1-4 digits invariant by making sure that we do not end up with 5 digits. When taking away elements from a Deep tree, we have to perform the opposite check and guard ourselves from ending up with an empty prefix or suffix. To see how this works, let's look at the leftHead and leftTail operation. leftHead is simple: take the leftmost item of the prefix. leftTail returns the same tree without the item returned by  leftHead. leftTail is straightforward most of the time. Abstracting away the middle and the suffix, we have for example 

<[l, k], M, sf>.leftHead() = l 
<[l, k], M, sf>.leftTail() = <[k], M, sf>

Now if we want to take the leftTail again, then we would end up with an empty prefix. The trick here is to pull a digit from the middle tree M. But M could be Empty, so we are forced to check this as well.

Therefore, if M is Empty, then 

<[k], <>, sf>.leftTail() = treeOfDigits(sf)

treeOfDigits is simply defined as the function that takes a number of digits and turns it into a finger tree (for example by consecutively applying addRight):

treeOfDigits([d]) = <d>
treeOfDigits([d1, d2, d3, d4]) = <[d1], <>, [d2, d3, d4]>

For example:

<[k], <>, [c, b, a]>.leftTail() 
    = treeOf(c, b, a)
    = <[c], <>, [b, a]>

If M is not Empty then

<[k], M, sf>.leftTail() 
    = <M.leftHead().toDigits(), M.leftTail(), sf>

If the type of digits in F is T, then the items in the middle tree M of F are of type Node. Contrary to packing digits into 2-nodes and 3-nodes when adding to the middle, we now have to deconstruct these nodes coming from M to end up with digits of the right type. This can be accomplished by defining a toDigits function on nodes. Because all nodes either pack 2 or 3 items we are sure that the 1-4 digits invariant is maintained at all times.

A concrete example of using leftTail with a non-Empty middle tree is 

<[d], <(x, y, z)>, [c, b, a]>.leftTail() 
    = <(x, y, z).toDigits(), <>, [c, b, a]> 
    = <[x, y, z], <>, [c, b, a]>

The above example also shows that you go from a Single tree to an Empty tree when taking the leftTail of the first. We also go from a Deep to an Single tree when taking the leftTail of the first. 

<[a], <>, [b]>.leftTail() = <b>
<a>.leftTail() = <>

Finaly, for Empty trees, leftTail makes no sense and is undefined.

Appending two finger trees is not that difficult as well. Again, the cases involving Empty and Single are trivial.

<>.append(<>) = <>
<a>.append(<>) = <>.append(<a>) = <a>
<a>.append(<b>) = <[a], <>, [b]>

For Deep trees, we first observe that we can preserve the leftmost prefix and the rightmost suffix when appending. 

<prl, Ml, sfl>.append(<prr, Mr, sfr>) = <prl, M, sfr>

We still need to determine M, which only depends on Ml, sfl, prr, and Mr. Again we have to think of our invariant (1-4 digits) and typing rule (adding to or removing digits from the middle tree involves constructing and deconstructing nodes respectively).

The paper by Hinze and Paterson suggests the following algorithm:

1) toNodes: make a list L of nodes based on the digits in sfl and prr
2) app: append Ml, L and Mr, possibly by recursively going back to step 1

To illustrate how this works, let's append the following finger trees: 

<[0], <(1, 2, 3)>, [4, 5, 6, 7]>


<[a],<[(b, c, d)], <>, [(e, f, g), (h, i, j)]>, [k, l]>

First of all, the result will be in the form of <[0], M, [k, l]>. We start computing M by concatenating the "middle" digits:

L = toNodes(4, 5, 6, 7, a) = [(4, 5, 6), (7, a)]

L is a list of 2 digits: a 3-node and a 2-node. We could also take L = [(4, 5), (6, 7, a)] but this is not terribly important. What is important, is that this step reduces a list of possibly more than 4 digits of type T to a list of maximum 3 digits of type Node<T>, required for our middle tree M.

In general, toNodes takes a minimum of 2 digits and a maximum of 12 digits to compute a list of anything between 1 2-node and 4 3-nodes depending on its input, preferring smaller resulting list sizes over larger ones (or the use of 3-nodes over 2-nodes where possible).

toNodes(1, 2) = [(1, 2)] 
toNodes(1, 2, 3) = [(1, 2, 3)] 
toNodes(1, 2, 3, 4) = [(1, 2), (3, 4)] 
toNodes(1, 2, 3, 4, 5, 6, 7, 8) = [(1, 2, 3), (4, 5, 6), (7, 8)] 
toNodes(1..12) = [(1, 2, 3), (4, 5, 6), (7, 8, 9), (10, 11, 12)]

Continuing with the example, now that we have L for our M we call an internal append, called app, to append Ml, L, and Mr.

M = app(<(1, 2, 3)>, [(4, 5, 6), (7, a)], <[(b, c, d)], <>, [(e, f, g), (h, i, j)]>)

This almost looks like our regular append operation of two finger trees: we have two trees Ml and Mr but here we also have a list L of digits in the middle. Let's break it down into distinct cases again.

First, the base cases where we don't recursively call app:

app(<>, [d1, ..., dn], F') = F'.addLeft(dn)...addLeft(d1)
app(F', [d1, ..., dn], <>) = F'.addRight(d1)...addRight(dn)
app(<a>, [d1, ..., dn], F') = F'.addLeft(dn)...addLeft(d1).addLeft(a)
app(F', [d1, ..., dn], <a>) = F'.addRight(d1)...addRight(dn).addRight(a)

The only remaining case is when we have 2 Deep trees. We return a new Deep tree for which we recursively call app to construct its middle tree.

app(<pr1, M1, [sfd1, ..., sfdn]>, [d1, ..., dn], <[prd1, ..., prdn], M2, sf2>
   = <pr1, app(M1, toNodes(sfd1, ..., sfdn, d1, ..., dn, prd1, ..., prdn), M2), sf2)>

The recursion is guaranteed to end because at each step we deconstruct Deep trees, splitting off a prefix and a suffix and packing the remaining digits using toNodes. Eventually we will end up in a base case because our trees have finite height.

Going back to our example, we compute 

M = app(<(1, 2, 3)>, [(4, 5, 6), (7, a)], <[(b, c, d)], <>, [(e, f, g), (h, i, j)]>) 
= <[(b, c, d)], <>, [(e, f, g), (h, i, j)]>.addLeft((7, a)).addLeft((4, 5, 6)).addLeft((1, 2, 3)) 
= <[(7, a), (b, c, d)], <>, [(e, f, g), (h, i, j)]>.addLeft((4, 5, 6)).addLeft((1, 2, 3)) 
= <[(4, 5, 6), (7, a), (b, c, d)], <>, [(e, f, g), (h, i, j)]>.addLeft((1, 2, 3)) 
= <[(1, 2, 3), (4, 5, 6), (7, a), (b, c, d)], <>, [(e, f, g), (h, i, j)]>

Substituting this finger tree for M in <[0], M, [k, l]> gives us the final result for our example of append.