Dotty: Spurious Ambiguous Implicits

[adamgfraser]

Minimized code

trait Equal[-A]

object Equal {

  implicit def DeriveEqual[F[_]: DeriveEqual, A: Equal]: Equal[F[A]] =
    ???
}

trait Derive[F[_], Typeclass[_]]

type DeriveEqual[F[_]] = Derive[F, Equal]

def foo[F[-_]: DeriveEqual, A: Equal, B: Equal]: Boolean = {
  val _ = implicitly[Equal[F[A]]]
  false
}

Output

ambiguous implicit arguments of type Equal[F[A]] found for parameter ev of method implicitly in object DottyPredef.
I found:

    Equal.DeriveEqual[F, A](evidence$1, 
      /* ambiguous: both value evidence$3 and value evidence$2 match type Equal[A] */
        summon[Equal[A]]
    )

But both value evidence$3 and value evidence$2 match type Equal[A].

Expectation

I would have expected this to compile as it does on Scala 2. The only way to derive an Equal[F[A]] here is through having a DeriveEqual and an Equal[A]. The compiler seems to get that far but then confuses having the Equal[A] with the Equal[B].

[smarter]

The compiler seems to get that far but then confuses having the Equal[A] with the Equal[B]

What the compiler is saying is true, both of those implicits can fit, as demonstrated by the following code that compiles both with scalac and dotty:

trait Equal[-A]

object Equal {
  type DeriveEqual[F[_]] = Derive[F, Equal]

  implicit def DeriveEqual[F[_]: DeriveEqual, A: Equal]: Equal[F[A]] =
    ???
}

trait Derive[F[_], Typeclass[_]]

object Test {
  import Equal._

  def foo[F[-_], A, B](implicit de: DeriveEqual[F], eqA: Equal[A], eqB: Equal[B]): Boolean = {

    val x: Equal[F[A]] = DeriveEqual[F, Nothing](de, eqA)
    val y: Equal[F[A]] = DeriveEqual[F, Nothing](de, eqB) // OK because Equal and F are both contravariant
                                                          // so Equal[F[Nothing]] <: Equal[F[A]]

    false
  }
}

So I think Scala 2 is the one which is wrong here. The ambiguity can be avoided by replacing F[-_] by F[_] in foo.

[adamgfraser]

Agreed they can both fit, but isn't there a further issue of which one is more specific? if we have stringEqual and anyEqual they both fit when we need an Equal[String] but we want to return the stringEqual, which Dotty does. It seems in this case that the eqA value is more specific, though the two contravariant types do complicate things.

[smarter]

It seems in this case that the eqA value is more specific

Equal[A] and Equal[B] are not known to be related by subtyping in any way, so eqA isn't more or less specific than eqB. I see why you'd want that one intuitively but I can't think of any good rule that would make us chose it here.

[smarter]

By the way, do you have any concrete contravariant F for which you can come up with a Derive[F, Equal]? It's not clear to me that they exist, e.g. if I know how to compare Int for equality, that doesn't really help me compare Encoder[Int] for equality. More generally for a contravariant F, I'm never going to be able to get an A out of an F[A] by definition, so being able to compare two A for equality is irrelevant to figuring out how to compare two F[A].

[adamgfraser]

I think that is right. Equality for contravariant types is tricky in general. If the input type A can be enumerated then you can say that two F[A] values are equal if they produce the same outputs for all inputs. If they can't be enumerated you could at least try to test a subset of the values. But either way you need a notion of equality for whatever you are converting the A values into, not the A values. So I think this is a case where we too quickly took logic from the covariant case to the contravariant one. Thanks for the good thought!