Why is Seq.newBuilder returning a ListBuffer?

Question

Looking at

val sb = Seq.newBuilder[Int]
println(sb.getClass.getName)
sb += 1
sb += 2
val s = sb.result()
println(s.getClass.getName)

the output is

scala.collection.mutable.ListBuffer
scala.collection.immutable.$colon$colon

using Scala 2.10.1.

I would expect Seq.newBuilder to return a VectorBuilder for example. This is returned by CanBuildFrom, if the result is explicitly typed to a Seq:

def build[T, C <: Iterable[T]](x: T, y: T)
                              (implicit cbf: CanBuildFrom[Nothing, T, C]): C = {
  val b = cbf()
  println(b.getClass.getName)
  b += x
  b += y
  b.result()
}

val s: Seq[Int] = build(1, 2)
println(s.getClass.getName) // scala.collection.immutable.Vector

in this case the builder is a VectorBuilder, and the result's class is a Vector.

So I explicitly wanted to build a Seq, but the result is a List which needs more RAM, according to Scala collection memory footprint characteristics.

So why does Seq.newBuilder return a ListBuffer which gives a List in the end?

Answer 1

The Scala Collections API is very complex and its hierarchy is rich in depth. Each level represents some sort of new abstraction. The Seq trait split up into two different subtraits, which give different guarantees for performance (ref.):

1. An IndexedSeq provides fast random-access of elements and a fast length operation. One representative of this IndexedSeq is the Vector.

2. A LinearSeq provides fast access only to the first element via head, but also has a fast tail operation. One representative of this LinearSeq is the List.

As the current default implementation of a Seq is a List, Seq.newBuilder will return a ListBuffer. However, if you want to use a Vector you can either use Vector.newBuilder[T] or IndexedSeq.newBuilder[T]:

scala> scala.collection.immutable.IndexedSeq.newBuilder[Int]
res0: scala.collection.mutable.Builder[Int,scala.collection.immutable.IndexedSeq[Int]] = scala.collection.immutable.VectorBuilder@1fb10a9f

scala> scala.collection.immutable.Vector.newBuilder[Int]
res1: scala.collection.mutable.Builder[Int,scala.collection.immutable.Vector[Int]] = scala.collection.immutable.VectorBuilder@3efe9969