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

[Maciej Piechotka]

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.

> Principle (1) may require to use some form of normalisation before
> applying principle (2), e.g., for Set, differently balanced trees
> should still produce the same hash.
> 
> Does this look reasonable?

For autogeneration - yes. However it may happen that for optimization &
special cases it is not correct. For example:

data ByteString = BS (ForeignPtr Word8) Int Int

I would expect that:

instance Hashable ByteString where
	hash = foldr' (\w h -> h <> hash w) (hash [])

rather then

instance Hashable ByteString where
	hash (BS f o l) = hash f <> hash f <> hash o <> hash l

I'm not sure what benefits have second principle - except forcing
'normalisation' which is not possible - either ForeignPtr is not
hashable and ByteString is not hashable as it requires IO or ForeignPtr
is hashable by pointer [not contents] so image of hash on bytestings
depends only on length alone if normalisation is applied (as ptr &
offset may vary).

Regards
-------------- 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/8e48bdb8/attachment.bin