Why is this implicit ambiguity behaviour happening?

Question

I have a typeclass Search, which has an instance Search[A] if we have a TypeClass1[A] or a TypeClass2[A] instance. With preference given to the 1 instance.

The following compiles:

trait TypeClass1[A]
trait TypeClass2[A]
trait Search[A]

object Search extends LPSearch {
  implicit def case1[A](implicit ev: TypeClass1[A]): Search[A] = null
}

trait LPSearch {
  implicit def case2[A](implicit ev: TypeClass2[A]): Search[A] = null
}

object Test {
  implicit val ev1: TypeClass1[Int] = null
  implicit val ev2: TypeClass2[Int] = null
  implicitly[Search[Int]]
}

This is as I would expect, the implicit search finds case1, finds ev1, and stops searching.

However, if we change TypeClass2 to have more structure, the implicit search stops working:

trait TypeClass1[A]
trait TypeClass2[M[_], A]
trait Search[A]

object Search extends LPSearch {
  // This is the same as before
  implicit def case1[A](implicit ev: TypeClass1[A]): Search[A] = null
}

trait LPSearch {
  implicit def case2[M[_], A](implicit ev: TypeClass2[M, A]): Search[M[A]] = null
}

object Test {
  implicit val ev1: TypeClass1[List[Int]] = null
  implicit val ev2: TypeClass2[List, Int] = null

  // Does not compile:
  implicitly[Search[List[Int]]]
}

Why does this last line not compile in the above example?

It fails with ambiguous implicit values, saying both case1 and case2 satisfy the condition.

Behaviour observed on scala 2.12.8 and 2.13.0

Egoist

Answer 1

Scala specification says:

If there are several eligible arguments which match the implicit parameter's type, a most specific one will be chosen using the rules of static overloading resolution.

https://www.scala-lang.org/files/archive/spec/2.13/07-implicits.html#implicit-parameters

The relative weight of an alternative A over an alternative B is a number from 0 to 2, defined as the sum of

• 1 if A is as specific as B, 0 otherwise, and
• 1 if A is defined in a class or object which is derived from the class or object defining B, 0 otherwise.

https://www.scala-lang.org/files/archive/spec/2.13/06-expressions.html#overloading-resolution

• case1 is defined in an object which is derived from the class (trait) defining case2 but not vice versa.

• case2 is as specific as case1 but not vice versa.

So relative weight of case1 over case2 is 1+0=1 and relative weight of case2 over case1 is 0+1=1. So it's ambiguity.

Error: ambiguous implicit values:
 both method case2 in trait LPSearch of type [M[_], A](implicit ev: App.TypeClass2[M,A])App.Search[M[A]]
 and method case1 in object Search of type [A](implicit ev: App.TypeClass1[A])App.Search[A]
 match expected type App.Search[List[Int]]
    implicitly[Search[List[Int]]]

In the second case there is no sense to use low-priority trait since if both implicits match expected type, case2 is preferred when they are defined in the same object. So try

object Search {
  implicit def case1[A](implicit ev: TypeClass1[A]): Search[A] = null
  implicit def case2[M[_], A](implicit ev: TypeClass2[M, A]): Search[M[A]] = null
}

Knickers

I see, that certainly explains the behaviour, thank you very much. What should I do though if I want case1 to be preferred? – Egoist

@Egoist Try to use shapeless.LowPriority. object Search { implicit def case1[A](implicit ev: TypeClass1[A]): Search[A] = null; implicit def case2[M[_], A](implicit ev: TypeClass2[M, A], lowPriority: LowPriority): Search[M[A]] = null } Also look at github.com/monix/implicitbox , github.com/milessabin/export-hook – Knickers

@Egoist Or you can use type class Not (there are standard shapeless.Refute, implicitbox.Not). object Search { implicit def case1[A](implicit ev: TypeClass1[A]): Search[A] = null; implicit def case2[M[_], A](implicit ev: TypeClass2[M, A], not: Not[TypeClass1[M[A]]]): Search[M[A]] = null } – Knickers