How does CanBuildFrom know whether a type can build from another?

Question

I read the official doc but I can't still understand how it works. For example:

class A {
  type Self
}
def seqToSet[T <: A](seq: Seq[T])
                    (implicit cbf: CanBuildFrom[Seq[T], T#Self, Set[T]]) {}

The above code can be compiled... but how? How does Scala know a Set can be built from a Seq? And how could it ensure a T#Self(literally any type) can be put into Set[T]?

Answer 1

It don't know it in general. You should provide such CanBuildFrom.

For simple cases like this you could use breakOut:

class A1 extends A { type Self = A1 }
seqToSet(new A1 :: Nil)(collection.breakOut)
// compiles fine

For more complicated case:

case class A2(val i: Int) extends A {
  type Self = Int
}

implicit val A2cbf = new CanBuildFrom[Seq[A2],A2#Self,Set[A2]] {
  import scala.collection.mutable.Builder
  class A2Builder extends Builder[A2#Self,Set[A2]] {
    var es = List[A2]()
    def +=(elem: A2#Self): this.type = { es ::= A2(elem); this }
    def clear(): Unit = es = Nil
    def result(): Set[A2] = es.toSet
  }
  def apply() = new A2Builder
  def apply(from: Seq[A2]) = apply()
}

seqToSet(new A2 :: Nil)(collection.breakOut)
// compiles fine

You should provide Builder (using CanBuildFrom) such that it accepts A2#Self in method += and returns Set[A2] as result. In code sample it creates new A2 using elem: A2(elem).

Let's create more useful method with almost the same parameters:

def seqToSet[T <: A](seq: Seq[T])(f: T => T#Self)
                    (implicit cbf: CanBuildFrom[Seq[T], T#Self, Set[T]]) = {
  seq.map{f}: Set[T]
}

seqToSet(A2(1) :: A2(2) :: Nil){ a2 => a2.i + 1 }
// Set[A2] = Set(A2(3), A2(2))

This method provides some strange transformation of A with transformation of collection type.

Answer 2

CanBuildFrom[A,B,C] is an implicit and it follows implicit resolution rules determined by the language specification. You can actually look directly here Where does Scala look for implicits? to find all the details.

So the answer is:

def seqToSet[T <: A](seq: Seq[T])
                    (implicit cbf: CanBuildFrom[Seq[T], T#Self, Set[T]]) {}

will compile if there is a CanBuildFrom[Seq[T],T#Self, Set[T]] in scope, and will fail to compile if there is not. If there is, someone has provided an implementation for it, which means the operation is possible (CanBuildFrom is a trait, so an instance is a concrete implementation of it)

With collections, the approached that the library designer decided to follow is to place the implicits in the companion objects : above you see Seq.scala from 2.10.3

trait Seq[+A] extends PartialFunction[Int, A]
                      with Iterable[A]
                      with GenSeq[A]
                      with GenericTraversableTemplate[A, Seq]
                      with SeqLike[A, Seq[A]] {
  override def companion: GenericCompanion[Seq] = Seq

  override def seq: Seq[A] = this
}

/** $factoryInfo
 *  The current default implementation of a $Coll is a `List`.
 *  @define coll sequence
 *  @define Coll `Seq`
 */
object Seq extends SeqFactory[Seq] {
  /** $genericCanBuildFromInfo */
  implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, Seq[A]] = ReusableCBF.asInstanceOf[GenericCanBuildFrom[A]]

  def newBuilder[A]: Builder[A, Seq[A]] = immutable.Seq.newBuilder[A]
}