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