RFC: Adding a Hashable type class and HashMap/HashSet data
types to HP
Maciej Piechotka
uzytkownik2 at gmail.com
Fri Nov 26 19:28:09 EST 2010
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
More information about the Libraries
mailing list