Why do we need the From type parameter in Scala's CanBuildFrom

Question

I am experimenting with a set of custom container functions and took inspiration from Scala's collections library with regard to the CanBuildFrom[-From, -Elem, -To] implicit parameter.

In Scala's collections, CanBuildFrom enables parametrization of the return type of functions like map. Internally the CanBuildFrom parameter is used like a factory: map applies it's first order function on it's input elements, feeds the result of each application into the CanBuildFrom parameter, and finally calls CanBuildFrom's result method which builds the final result of the map call.

In my understanding the -From type parameter of CanBuildFrom[-From, -Elem, -To] is only used in apply(from: From): Builder[Elem, To] which creates a Builder preinitialized with some elements. In my custom container functions I don't have that use case, so I created my own CanBuildFrom variant Factory[-Elem, +Target].

Now I can have a trait Mappable

trait Factory[-Elem, +Target] {
  def apply(elems: Traversable[Elem]): Target
  def apply(elem: Elem): Target = apply(Traversable(elem))
}

trait Mappable[A, Repr] {
  def traversable: Traversable[A]

  def map[B, That](f: A => B)(implicit factory: Factory[B, That]): That =
    factory(traversable.map(f))
}

and an implementation Container

object Container {
  implicit def elementFactory[A] = new Factory[A, Container[A]] {
    def apply(elems: Traversable[A]) = new Container(elems.toSeq)
  }
}

class Container[A](val elements: Seq[A]) extends Mappable[A, Container[A]] {
  def traversable = elements
}

Unfortunately though, a call to map

object TestApp extends App {
  val c = new Container(Seq(1, 2, 3, 4, 5))
  val mapped = c.map { x => 2 * x }
}

yields an error message not enough arguments for method map: (implicit factory: tests.Factory[Int,That])That. Unspecified value parameter factory . The error goes away when I add an explicit import import Container._ or when I explicitly specify the expected return type val mapped: Container[Int] = c.map { x => 2 * x }

All of these "workarounds" become unnecessary when I add an unused third type parameter to Factory

trait Factory[-Source, -Elem, +Target] {
  def apply(elems: Traversable[Elem]): Target
  def apply(elem: Elem): Target = apply(Traversable(elem))
}

trait Mappable[A, Repr] {
  def traversable: Traversable[A]

  def map[B, That](f: A => B)(implicit factory: Factory[Repr, B, That]): That =
    factory(traversable.map(f))
}

and change the implicit definition in Container

object Container {
  implicit def elementFactory[A, B] = new Factory[Container[A], B, Container[B]] {
    def apply(elems: Traversable[A]) = new Container(elems.toSeq)
  }
}

So finally my question: Why is the seemingly unused -Source type parameter necessary to resolve the implicit?

And as an additional meta question: How do you solve these kinds of problems if you don't have a working implementation (the collection library) as a template?

Clarification

It might be helpful to explain why I thought the implicit resolution should work without the additional -Source type parameter.

According to this doc entry on implicit resolution, implicits are looked up in companion objects of types. The author does not provide an example for implicit parameters from companion objects (he only explains implicit conversion) but I think what this means is that a call to Container[A]#map should make all implicits from object Container available as implicit parameters, including my elementFactory. This assumption is supported by the fact that it is enough to provide the target type (no additional explicit imports!!) to get the implicit resolved.

Answer 1

The extra type parameter enables this behavior according to the specification of implicit resolution. Here is a summary from the FAQ answer to where do implicits come from (relevant parts bolded):

First look in current scope:

• Implicits defined in current scope
• Explicit imports
• wildcard imports

Now look at associated types in:

• Companion objects of a type (1)
• Implicit scope of an argument’s type (2)
• Implicit scope of type arguments (3)
• Outer objects for nested types
• Other dimensions

When you call map on a Mappable, you get the implicits from the implicit scope of its arguments, by (2). Since its argument is Factory in this case, that means that you also get the implicits from the implicit scope of all of type arguments of Factory, by (3). Next is the key: only when you add Source as a type parameter to Factory do you get all the implicits in the implicit scope of Container. Since the implicit scope of Container includes the implicits defined in its companion object (by (1)), this brings the desired implicit into scope without the imports you were using.

That's the syntactic reason, but there is a good semantic reason for this to be the desired behavior – unless the type is specified, the compiler would have no way of resolving the correct implicit when there may be conflicts. For example, if choosing between builder for a String or List[Char], the compiler needs to pick the correct one to enable "myFoo".map(_.toUpperCase) returning a String. If every implicit conversion were brought into scope all the time, this would be difficult or impossible. The above rules are meant to encompass an ordered list of what could possibly be relevant to the current scope in order to prevent this problem.

You can read more about implicits and implicit scope in the specification or in this great answer.

Here's why your other two solutions work: When you explicitly specify the return type of the call to map (in the version without the the Source parameter), then type inference comes into play, and the compiler can deduce that the parameter of interest That is Container, and therefore the implicit scope of Container comes into scope, including its companion object implicits. When you use an explicit import, then the desired implicit is in scope, trivially.

As for you meta-question, you can always click through the source code (or just checkout the repo), build minimal examples (like you have), and ask questions here. Using the REPL helps a lot to dealing with small examples like this.

Answer 2

The spec has a dedicated section on implicit parameter resolution. According to that section there are two sources for arguments to implicit parameters.

First, eligible are all identifiers x that can be accessed at the point of the method call without a prefix and that denote an implicit definition or an implicit parameter. An eligible identifier may thus be a local name, or a member of an enclosing template, or it may be have been made accessible without a prefix through an import clause.

So every name which is available without qualification and which is marked with the implicit keyword can be used as implicit parameter.

second eligible are also all implicit members of some object that belongs to the implicit scope of the implicit parameter's type, T.   The implicit scope of a type T consists of all companion modules of classes that are associated with the implicit parameter's type. Here, we say a class C is associated with a type T if it is a base class of some part of T.

Implicits defined in companion objects (a.k.a companion modules) of all parts of the types of an implicit parameter list are also available as parameter. So in the original example

def map[B, That](f: A => B)(implicit factory: Factory[Repr, B, That]): That 

we will get implicits defined in the companion objects of Factory, Repr, B, and That. As Ben Reich has pointed out in his answer, this explains why the Repr type parameter is necessary to find the implicit parameter.

Here is why it works with the explicitly defined return type

val mapped: Container[Int] = c.map { x => 2 * x }

With the explicit return type definition, type inference selects Container[Int] for the That parameter in Factory[Repr, B, That]. Therefore, implicits defined in Container are then available as well.