Monday, March 21, 2011

Personalize your containers

When I was playing around with Scala I was disappointed with the limited operations available on the map container. It is nice to have the power of the for comprehension but if it only performs selects and maps the functionality has its limits.

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:
  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. I mistakenly gave F# another chance and 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 much wasted time I gave up AGAIN on using F# in any other way than a glorified ML language: API signatures are only based on functions.

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.

No comments: