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.