{"id":775,"date":"2009-05-27T16:36:35","date_gmt":"2009-05-27T16:36:35","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2009\/05\/27\/finally-finger-trees\/"},"modified":"2009-05-27T16:36:35","modified_gmt":"2009-05-27T16:36:35","slug":"finally-finger-trees","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2009\/05\/27\/finally-finger-trees\/","title":{"rendered":"Finally: Finger Trees!"},"content":{"rendered":"

\"stone<\/p>\n

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

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
\nany 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++.)<\/p>\n

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
\nup 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
\nbinary 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.<\/p>\n

What finger trees do is give me a way of representing a list that has both the convenience
\nof the traditional cons list, and the search efficiency of the array based method.<\/p>\n

<\/p>\n

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

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

\"leaf-tree.png\"<\/div>\n

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

\"counted-finger-tree.png\"<\/div>\n

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.<\/p>\n

But there’s more to like about it than that. It’s downright easy to keep every<\/em> 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
\nmemory 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.)<\/p>\n

But we still haven’t even gotten to the most beautiful thing about finger trees!<\/p>\n

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

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
\nend of the list. What we want to do is to try to pick the leftmost high-priority task in the
\nlist.<\/p>\n

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

Now, the real question is: what do these two have in common? That is, if we wanted to
\nimplement a generic<\/em> finger tree, what do the annotations have in common?<\/p>\n

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

In the list of integers, the set of annotation values are natural numbers, the operation
\nis 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.<\/p>\n

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

As I said above, a monoid is a set of values with a single, associative operation. (For
\nthis discussion, I’m going to use ♦ for the monoid operation.) What associativity
\nmeans is that given any sequence of values (v1<\/sub>, …, vn<\/sub>),
\nif you apply ♦ to the set, any way of parenthesizing it will produce the
\nsame result: you can group the list any way you want.<\/p>\n

v1<\/sub> ♦ v2<\/sub> ♦ v3<\/sub> ♦ v4<\/sub> ♦ v5<\/sub> ♦ v6<\/sub> ♦ v7<\/sub> ♦ v8<\/sub> ♦ v9<\/sub> =
\n((v1<\/sub> ♦ v2<\/sub>) ♦ (v3<\/sub> ♦ v4<\/sub>)) ♦ ((v5<\/sub> ♦ v6<\/sub>) ♦ ((v7<\/sub> ♦ v8<\/sub>) ♦ v9<\/sub>)) =
\n((((((((v1<\/sub> ♦ v2<\/sub>) ♦ v3<\/sub>) ♦ v4<\/sub>) ♦ v5<\/sub>) ♦ v6<\/sub>) ♦ v7<\/sub>) ♦ v8<\/sub>) ♦ v9<\/sub>)\n<\/p>\n

What that means in terms our finger tree is that the value at the root of any
\nsubtree is a measure<\/em> of its subtree – and that the grouping of the children
\nof 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
\nabout what’s in the subtree.<\/p>\n

And there’s the key: what does it tell you?<\/p>\n

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

Let’s look at a couple of examples. First, let’s pull out our array tree.
\nLook back at the example tree towards the top of the post. We’re going to look
\nfor the seventh element of the list. We start at the root: the measure of the
\nroot is
\n((1♦1♦1)♦(1♦1))♦((1♦1)♦(1♦1)) –
\nor (1♦1♦1♦1♦1♦1♦1♦1♦1) – which
\nis 9. <\/p>\n

This tells us that the entire tree has 9 leafs. Doesn’t matter how they’re
\narranged: every tree with 9 leaves will produce the same measure.<\/p>\n

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

If you look at that process – it’s precisely<\/em> a binary search of the list.<\/p>\n

Now, let’s try looking at a priority queue. Here’s a binary tree priority
\nqueue, which contains a set of tasks A (pri 3), B (pri 9), C(pri 4), D(pri 3),
\nE(pri 1), F(pri 3), and G (pri 4). As a finger tree, that would look like the
\nfollowing:<\/p>\n

\"finger-pqueue.png\"<\/div>\n

The monoid set for the priority queue is the set of possible priority
\nvalues; the operation is natural-number minimum. So for this queue, it’s
\n3♦9♦4♦3♦1♦3♦4 – or min(3, 9, 4, 3, 1, 3, 4) =
\n1.<\/p>\n

Now, we want to to split the queue into two subqueues, and only search the
\nsubqueue that contains the highest priority task. We do that using the tree:
\nwe 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).<\/p>\n

Again, we want to divide the set of tasks into two subsets, and only search
\nthe subset that contains the highest priority task. The measure of the left
\nsubtree-subset is 3; the right is 1. So it’s in the right subtree. And so on,
\nuntil we wind up at E.<\/p>\n","protected":false},"excerpt":{"rendered":"

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 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[83],"tags":[],"class_list":["post-775","post","type-post","status-publish","format-standard","hentry","category-data-structures"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-cv","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/775","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=775"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/775\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=775"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=775"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=775"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}