Bringing the IntMap API up to par with the Map API

Evan Laforge qdunkan at
Fri Aug 6 13:44:11 EDT 2010

> Or there is the other alternative -- to drop these functions from
> Data.Map. These functions are usually not available in other languages
> and the implementation is essentially forced to store the size of the
> subtrees in the tree. That is convenient for Adams' balanced trees, but
> not for AVL trees, red-black trees, tries (IntMap) etc.

I don't Data.Map is supposed to be an interface, it's an
implementation.  I don't think there's anything wrong with a data
structure providing operations you can do efficiently in that data
structure, even if other data structures can't.  In fact, that's often
the point of having different data structures.

As to making IntMap a drop-in replacement, should it be?  If you want
to switch to IntMap for performance but need to do some things are
going to be inefficient with it, then you should probably either not
switch, or come up with a different way of doing things, right?

More information about the Libraries mailing list