Personalize your containers (in F#)

Many years ago I implemented an augmented tree structure in C++. Inspired, 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:

1. 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).
2. Add a node field to store the augmentation (a generic type)
3. 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
4. Pass the generic augmentation "maker" function as argument to the function calls

On this last point I wasted much time. Initialy, I tried to encapsulate the "augmentation" api with abstract methods on one the the types. As all this code is polymorphic the compiler barfed with "would leave scope" and this type of error. After a bit too much time, I reverted to only define API signatures are with functions, no methods. (I understood later that this is mostly true for all languages: stick to functions/lambda constructions because they always scale). 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.