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]>

and 

<[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.

Touch the future

I recently implemented concurrency constructs for Streme, and I decided to go with future/touch.

(future exp) allows the programmer to say to the evaluator: I will need the value of exp some time in the future. This means the evaluator has more freedom in choosing when to evaluate exp. Some possibilities:

1. Evaluate exp directly: this gives the future construct the semantics of the identity function.
2. Evaluate exp when its value is needed: the future becomes a delay.
3. The evaluation can start between 1 and 2, and in the best-case scenario the value is available when needed.

Of course, 3 is by far the most interesting option because exp can be concurrently evaluated with the rest of the program, including the thread that constructed the future. There is one "small" detail of course that should be mentioned: choosing between 1, 2 and 3 potentially changes the semantics of a program. More on that later.

(future exp) creates a future value that can be resolved by its cousin procedure touch. touch always returns the value of exp, but it is possible it has to wait for it to become available, so it is a blocking operation.

Futures are first class values and can freely be passed around. So when is it necessary to use touch? At least before the value of exp is needed. And who has to perform the touch? Again some options:

1. The programmer manually introduces touch where necessary.
2. The evaluator, when needing a strict value, checks for futures and touches if necessary.
3. The evaluator does value-flow analysis and introduces the necessary touch operations.

And again option 3 is the most attractive. Option 1 requires the programmer to keep track of where futures flow, which can increase the complexity of writing non-trivial programs. Option 2 incurs a performance penalty: if every time the evaluation of, say, (+ a b) actually becomes (let ((a-value (if (future? a) (touch a) a) (b-value (if (future? b) (touch b) b)) (+ a-value b-value)) at runtime, it is easy to see why this is so.

Options 2 and 3 makes the use of futures more transparent for the programmer, since he or she doesn't have to deal with touch explicitly. But wait... let's extend this principle. What if the evaluator can perform an analysis to decide where to introduce futures? That way, not only touch but also future becomes transparent, resulting in automatic parallelization.

The analysis needed for safe introduction of futures is dependency analysis. As said before, introducing futures can change the semantics of a program. The only way to make sure this doesn't happen is to check for interdependence between expressions. In short, if two expressions have no dependencies, evaluating them in parallel cannot change the meaning of a program.

So, to conclude, future and touch available at the source level in Streme only to manually test out concurrency in Streme. Ideally, in the near "future", the programmer should not worry about future/touch at all, since the evaluator will take care of it. Hopefully.