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

[Victor Nazarov]

On Sat, Feb 19, 2011 at 4:38 AM, Johan Tibell <johan.tibell at gmail.com> wrote:
> Hi all,
>
> I am delighted to announce the release of preview versions of two new packages:
>
> unordered-containers 0.1
> Efficient hashing-based container types.
> http://hackage.haskell.org/package/unordered-containers
>
> hashable 1.1
> Efficient hashing of common types.
> http://hackage.haskell.org/package/hashable
>
> These packages address a need for faster container types in Haskell,
> especially for string types like ByteString and Text. The package
> achieves better performance by using hashing and a Patricia trie (also
> known as a radix tree), instead of a balanced tree, in its
> implementation.
>
> The provided HashMap type is three times faster than Data.Map for
> lookups and twice as fast for inserts, for all key types I've tried,
> including ByteString, String, and Int.
>
> I'm calling this a preview release, even though the code hash been
> well tested both for correctness and performance, as the API is quite
> basic and doesn't provide a HashSet type yet. One thing you'll notice
> is that the API is split into a value-strict and a value-lazy version,
> making it easier to use in a strict setting.
>
> If you want to contribute, please get copies of the source trees from here:
>
> * git clone https://github.com/tibbe/unordered-containers.git
> * git clone https://github.com/tibbe/hashable.git
>
> Alternatively, just fork the projects on GitHub:
>
> http://github.com/tibbe
>
> As I mentioned in my talk on hashing-based containers earlier this
> week, I'm working on an even faster version, based on hash-array
> mapped tries, but it won't be ready until GHC 7.2.
>
> Johan
>

What about making Hashable subclass of Eq

    class Eq a => Hashable a where

I think it's is obvious from Hasable class properties that some kind
of equality is needed and I think it will reduce type class
constraints in actual hash table implementation in
unordered-containers package.

Also I think that value of hash functions is obviously a Monoid and it
will be convenient to have Monoid instance

    newtype Hash = Hash Int
    instance Monoid Hash where
      mempty = Hash 0
      Hash a `mappend` Hash b = Hash (a `combine` b)

    class Eq a => Hashable a where
        hash :: a -> Hash
        hashWithSalt :: Hash -> a -> Hash

        hashWithSalt salt x = salt `mappend` hash x

-- 
Victor Nazarov