immutable HashSet/HashMap using Eq/Hash/Order

[johnynek]

Note the issue here:

https://github.com/twitter/algebird/pull/399#issuecomment-73473246

The problem comes that Array[T] does not have sane equals/compareTo even though it clearly could. Making an Equiv,Ordering instance in scala won't help, because Set does not use it.

It might be nice to have versions that could side step these pains.

[rklaehn]

You mean completely new versions of HashSet/HashMap/SortedMap that use typeclasses instead of relying on the equals/hashCode, which just does not work for many things such as arrays? Wouldn't this be out of scope for something like non/algebra?

I played around with something like this a few months ago. See https://github.com/rklaehn/abc/tree/master/core/src/main/scala/com/rklaehn/abc . I don't have hash-based collections yet, mostly because there is no hashing typeclass in spire.

[johnynek]

It's hard to say if it is out of scope or not. I definitely would not put it in the core, I guess.

[rklaehn]

Having even a basic Hash typeclass would be a precondition for writing hash-based collections such as HashSet and HashMap. I understand that there was some discussion regarding that?

[johnynek]

some. See #38. The problem here is what we want to do. Some cases need hash families. Some cases need 128 bits of hash (say hyperloglog on big data).

A simple Hash typeclass probably extends Eq, since the law is: (!eqv(a, b)) || hash(a) == hash(b), so we need an Eq to test a Hash.