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

[Maciej Piechotka]

On Fri, 2010-11-26 at 23:05 +0000, Thomas Schilling wrote:
> On 26 November 2010 17:18, Maciej Piechotka <uzytkownik2 at gmail.com> wrote:
> > On Thu, 2010-11-25 at 16:15 +0000, Thomas Schilling wrote:
> >> and for a data type with constructors C_1 .. C_n
> >>
> >>    2. hash (C_i x_i1 ... x_iN) = hash i <> hash x_i1 <> ... <> hash x_iN
> >>
> >> where <> is the hash combine function (probably (.))
> >>
> >
> > (.) seems to fail type-checking.
> >
> 
> Right, sorry, I was actually having a different type in mind.  Something like:
> 
>     newtype HashBuilder = HashBuilder { unHB :: Word -> Word }
>     class Hashable a where
>          addHash :: a -> HashBuilder
> 
> The argument would be the seed.  We'd then have:
> 
>     hash :: Hashable a => a -> Word
>     hash a = finaliseHash $ unHB (addHash a) seed
>        where
>          seed = 0xdeadbeef
>          finaliseHash x = ... -- some final mixing operation
> 
> As Bryan mentioned, though, this does not allow building hashes in
> parallel.  It would also hard-code the hash function.
> 

Possibly the autogenerated function would be:

hash (C_n x_1 x_2 ... x_n)
    = hash "C_n" <> hash x_1 <> hash x_2 <> ... <> hash x_n

where <> is function Word -> Word -> Word (like xor).

Regards

PS. As with list there is problem with hash "[]" and hash ":" possibly:

instance Hashable a => Hashable [a] where
    hash = foldl' (<>) 0xdeadbeef . map hash
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 836 bytes
Desc: This is a digitally signed message part
Url : http://www.haskell.org/pipermail/libraries/attachments/20101126/4c2210b8/attachment-0001.bin