Proposal: Add the unordered-containers package and the hashable package to the Haskell Platform

[Jan-Willem Maessen]

On Wed, Mar 20, 2013 at 6:02 AM, Gábor Lehel <illissius at gmail.com> wrote:

> Compatibility issues aside, is there any reason newtypes aren't a good
> solution here?
>

Well, the tricky bit is that there are really two distinct uses of hashing
in the field in general and under discussion here in particular.  The first
(which is the one that's important for unordered-containers and almost all
practical uses of hashing *within* a program) is to provide fast keys for
hash tables, where the hash function is backed by equality checks and the
like and is thus a question of performance rather than correctness.  For
this a reasonably good, but not necessarily cryptographically secure,
hashing method is more than sufficient.

The second is to summarize large quantities of data compactly in a way that
can't efficiently be forged.  This generally requires a lot more bits than
an Int will provide.

My feeling is that Hashable is pretty good for the first purpose, but not
actually great for the second one.  HashWithSalt is the right primitive for
Hashable primarily because it avoids a ton of problems with hash mixing
when you combine hashes for sub-pieces of your data, and because good hash
algorithms of both kinds are almost always specified over streams of bytes.

Indeed, cryptographic hashing arguably could exist comfortably just on
serialized byte sequences, though I personally find that view a little bit
limiting.

So I'd favor a view where Hashable is explicitly specified to be used for
the first purpose, and other libraries provide crypto-quality hashing.
 There's an unfortunate tendency on this and related threads to pretend
that we can get good cryptographic hashing out of Hashable – whereas it
just slows hashing down to the point where UnorderedSet no longer
outperforms Set while providing no actual security.

-Jan-Willem Maessen
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20130320/71f1dba5/attachment.htm>