generics - Scala 2.8 CanBuildFrom

Question

Following on from another question I asked, Scala 2.8 breakout, I wanted to understand a bit more about the Scala method TraversableLike[A].map whose signature is as follows:

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

Notice a few things about this method:

• It takes a function turning each A in the traversable into a B.
• It returns That and takes an implicit argument of type CanBuildFrom[Repr, B, That].

I can call this as follows:

> val s: Set[Int] = List("Paris", "London").map(_.length)
s: Set[Int] Set(5,6)

What I cannot quite grasp is how the fact that That is bound to B (that is, it is some collection of B's) is being enforced by the compiler. The type parameters look to be independent of both the signature above and of the signature of the trait CanBuildFrom itself:

trait CanBuildFrom[-From, -Elem, +To]

How is the Scala compiler ensuring that That cannot be forced into something which does not make sense?

> val s: Set[String] = List("Paris", "London").map(_.length) //will not compile

How does the compiler decide what implicit CanBuildFrom objects are in scope for the call?

Answer 1

Note that the second argument to map is an implicit argument. There must be an implicit in scope with the appropriate types, or, otherwise, you must pass such an argument.

In your example, That must be Set[String], B must be Int and Repr must be List[String]. Therefore, for that to compile you need the following implicit object in scope:

implicit object X: CanBuildFrom[List[String], Int, Set[String]]

There's no such thing in scope. Also, breakOut can't provide it, because it, itself, needs an implicit CanBuildFrom, whose first type can be any class (a contra-variant descendant of Nothing), but otherwise restricted by the other types.

Take a look, for instance, on the CanBuildFrom factory from the companion object of List:

implicit def  canBuildFrom [A] : CanBuildFrom[List, A, List[A]]  

Because it binds the second and third parameters through A, the implicit in question won't work.

So, how does one know where to look for, regarding such implicits? First of all, Scala does import a few things into all scopes. Right now, I can recall the following imports:

import scala.package._ // Package object
import scala.Predef._  // Object
// import scala.LowPriorityImplicits, class inherited by Predef
import scala.runtime._ // Package

Since we are concerned about implicits, note that when you import things from packages, the only implicits possible are singletons. When you import things from objects (singletons), on the other hand, you can have implicit definitions, values and singletons.

Right now, there are CanBuildFrom implicits inside Predef and LowPriorityImplicits, which are concerned with strings. They enable us to write "this is a string" map (_.toInt).

So, barring these automatic imports, and the explicit imports you make, where else can an implicit be found? One place: the companion objects of the instance on which the method is being applied.

I say companion objects, in the plural, because the companion objects of all traits and classes inherited by the class of the instance in question may contain relevant implicits. I'm not sure if the instance itself may contain an implicit. To be honest, I can't reproduce this right now, so I'm certainly making a mistake of some kind here.

At any rate, look inside the companion objects.