Scala implicit conversion of container nested types

Question

Consider the following example:

case class A()

case class B()

object Conversions {
  implicit def aToB(a: A): B = B()

  implicit def convert[U, T](seq: Seq[U])(implicit converter: U => T): Seq[T] = {
    seq.map(converter)
  }
}

object Main {
  import Conversions._

  def main(args: Array[String]): Unit = {

    val sa = Seq(A())

    def example(): Seq[B] = sa
  }
}

This example won't compile by scala compiler for version 2.11.8. I do compilation with IntelliJ Idea, but actually idea don't produce error on the fly and shows that implicit is used for conversion: Screenshot from Intellij Idea
To workaround this issue I've used the approach described here: "Scala: Making implicit conversion A->B work for Option[A] -> Option[B]"
My code started to look as follow:

case class A()

case class B()

object Conversions {
  implicit def aToB(a: A): B = B()

  trait ContainerFunctor[Container[_]] {
    def map[A, B](container: Container[A], f: A => B): Container[B]
  }

  implicit object SeqFunctor extends ContainerFunctor[Seq] {
    override def map[A, B](container: Seq[A], f: (A) => B): Seq[B] = {
      Option(container).map(_.map(f)).getOrElse(Seq.empty[B])
    }
  }

  implicit def functorConvert[F[_], A, B](x: F[A])(implicit f: A => B, functor: ContainerFunctor[F]): F[B] = functor.map(x, f)
}

object Main {

  import Conversions._

  def main(args: Array[String]): Unit = {

    val sa = Seq(A())

    def example(): Seq[B] = sa
  }
}

This code compiles well and works as needed.

My questions are:
Why the first approach fails to compile?
Is this somehow related to type erasure and if yes, how usage of Functor helps with it?
How compiler resolves implicits for both of this cases?

Answer 1

Why the first approach fails to compile?

I've opened a bug for this issue.

This seems like a compiler quirk in implicit search. Since you're providing the convert method which converts Seq[A] => Seq[B], the compiler isn't able to properly align the types. This is the output of compiling with Ytyper-debug:

|    [search #3] start `[U, T](seq: Seq[U])(implicit converter: U => T)Seq[T]` inferring type T, searching for adaptation to pt=A => T (silent: method example in Test) implicits disabled
|    [search #3] considering aToB
|    |-- { ((a: A) => Conversions.aToB(a)) } : pt=A => ? EXPRmode (silent: method example in Test) implicits disabled
|    |    |-- ((a: A) => Conversions.aToB(a)) : pt=A => ? EXPRmode (silent: method example in Test) implicits disabled
|    |    |    |-- Conversions.aToB(a) EXPRmode (silent: value $anonfun in Test) implicits disabled
|    |    |    |    |-- Conversions.aToB BYVALmode-EXPRmode-FUNmode-POLYmode (silent: value $anonfun in Test) implicits disabled
|    |    |    |    |    \-> (a: A)B
|    |    |    |    |-- a : pt=A BYVALmode-EXPRmode (silent: value $anonfun in Test) implicits disabled
|    |    |    |    |    \-> A
|    |    |    |    \-> B
|    |    |    \-> A => B
|    |    \-> A => B
|    [adapt] aToB adapted to { ((a: A) => Conversions.aToB(a)) } based on pt A => T
|    [search #3] solve tvars=?T, tvars.constr= >: B
|    solving for (T: ?T)
|    [search #3] success inferred value of type A => =?B is SearchResult({
|      ((a: A) => Conversions.aToB(a))
|    }, TreeTypeSubstituter(List(type T),List(B)))
|    solving for (A: ?A)
|    solving for (A: ?A)
|    solving for (A: ?A)
|    solving for (A: ?A)
|    [search #3] considering $conforms
|    solving for (A: ?A)
|    [adapt] $conforms adapted to [A]=> <:<[A,A] based on pt A => T
|    [search #3] solve tvars=?T, tvars.constr= >: A
|    solving for (T: ?T)
|    [search #3] success inferred value of type A => =?A is SearchResult(scala.Predef.$conforms[A], TreeTypeSubstituter(List(type T),List(A)))

It seems like the search #3 is trying to adapt conforms (<:<) which takes the entire implicit search from A => B to A => A. If I compile with the -Yno-predef, the implicit conversion succeeds:

|    |    |-- [U, T](seq: Seq[U])(implicit converter: U => T)Seq[T] : pt=Seq[B] EXPRmode (silent: method example in Test) implicits disabled
|    |    |    [search #4] start `[U, T](seq: Seq[U])(implicit converter: U => T)Seq[T]`, searching for adaptation to pt=A => B (silent: method example in Test) implicits disabled
|    |    |    [search #4] considering aToB
|    |    |    |-- { ((a: A) => Conversions.aToB(a)) } : pt=A => B EXPRmode (silent: method example in Test) implicits disabled
|    |    |    |    |-- ((a: A) => Conversions.aToB(a)) : pt=A => B EXPRmode (silent: method example in Test) implicits disabled
|    |    |    |    |    |-- Conversions.aToB(a) : pt=B EXPRmode (silent: value $anonfun in Test) implicits disabled
|    |    |    |    |    |    |-- Conversions.aToB BYVALmode-EXPRmode-FUNmode-POLYmode (silent: value $anonfun in Test) implicits disabled
|    |    |    |    |    |    |    \-> (a: A)B
|    |    |    |    |    |    |-- a : pt=A BYVALmode-EXPRmode (silent: value $anonfun in Test) implicits disabled
|    |    |    |    |    |    |    \-> A
|    |    |    |    |    |    \-> B
|    |    |    |    |    \-> A => B
|    |    |    |    \-> A => B
|    |    |    [adapt] aToB adapted to { ((a: A) => Conversions.aToB(a)) } based on pt A => B
|    |    |    [search #4] success inferred value of type A => B is SearchResult({
|    |    |      ((a: A) => Conversions.aToB(a))
|    |    |    }, )
|    |    |    |-- [U, T](seq: Seq[U])(implicit converter: U => T)Seq[T] : pt=Seq[B] EXPRmode (silent: method example in Test) implicits disabled
|    |    |    |    \-> Seq[B]
|    |    |    [adapt] [U, T](seq: Seq[U])(implicit converter: U => T)Seq[T] adapted to [U, T](seq: Seq[U])(implicit converter: U => T)Seq[T] based on pt Seq[B]
|    |    |    \-> Seq[B]
|    |    [adapt] Seq[A] adapted to [U, T](seq: Seq[U])(implicit converter: U => T)Seq[T] based on pt Seq[B]
|    |    \-> Seq[B]
|    \-> [def example] ()Seq[B]

Is this somehow related to type erasure and if yes, how usage of Functor helps with it?

The second example works because you're now laying out explicitly how to map a Seq[A] into a Seq[B] by using the Functor type class and thus when the compiler sees a Seq[A], it has an implicit to convert it to Seq[B]:

def example(): Seq[B] = Conversions.functorConvert[Seq, A, B](sa)({
        ((a: A) => Conversions.aToB(a))
}, Conversions.SeqFunctor);

Note you require both a conversion from A => B, and a Functor[Seq] to be able to map over all As to convert them to Bs, which is what it does using conversions.aToB.