scala overloading resolution differences between function calls and implicit search

Question

There is a difference in the way the scala 2.13.3 compiler determines which overloaded function to call compared to which overloaded implicit to pick.

object Thing {
    trait A;
    trait B extends A;
    trait C extends A;

    def f(a: A): String = "A"
    def f(b: B): String = "B"
    def f(c: C): String = "C"

    implicit val a: A = new A {};
    implicit val b: B = new B {};
    implicit val c: C = new C {};
}
import Thing._

scala> f(new B{})
val res1: String = B

scala> implicitly[B]
val res2: Thing.B = Thing$$anon$2@2f64f99f

scala> f(new A{})
val res3: String = A

scala> implicitly[A]
                 ^
       error: ambiguous implicit values:
        both value b in object Thing of type Thing.B
        and value c in object Thing of type Thing.C
        match expected type Thing.A

As we can see, the overload resolution worked for the function call but not for the implicit pick. Why isn't the implicit offered by val a be chosen as occurs with function calls? If the callers ask for an instance of A why the compilers considers instances of B and C when an instance of A is in scope. There would be no ambiguity if the resolution logic were the same as for function calls.

Edit 2: The Edit 1 was removed because the assertion I wrote there was wrong.

In response to the comments I added another test to see what happens when the implicit val c: C is removed. In that case the compiler don't complains and picks implicit val b: B despite the caller asked for an instance of A.

object Thing {
    trait A { def name = 'A' };
    trait B extends A { def name = 'B' };
    trait C extends A { def name = 'C' };

    def f(a: A): String = "A"
    def f(b: B): String = "B"

    implicit val a: A = new A {};
    implicit val b: B = new B {};
}
import Thing._

scala> f(new A{})
val res0: String = A

scala> implicitly[A].name
val res3: Char = B

So, the overloading resolution of implicit differs from function calls more than I expected. Anyway, I still don't find a reason why the designers of scala decided to apply a different resolution logic for function and implicit overloading. (Edit: Later noticed why).

Let's see what happens in a real world example. Suppose we are doing a Json parser that converts a Json string directly to scala Abstract data types, and we want it to support many standard collections. The snippet in charge of parsing the iterable collections would be something like this:

trait Parser[+A] {
    def parse(input: Input): ParseResult;
    ///// many combinators here
}

implicit def summonParser[T](implicit parserT: Parser[T]) = parserT;

/** @tparam IC iterator type constructor
 * @tparam E element's type */
implicit def iterableParser[IC[E] <: Iterable[E], E](
    implicit
    parserE: Parser[E],
    factory: IterableFactory[IC]
): Parser[IC[E]] = '[' ~> skipSpaces ~> (parserE <~ skipSpaces).repSepGen(coma <~ skipSpaces, factory.newBuilder[E]) <~ skipSpaces <~ ']';

Which requires a Parser[E] for the elements and a IterableFactory[IC] to construct the collection specified by the type parameters. So, we have to put in implicit scope an instance of IterableFactory for every collection type we want to support.

implicit val iterableFactory: IterableFactory[Iterable] = Iterable
implicit val setFactory: IterableFactory[Set] = Set
implicit val listFactory: IterableFactory[List] = List

With the current implicit resolution logic implemented by the scala compiler, this snippet works fine for Set and List, but not for Iterable.

scala> def parserInt: Parser[Int] = ??? 
def parserInt: read.Parser[Int]

scala> Parser[List[Int]]
val res0: read.Parser[List[Int]] = read.Parser$$anonfun$pursue$3@3958db82

scala> Parser[Vector[Int]]
val res1: read.Parser[Vector[Int]] = read.Parser$$anonfun$pursue$3@648f48d3

scala> Parser[Iterable[Int]]
             ^
       error: could not find implicit value for parameter parserT: read.Parser[Iterable[Int]]

And the reason is:

scala> implicitly[IterableFactory[Iterable]]
                 ^
error: ambiguous implicit values:
both value listFactory in object IterableParser of type scala.collection.IterableFactory[List]
 and value vectorFactory in object IterableParser of type scala.collection.IterableFactory[Vector]
match expected type scala.collection.IterableFactory[Iterable]

On the contrary, if the overloading resolution logic of implicits was like the one for function calls, this would work fine.

Edit 3: After many many coffees I noticed that, contrary to what I said above, there is no difference between the way the compiler decides which overloaded functions to call and which overloaded implicit to pick.

In the case of function call: from all the functions overloads such that the type of the argument is asignable to the type of the parameter, the compiler chooses the one such that the function's parameter type is assignable to all the others. If no function satisfies that, a compilation error is thrown.

In the case of implicit pick up: from all the implicit in scope such that the type of the implicit is asignable to the asked type, the compiler chooses the one such that the declared type is asignable to all the others. If no implicit satisfies that, an compilation error is thrown.

My mistake was that I didn't notice the inversion of the assignability. Anyway, the resolution logic I proposed above (give me what I asked for) is not entirely wrong. It's solves the particular case I mentioned. But for most uses cases the logic implemented by the scala compiler (and, I suppose, all the other languages that support type classes) is better.

Answer 1

As explained in the Edit 3 section of the question, there are similitudes between the way the compiler decides which overloaded functions to call and which overloaded implicit to pick. In both cases the compiler does two steps:

1. Filters out all the alternatives that are not asignable.
2. From the remaining alternatives choses the most specific or complains if there is more than one.

In the case of the function call, the most specific alternative is the function with the most specific parameter type; and in the case of implicit pick is the instance with the most specific declared type.

But, if the logic in both cases were exactly the same, then why did the example of the question give different results? Because there is a difference: the assignability requirement that determines which alternatives pass the first step are oposite. In the case of the function call, after the first step remain the functions whose parameter type is more generic than the argument type; and in the case of implicit pick, remain the instances whose declared type is more specific than the asked type.

The above words are enough to answers the question itself but don't give a solution to the problem that motivated it, which is: How to force the compiler to pick the implicit instance whose declared type is exactly the same than the summoned type? And the answer is: wrapping the implicit instances inside a non variant wrapper.