How does scala.collection.TraversableView.NoBuilder work?

Question

I've read

• Architecture of Scala Collections
• How are Scala collections able to return the correct collection type from a map operation?
• And of course, Is the Scala 2.8 collections library a case of "the longest suicide note in history"?

I think I have a bit of a handle on canBuildFrom.

But then I look at the source for TraversableView, and I see this:

object TraversableView {
  class NoBuilder[A] extends Builder[A, Nothing] {
    def +=(elem: A): this.type = this
    def iterator: Iterator[A] = Iterator.empty
    def result() = throw new UnsupportedOperationException("TraversableView.Builder.result")
    def clear() {}
  }
  type Coll = TraversableView[_, C] forSome {type C <: Traversable[_]}
  implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, TraversableView[A, Traversable[_]]] =
    new CanBuildFrom[Coll, A, TraversableView[A, Traversable[_]]] {
      def apply(from: Coll) = new NoBuilder
      def apply() = new NoBuilder
    }
}

How does TraversableView even work like this? It seems like there is nothing happening here (NoBuilder seems aptly named).

Could someone explain (1) the function that NoBuilder plays here and (2) how map, filter, etc. can still work?

Answer 1

The NoBuilder exists so that clients can treat Scala views as if they were normal collections when transforming them. It is a dummy implementation that allows TraversableView to extend Traversable and call methods like map without knowing if the collection is a view or a normal collection.

Longer explanation

When you call map, flatMap or scanLeft (called transformer operations) on a Scala collection, a CanBuildFrom implicit argument is automatically resolved. The CanBuildFrom object is an abstract factory for Builder objects.

Most Scala collections use Builders to add elements with += and produce a new collection by calling result on the buidler. E.g. given a builder object b, map does this:

def map[S, That](f: T => S)(implicit cbf: CanBuildFrom[Repr, S, That]) = {
  val b: Builder[S, That] = cbf(this)
  for (x <- this) b += f(x)
  b.result
}

Transformer operations on views do not instantiate a new collection. Instead, they create a lazy view. For example, map does something like this:

def map[S, That](f: T => S)(implicit cbf: CanBuildFrom[Repr, S, That]) = new TraversableView {
  def foreach[U](forFunc: T => U): Unit = for (x <- self) forFunc(f(x))
}

Note that a map on a view has the same signature, but does not really call += and result on the builder. Thus, the NoBuilder used in views does not really need to store elements or return a collection, it is just a dummy whose methods are never called.

The same signature allows writing this in client code:

def foo(xs: Traversable[Int]) = xs.map(_ + 1)
foo(0 until 100)
foo((0 until 100).view)