Add higher kinded versions of `Eq`, `Order`, `Show`

[kubukoz]

...or at least some of them.

Reasoning: in #2300, I was trying to implement Eq[Cofree[S, A]] using implicit instances of Eq[S[Cofree[S, A]]] and Eq[A]. That would look like this:

implicit def catsFreeEqForCofree[S[_], A : Eq](implicit S: Eq[S[Cofree[S, A]]]): Eq[Cofree[S, A]] = new Eq[Cofree[S, A]] {
  override def eqv(x: Cofree[S, A], y: Cofree[S, A]): Boolean = Eq[A].eqv(x.head, y.head) && S.eqv(x.tailForced, y.tailForced)
}

However, any attempt at e.g. Eq[Cofree[List, Int]] will fail compilation due to an diverging implicit expansion - and it makes sense, since Eq[List[Cofree[List, A]]] needs an Eq[Cofree[List, A]], which is exactly what we're trying to construct.

The same situation will happen if someone tries to implement Order or Show.

Since we don't have a mechanism for shapeless-style lazy implicits, it doesn't seem possible to implement such instances without changes outside of Cofree.

One solution to this problem that I see is creating a higher kinded variant of Eq, similar to Semigroup / SemigroupK:

trait EqK[F[_]] { self =>
  def eqv[A : Eq](x: F[A], y: F[A]): Boolean

  def algebra[A : Eq]: Eq[F[A]] = new Eq[F[A]] {
    def eqv(x: F[A], y: F[A]): Boolean = self.eqv(x, y)(Eq[A])
  }
}

I believe that's Eq1 in Haskell: http://hackage.haskell.org/package/base-4.11.1.0/docs/Data-Functor-Classes.html#g:2

Having that, we might remove the current instances of Eq for higher kinded types like Option:

implicit def catsKernelStdEqForOption[A: Eq]: Eq[Option[A]] = ...

and replace them with instances of EqK:

implicit val catsKernelStdEqKForOption: EqK[Option] = ...

To make it possible to seamlessly get an Eq[Option[A]] for an A : Eq, we could add a derivation method:

implicit def eqFromEqK[F[_] : EqK, A : Eq]: Eq[F[A]] = EqK[F].algebra[A]

or, alternatively (and this would probably make it possible to keep binary compatibility), add instances of EqK alongside the old instances, and make the old instances use the implementations from EqK instances underneath (the old instances could be removed later, at a point when we can break compatibility).

The same thing could happen to Order and Show.

Another idea would be to introduce lazy implicits to Cats.

[kubukoz]

Initial discussion about the old EqK and drawbacks:

https://gitter.im/typelevel/cats?at=5b33fa45479ca26689854ba6

Looks like the reason to remove EqK originally was to loosen the requirements for tests - in places where an EqK[F] and an Eq[A] was required, the removal made it just a requirement on Eq[F[A]].

I believe we could leave these tests unchanged and still have EqK in the library.

This affects instances for any fixpoint data type like Cofree. An alternative solution is what matryoshka did: simulating lazy implicits using Delay[Eq, F] -

https://github.com/slamdata/matryoshka/blob/2233e287fab4ab8cd509663f2f384822af2ff32c/core/shared/src/main/scala/matryoshka/Delay.scala#L24

[kubukoz]

Also, maybe we don't need to support binary type constructors as well - the usecase in which I'm hitting this wall is S[_], so it can't be a type of an arbitrary kind. If S[_] were Either[Int, ?] or Either[?, Int], we should be able to define an EqK for both of these variants.

[djspiewak]

I'm relatively certain Defer solves this problem.

Edit: No it doesn't. I was confused. Delay from Matryoshka does solve it, but Defer as referenced in #2279 does not.

[kubukoz]

I prepared a POC for solving it with Delay (which has its own problems), for anyone interested in the issue: https://github.com/typelevel/cats/pull/2316

[xuwei-k]

FYI https://github.com/typelevel/shapeless-contrib/pull/9/files

[kubukoz]

I don't like the idea that having Eq for Cofree would require another dependency, let alone shapeless (if we were to implement instances for cats simpilar to what you did in that PR for scalaz)... but if there's a decision that we don't want to add Delay in some shape of form, that might be the best option indeed

[xuwei-k]

https://gist.github.com/xuwei-k/118230f49c6522bddfcf1ef137c11945 byname implicit (since Scala 2.13)

[milessabin]

You definitely don't want to be using Lazy at this point ...

[kubukoz]

guess we'll just have to wait for 2.13 ;)

[kubukoz]

Closing, I suggest to wait with the original issue until 2.13 is available, then we can use lazy implicits to add an instance to cats. I'll post more in the issue.