Many years ago I implemented an augmented tree structure in C++. So while I was at the Functional Programming eXchange last week I decided to implement the structure in F#. FYI by augmentation I mean storing extra data at each node of the tree that will accelerate the later operations on the tree. In DB terms, augmentations are typically used include secondary key conditions in your tree query.
This is what I did:
- Take a balanced tree implementation off the web. I was thinking finger tree but then though better to start with a simpler implementation. I chose an AVL tree. (I may revert the code to a red and black tree to simplify).
- Add a node field to store the augmentation (a generic type)
- Refactor the code by replacing the call of the node constructor by a call to a function that will first build an augmentation and then call the node constructor
- Pass the generic augmentation "maker" function as argument to the function calls
Then I wrote a generic select like operation that uses augmentations. And finally a "general" map operation: it uses the augmentations to optimize its search, it only transforms nodes that have the selected property AND it allows nodes to be deleted.
There are still a few more things to do to wrap this code up but I again can only admire the speed at which one can write functional style.
I'd love to tell you why you want to have these types of data structures but not everything can be for free.