Re: RFC: Adding a Hashable type class and HashMap/HashSet data types to HP

On 26 Nov 2010, at 23:14, Johan Tibell wrote:

On Fri, Nov 26, 2010 at 8:35 PM, Bryan O'Sullivan wrote:

...

I think so. The purpose of having the Hashable typeclass is so that the universe of typed values that we can hash is open.

I don't disagree that being able to hash everything is nice, but I don't think it's crucial. My main interest in having a Hashable type class is so we can have containers that can be keyed by hashable things, for the types where this make sense (e.g. string like types where comparison is expensive.) If all that a Hashable type class would give me is the ability to store ByteStrings and Texts in a HashMap, that alone would be enough motivation for having one in my opinion.

I am probably showing my ignorance here, but I am puzzled as to how a hash value of type Word32 helps anyone. When I learnt CS a long time ago (and I even implemented a Hashable class for Haskell in the early 1990s), a hash value was always used as the index into a constant-time lookup table. I certainly don't want tables of size 2^32 in any programs I write, even if I do have 12G of memory in my machine. Way back when, my Hashable method needed to know what size of table you wanted in order to generate the hash. Of course, you could resize tables upwards if required too. So I'm imagining you have a different idea in mind for how to store a HashMap? Will it be a rebalancing tree structure, using the ordering on Hashes as keys? This changes the computational complexity of both storage and lookup, and I begin to wonder whether you will gain any performance ultimately. Regards, Malcolm