[Haskell-cafe] ANN: unordered-containers - a new, faster hashing-based containers library

Roman Leshchinskiy rl at cse.unsw.edu.au
Wed Feb 23 13:10:34 CET 2011

Johan Tibell wrote:
> I'm working on a patch that provides O(1) size right now. The trick is
> to define HashMap as:
> data HashMap k v = HM {-# UNPACK #-} !Int !(Tree k v)

Another possibility is:

data HashMap k v = HM Int !(Tree k v)

hashMap t = HM (treeSize t) t

That way size is O(n) on first use but O(1) afterwards. Then again, if
someone really needs this they can program it themselves. I've never
needed an O(1) size for maps.


More information about the Haskell-Cafe mailing list