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