Allow implicit parameters of polymorphic function types to behave like implicit parameters

[LukaJCB]

Polymorphic function types are a fantastic feature and without a doubt one of the features I'm most excited about in Dotty. They currently have a few restrictions, that hopefully we could relax in time for the full release of Scala 3.

Motivation

Sometimes when working with type classes of you run into issues where you e.g. want to say that a given type constructor can be compared for equality given that its contents are. A good example for this is the following issue in cats: typelevel/cats#2308

Basically what we want to say that we can have an instance of Eq[Cofree[S, A] whenever S[_] itself also has an Eq instance for any A that in turn also has an Eq instance. One solution to this problem is to add a higher kinded version of Eq.
In Haskell this can be found as Eq1 here (along with Ord1, Show1, etc.)
https://hackage.haskell.org/package/transformers-0.4.2.0/docs/Data-Functor-Classes.html

The problem with this of course is that now, you start to have to duplicate most of the hierarchy in this fashion, even though they don't really convey any different meaning.

Ideally given polymorphic functions, we should be able to express Eq1 as a polymorphic function type in the following way:

trait Eq[A] {
  def (x: A) eqv (y: A): Boolean 
}

type Eq1[F[_]] = [A] => given Eq[A] => Eq[F[A]]

In my opinion, this reads quite nicely as well, since it basically says an Eq1 of a type constructor is an Eq[F[A]] for any A, given Eq[A].

This problem props up in a bunch of different type classes as well, see for example Arbitrary1 or Monoid1.

Another example of something like this would be SemigroupK in cats, which is a universally quantified semigroup which would look like this:

trait Semigroup[A] {
  def (x: A) combine (y: A): A
}

type SemigroupK[F[_]] = [A] => () => Semigroup[F[A]]

Furthermore there are some other really neat use cases that this would enable, including the ability to unite the bifunctor and monofunctor styles in a single type class hierarchy in a future version of cats-effect. (I will try to write more on this in a later post)

Problems

As far as I can see there are two problems that hinder this from working well.

1. Polymorphic function types as implicit arguments don't behave like regular implicit params

Say we have the Eq1 definition from above, my expectation would be that if I use a function with an abstract F[_]: Eq1, that I should be able to use eqv on any F[A] given Eq[A].
Instead this is what happens:

def foo[F[_]: Eq1](x: F[Int], y: F[Int]) =
  x.eqv(y)
| ^^^^^
| value eqv is not a member of F[Int] - did you mean x.==?
|
| where:    F is a type in method foo with bounds <: [_$30] => Any

We can get it around this by calling the implicit manually, but it's not quite ergonomic:

// this works
def foo[F[_]: Eq1](x: F[Int], y: F[Int]) =
  implicitly[Eq1[F]][Int].eqv(x)(y)

Ideally it would pull in something like an implicit def ev[A: Eq]: Eq[F[A]] into scope to make it possible to just type x.eqv(y).

2. Construction of these type aliases is fairly difficult (or impossible)

Ideally since something like Eq1 is just a type alias, I wouldn't need to define anything extra.
So if we had an instance like this:

implicit def eqOption[A: Eq]: Eq[Option[A]] = new Eq[Option[A]] {
  def (x: Option[A]) eqv (y: Option[A]) = ???
}

we should be able call the foo method from above with Option:. This is what happens instead.

foo(Option(3), Option(4))
|                       ^
|no implicit argument of type Eq1[Option] was found for parameter evidence$10 of method fooo

I've tried to get around this by making eqOption non-implicit and defining an implicit instance of Eq1 instead, but could not get them to unify:

def eqOption[A: Eq]: Eq[Option[A]] = new Eq[Option[A]] {
  def (x: Option[A]) eqv (y: Option[A]) = x == y
}

implicit def eq1Option: Eq1[Option] = eqOption
|                                     ^^^^^^^^
|                                      Found:    Eq[Option[Int]]
|                                      Required: Eq1[Option]

Maybe there's something else you can do, but ideally it should just work :)

/cc @smarter

[LukaJCB]

Also, I wrote a quick gist on how this could really help with future versions of cats-effect and bifunctor tagless final code:
https://gist.github.com/LukaJCB/4440ad2bc351f1d8e98601f247ec4c02

[neko-kai]

Related/duplicate: #50