Finger trees allow you to do amazing things. In essence they let you build an index, or multiple indices, for your dataset and then store them in a single structure.
When I go from Haskell back to imperative land I find myself greatly missing this ability. Sure I can make multiple hashmaps or trees or whatever but being able to stuff it all in one data structure is amazing.
One structure I built with them that is much more difficult with typical structures is a "block list" structure.
In this structure each block has a particular width and they're all stacked side by side.
I want to perform a query, "which box is at position X". So if my boxes are of widths 7,20,10, then the lookup for 2 yields the first box, the lookup for 12 yields the second, etc.
More interestingly, if add a new box between the second and third, the indices covered by the last box is increased.
With finger trees you use a sum monoid. This is easy. In other languages you have to roll your own structure either using a list (with o(n) lookup) or a tree with o(log n) lookup, but o(n) inserts (to translate the indices of future blocks)
You might enjoy a paper I’m a coauthor on which combines finger trees with B-trees to build a data structure for optimal updates to sliding windows: Optimal and General Out-of-Order Sliding-Window Aggregation, https://www.scott-a-s.com/files/vldb2019_fiba.pdf
Very interested in your idea. How does concurrent updates work with the augumented trees? I have been thinking about the same for a while something like CouchDB but segment aggregations (monoid) augumented so we can do interval queries over time too. But the only thing bothering is augumented trees are notorious of contention on concurrent updates. Do you have any ideas on merging back if we have multiple versions of augumented trees.
You can do this with any tree, finger or otherwise, and the big-O stuff applies as long as the tree is within a constant factor of balanced. For some bizarre reason, though, the concept of caching a monoid in each node doesn’t seem to have spread to the standard libraries of most languages. It’s a pity, since that would be incredibly useful.
A variation on 32 wide Bagwell hashed tries last time I looked. Scala was too. Those are much more annoying to implement without garbage collection fwiw.
When I go from Haskell back to imperative land I find myself greatly missing this ability. Sure I can make multiple hashmaps or trees or whatever but being able to stuff it all in one data structure is amazing.
One structure I built with them that is much more difficult with typical structures is a "block list" structure.
In this structure each block has a particular width and they're all stacked side by side.
I want to perform a query, "which box is at position X". So if my boxes are of widths 7,20,10, then the lookup for 2 yields the first box, the lookup for 12 yields the second, etc.
More interestingly, if add a new box between the second and third, the indices covered by the last box is increased.
With finger trees you use a sum monoid. This is easy. In other languages you have to roll your own structure either using a list (with o(n) lookup) or a tree with o(log n) lookup, but o(n) inserts (to translate the indices of future blocks)
https://andrew.gibiansky.com/blog/haskell/finger-trees/