Of course, there's Data.HashMap.HashMap[1], which is just a Data.IntMap.{Lazy,Strict}.IntMap[2], whose "implementation is based on big-endian patricia trees".

Of course, there's Data.HashMap.HashMap[1], which is just a Data.IntMap.{Lazy,Strict}.IntMap[2], whose "implementation is based on big-endian patricia trees". > Many operations have a worst-case complexity of O(min(n,W)). This means that the operation can become linear in the number of elements with a maximum of W -- the number of bits in an Int (32 or 64). [1] http://hackage.haskell.org/packages/archive/hashmap/1.3.0.1/doc/html/Data-HashMap.html http://hackage.haskell.org/packages/archive/hashmap/1.3.0.1/... [2] http://hackage.haskell.org/packages/archive/containers/latest/doc/html/Data-IntMap.html http://hackage.haskell.org/packages/archive/containers/lates...