Add Hash typeclasses to cats

[ctongfei]

Hash is a special case of Eq.
These captures the Java default method hashCode and clone (in Cloneable), just like Eq for equals and Show for toString.

Example implementation:
https://github.com/ctongfei/poly-collection/blob/master/core/src/main/scala/poly/collection/typeclass/Hash.scala#L12
https://github.com/ctongfei/poly-collection/blob/master/core/src/main/scala/poly/collection/typeclass/Cloning.scala#L11

[johnynek]

-1 on Clone. All should be immutable, so Clone should be a no-op. +1 on Hash extending Eq.

…

On Fri, May 19, 2017 at 11:26 AM Tongfei Chen ***@***.***> wrote: Hash is a special case of Eq. These captures the Java default method hashCode and clone (in Cloneable), just like Eq for equals and Show for toString. Example implementation: https://github.com/ctongfei/poly-collection/blob/master/core/src/main/scala/poly/collection/typeclass/Hash.scala#L12 https://github.com/ctongfei/poly-collection/blob/master/core/src/main/scala/poly/collection/typeclass/Cloning.scala#L11 — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#1690>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAEJdmckRku9NOM6G7wGanJk965B4W6Iks5r7gj6gaJpZM4NhCMq> .

[adelbertc]

Related: typelevel/algebra#38

[ctongfei]

OK. But Hash and/or HashFamily (for BloomFilter/CountMinSketch/etc.) should be added

[djspiewak]

Ditto @johnynek. Hash would be quite useful. Clone not so much.

[kailuowang]

Thanks for the suggestion @ctongfei . Also 👍 on adding Hash. A PR would be more than welcome.

[ctongfei]

@kailuowang Thanks. I'll open a PR.

[ctongfei]

I propose a HashOrder[A] typeclass that extends both Hash[A] and Order[A].

Two reasons:

• If we give an implicit instance of Hash[A] for the common As in cats.kernel.instances, every time when we require an Eq[A] we would be in a situation where implicit objects are ambiguous: There exists both a Hash[A] and an Order[A] instance. If all of those instances in cats.kernel.instances are instances of HashOrder this problem cease to exist.
• This solves the diamond inheritance problem, especially on the method on[B](f: B => A): Hash[B]. In HashOrder we can define an overriding on that overrides both the Hash and the Order on methods.

[johnynek]

this isn't uncommon in cats (see previous discussions #1210).

i think the best we have to offer is implicit ho: Hash[A] with Order[A] has been proposed, which means you don't have the ambiguity, or explicitly passing the Eq to break the ambiguity manually.

I personally don't like making the full cross product of possible compositions reified in types. So, I would be -1 on HashOrder. Lastly, I can't see any relationship between Hash and Order unlike Hash and Eq.

[ctongfei]

@johnynek So for each typeclass instance we provide, we will override the on method manually. Is that the proposed solution?

[johnynek]

Can you sketch the case you are worried about?

I see the issue with on returning either Hash or Order. It's not ideal. I guess you would just indeed override:

scala> trait Foo { def bar: Foo = this }
defined trait Foo

scala> trait Baz { def bar: Baz = this }
defined trait Baz

scala> new Foo with Bar { }
<console>:13: error: not found: type Bar
       new Foo with Bar { }
                    ^

scala> new Foo with Baz { }
<console>:14: error: <$anon: Foo with Baz> inherits conflicting members:
  method bar in trait Foo of type => Foo  and
  method bar in trait Baz of type => Baz
(Note: this can be resolved by declaring an override in <$anon: Foo with Baz>.)
       new Foo with Baz { }
           ^

scala> new Foo with Baz { override def bar: Foo with Baz = this }
res2: Foo with Baz{def bar: Foo with Baz} = $anon$1@8d7b252

I see your concern since basically everything has Hash and so that means everything with Order also will suffer if we do import cats.implicits._. It will basically render Eq unusable at that point, I guess.

We could use the alternate encoding for Hash:

trait Hash[A] {
  def eqInstance: Eq[A]
  def hash(a: A): Int
}

so we don't extend, but point to the instance. This would make Hash an odd duck in cats.

This keeps coming up.

[ctongfei]

I would say the better route is do manual overriding on for every typeclass instance.
Or another option is not to implement the Hash#on method. Instead, use Hash$.by[A, B](f: A=>B)(implicit ev: Hash[B]): Hash[A].

Hash extends Eq has good intuitions: every map requires that there is an Eq on the type of keys: ListMap only requires Eq, TreeMap requires Order, whereas HashMap requires Hash. Very neat.

[ctongfei]

I drafted a pull request #1712 .