Daniel Peebles wrote:

I like this idea. As I mentioned on IRC, I'd call the class Hash rather than Hashable

The crypto-api already uses the class "Hash" for cryptographic hashes. If you are talking about data to be hashed, and not the algorithm to do the hashing, then "Hashable" is both correct and unique.

I'm also with you on the Word return type. It may be less convenient but maybe this will be a tiny step towards the "great Word revolt" (in which all conceptually unsigned things in the prelude and standard libraries actually become unsigned) that I hope will occur sometime in the near future.

Whats next, making sure all bounded things don't flow over/under? Pfft. Data.Word.NonFlowing Cheers, Thomas

On Fri, Nov 19, 2010 at 10:48 AM, Gregory Collins wrote:

On Thu, Nov 18, 2010 at 11:05 PM, Johan Tibell wrote:

...

* A type class for things that can be hashed, Hashable.

class Hashable a where    hash :: a -> Word

BTW,

An issue that needs to be resolved is: "Where should this change go?" We have a couple of options:

 a) Bring http://hackage.haskell.org/package/hashable into the platform

 b) Put the module into base -- probably a -1 for political/logistical reasons

 c) Put it into containers -- probably a -1 because it would force a     containers dependency where there was no containers dependency before.

Right. Putting it into containers would force text/bytestring to depend on containers or vice versa, in order to provide instances. Base or a separate package are the only options I think. Johan

On Sat, Nov 20, 2010 at 3:53 PM, Maciej Piechotka wrote:

On Fri, 2010-11-19 at 10:48 +0100, Gregory Collins wrote:

...

On Thu, Nov 18, 2010 at 11:05 PM, Johan Tibell wrote:

...

* A type class for things that can be hashed, Hashable.

class Hashable a where    hash :: a -> Word

Shouldn't it be:

class Eq a => Hashable a where        hash :: a -> Word

Or is there useful case where we want to hash something but it cannot be member of Eq?

I can think of a few. Regardless, constraining the type class in this way doesn't really buy us anything. Johan

On Sat, Nov 20, 2010 at 02:53:03PM +0000, Maciej Piechotka wrote:

On Fri, 2010-11-19 at 10:48 +0100, Gregory Collins wrote:

...

On Thu, Nov 18, 2010 at 11:05 PM, Johan Tibell wrote:

An issue that needs to be resolved is: "Where should this change go?" We have a couple of options:

a) Bring http://hackage.haskell.org/package/hashable into the platform

b) Put the module into base -- probably a -1 for political/logistical reasons

I'd say base

I would suggest not putting it into base if it isn't necessary to do so. It's much easier to merge things later (if desired) than to split them apart, and base is already far too big. Thanks Ian

On 11/20/10 1:32 PM, Ian Lynagh wrote:

On Sat, Nov 20, 2010 at 02:53:03PM +0000, Maciej Piechotka wrote:

...

On Fri, 2010-11-19 at 10:48 +0100, Gregory Collins wrote:

...

On Thu, Nov 18, 2010 at 11:05 PM, Johan Tibell wrote:

An issue that needs to be resolved is: "Where should this change go?" We have a couple of options:

a) Bring http://hackage.haskell.org/package/hashable into the platform

b) Put the module into base -- probably a -1 for political/logistical reasons

I'd say base

I would suggest not putting it into base if it isn't necessary to do so. It's much easier to merge things later (if desired) than to split them apart, and base is already far too big.

+1. Especially given the recent trend towards breaking things out of base, moving this in is suspect. As folks have been moving towards base-4 we've been able to finally start getting rid of the slew of Cabal flags for figuring out when base does or does not include various libraries. Don't start inventing new ones :) -- Live well, ~wren

On 20 November 2010 19:26, Yitzchak Gale wrote:

Johan Tibell wrote:

...

* Instances of Hashable for common types, in particular ByteString and Text.

And of course, all of the numeric types, unit, and Bool, Maybe, and Either.

More interesting are Maybe, Either, lists, tuples, Data.Map, Data.Set, etc. These are far from trivial; I did some work on it for Python. If you think you can just do something fairly simple and reasonable and hope that it will have the right statistical properties, I promise you that it won't work.

Are you referring to the hash function or to the fact that you want structurally different types to map to different hashes? I.e., hash (Data.Binary.encode x) probably would lead to unintended collisions. E.g., isomorphic values might get the same hash, right?

On 25 November 2010 13:10, Yitzchak Gale wrote:

I wrote:

...

...

More interesting are Maybe, Either, lists, tuples, Data.Map, Data.Set, etc. These are far from trivial; I did some work on it for Python. If you think you can just do something fairly simple and reasonable and hope that it will have the right statistical properties, I promise you that it won't work.

Thomas Schilling wrote:

...

Are you referring to the hash function or to the fact that you want structurally different types to map to different hashes?

The former. In Python, where objects of varying types will be inserted into the same hash table, the latter is also important. But why should we care about that in Haskell? If people circumvent the type system by serializing before hashing, I don't think we can help them very much. Or perhaps I am misunderstanding you.

Right, murmurhash2 is a very good and well-tested hash function. There is currently a beta version version 3 because a weakness has been found for some cases ("repetitions of 4-byte patterns have a much higher chance of collision than expected"). I think if we base our hash function on Murmur3, we don't need to worry much about the rest. Regarding hashing of ADTs, I agree with you that hash () == hash False should be no problem. The general principles would be: 1. prop_hashEq x y = x == y ==> hash x == hash y 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 (.)) 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? Also, I'm fine with the return of hash being an architecture-specific Word type, but we also need variants with a known bit-width of the resulting hash. For example, a Word32 hash has way more collisions than a Word64 hash, and this is important for some applications. / Thomas -- Push the envelope. Watch it bend.

I wrote:

...

...

...

More interesting are Maybe, Either, lists, tuples, Data.Map, Data.Set, etc. These are far from trivial; I did some work on it for Python. If you think you can just do something fairly simple and reasonable and hope that it will have the right statistical properties, I promise you that it won't work.

Thomas Schilling wrote:

Right, murmurhash2 is a very good and well-tested hash function.

It's good for strings. So we can use it for String and Data.Text. But how about [Data.Map Data.Text (String, [(Int, Bool)])] or whatever. Do you have a hash function for that? When you have containers that can be used to build structures of arbitrary shape, writing a hash function that works in general is a hard problem. Were you thinking that you could serialize those things and then just use murmurhash on them? Try it, but my guess is it won't work well. Murmurhash is designed for strings, not for those things. It's not a cryptographic hash; it's designed to have good statistical properties for a certain very specific types of input. If you abuse it, you'll likely lose those good properties. The parameters for murmerhash were tweaked using keys that were English words, and very short strings of random bytes. There is no evidence it will work well with other kinds of keys. I'd be very happy to be proven wrong though. Regards, Yitz

I wrote:

...

Were you thinking that you could serialize those things and then just use murmurhash on them? Try it, but my guess is it won't work well. Murmurhash is designed for strings, not for those things. It's not a cryptographic hash; it's designed to have good statistical properties for a certain very specific types of input. If you abuse it, you'll likely lose those good properties. The parameters for murmerhash were tweaked using keys that were English words, and very short strings of random bytes. There is no evidence it will work well with other kinds of keys.

Thomas Schilling wrote:

Where did you get this from?

From experience developing hashes for container types.

 The criteria listed at http://code.google.com/p/smhasher/wiki/SMHasher all talk about arbitrary bytes.  MurmurHash is designed for arbitrary byte strings, not English words.  It is not a cryptographic hash, sure, but I can't see any evidence that it only works with text.

Never mind their claims, look at their test cases. What they tested ought to work well. What they didn't test may or may not work well, and almost certainly will behave badly at least some of the time. Any fast non-cryptographic hash will by necessarily have many kinds of input that will behave badly. The idea is to test across a large sampling of the kinds of keys that typify the input you expect and tweak the constants in the hash to avoid too many collisions in those cases. As far as I could see, they tested against English words, and against fairly short strings of random bytes. And for "random bytes", the technique they used to generate them is important; changing to a different pseudorandom generator sometimes changes the results significantly. Furthermore, a fast serialization of containers is non-random, so you will be exercising the hash in a specific way that has not been tested. It could be it will be good enough, or it could be you can tweak your serialization or add another thin layer of hashing to make it all work. Thanks, Yitz

On Thu, Nov 25, 2010 at 2:23 PM, Johan Tibell wrote:

Is this an interesting problem to optimize for?

I think so. The purpose of having the Hashable typeclass is so that the universe of typed values that we can hash is open. It thus behooves us to figure out how to do that safely. For instance, someone using the Hashable class should be able to figure out how to hash this: data HttpUrl = HttpUrl { urlScheme :: ByteString, urlHost :: ByteString, urlPort :: Int, urlPath :: ByteString, urlQuery :: Maybe ByteString } Using the Hashable class, I can see how to hash the individual elements of this, but not how to safely glue them together into a hash for the whole value. Over in the Java world, where they depend to an arguably ridiculous degree on hashing, we often see horror stories of some hash function having bad dispersal properties (or worse, equality and hashing not matching) and causing nasty knock-on performance effects due to too many values hashing to the same few numbers in the range. I notice that the Hashable class doesn't have a way to supply a seed. If it did, we could possibly chain the result of one hash as the seed of the next, allowing us to construct a complete hash in an obvious way (although introducing a possibly undesirable data dependency, making it difficult or impossible to hash a large structure in parallel).

On Fri, Nov 26, 2010 at 8:35 PM, Bryan O'Sullivan wrote:

I think so. The purpose of having the Hashable typeclass is so that the universe of typed values that we can hash is open.

I don't disagree that being able to hash everything is nice, but I don't think it's crucial. My main interest in having a Hashable type class is so we can have containers that can be keyed by hashable things, for the types where this make sense (e.g. string like types where comparison is expensive.) If all that a Hashable type class would give me is the ability to store ByteStrings and Texts in a HashMap, that alone would be enough motivation for having one in my opinion.

I notice that the Hashable class doesn't have a way to supply a seed. If it did, we could possibly chain the result of one hash as the seed of the next, allowing us to construct a complete hash in an obvious way (although introducing a possibly undesirable data dependency, making it difficult or impossible to hash a large structure in parallel).

Having a hashWith method that takes a seed sounds reasonable. I guess a hash algorithm that doesn't make use of a seed (are there any?) could just throw away the seed in the implementation of hashWith. Johan

On 26 Nov 2010, at 23:14, Johan Tibell wrote:

On Fri, Nov 26, 2010 at 8:35 PM, Bryan O'Sullivan wrote:

...

I think so. The purpose of having the Hashable typeclass is so that the universe of typed values that we can hash is open.

I don't disagree that being able to hash everything is nice, but I don't think it's crucial. My main interest in having a Hashable type class is so we can have containers that can be keyed by hashable things, for the types where this make sense (e.g. string like types where comparison is expensive.) If all that a Hashable type class would give me is the ability to store ByteStrings and Texts in a HashMap, that alone would be enough motivation for having one in my opinion.

I am probably showing my ignorance here, but I am puzzled as to how a hash value of type Word32 helps anyone. When I learnt CS a long time ago (and I even implemented a Hashable class for Haskell in the early 1990s), a hash value was always used as the index into a constant-time lookup table. I certainly don't want tables of size 2^32 in any programs I write, even if I do have 12G of memory in my machine. Way back when, my Hashable method needed to know what size of table you wanted in order to generate the hash. Of course, you could resize tables upwards if required too. So I'm imagining you have a different idea in mind for how to store a HashMap? Will it be a rebalancing tree structure, using the ordering on Hashes as keys? This changes the computational complexity of both storage and lookup, and I begin to wonder whether you will gain any performance ultimately. Regards, Malcolm

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

On Fri, 2010-11-26 at 23:05 +0000, Thomas Schilling wrote:

On 26 November 2010 17:18, Maciej Piechotka 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

On Fri, Nov 26, 2010 at 5:59 PM, Thomas Schilling wrote:

This is what I had in mind: https://gist.github.com/717475

Cute. Of course (<>) suggests that you use a Monoid instance instead and drop the special operator :-)