Another common usage for Map is as a functional integer-indexed random access array. Once I implemented the standard algorithm for random shuffle of a list using Data.Map Int. It was much nicer than the STArray version, in my opinion. But when I tried switching to Data.IntMap, hoping to make it faster, I was devastatingly disappointed. Now I understand why.

A couple thoughts: If you're going to provide an isSingleton method, provide getSingleton :: IntMap m -> Maybe (Int, a) which is trivial based on the current implementation. For my TrieMap package, I've been working on my WordMap implementation herehttp://hackage.haskell.org/packages/archive/TrieMap/3.0.1/doc/html/src/Data-.... (Using Words as keys makes my life easier, and it doesn't take too much work to write a wrapper that provides an order-preserving bijection from Int to Word.) It provides O(1) size, but its design reflects my willingness to trade memory and code size for speed. ;) Louis Wasserman wasserman.louis@gmail.com http://profiles.google.com/wasserman.louis