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

[Malcolm Wallace]

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

> On Fri, Nov 26, 2010 at 8:35 PM, Bryan O'Sullivan  
> <bos at serpentine.com> 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