As an alert commenter pointed out, I left out one really important thing in

my earlier post about finger trees. That's what I get for trying to write when

I'm sick :-). Seriously, this is a point that's implied by the post as it stands, but never explicitly stated - and since it's really important, it

should be stated explicitly.

The monoid-annotated tree structure doesn't *replace* the original

data structure: it's superimposed on it.

So, as I said: cons-cell style lists are ubiquitous and beloved by

functional and non-functional programmers. In finger trees, you're

*not* getting rid of them. The point of finger trees is to let

you *keep* the convenient data structure, with its basic operations

and properties intact, and to *augment* it with a tree that lets you search it efficiently.

To illustrate: here's the number list example from yesterdays post. The

original list is at the bottom, with green pointers representing the

original cons-list next-pointers. The monoid-annotated tree is on top,

with red pointers. The combination of the original list with the

monoid annotated tree is a finger tree.

The point of this is that you've still got your cons list. All of the

beautiful recursive/iterative algorithms that walk the list continue to

work *exactly* the way that they would in the traditional cons-list: for code that walks the list, the fact that there are finger-tree pointers

sitting on top of the list is irrelevant - and, in fact, completely invisible. For algorithms that want to search the list, the tree structure is there,

and allows the searches to be performed much more quickly than they could be on

the traditional list. The superposition of those two structures is the

genius of the finger tree.