Why does Seq.newBuilder return 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) 

conclusion

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

using Scala 2.10.1.

I would expect Seq.newBuilder return VectorBuilder , for example. This returns CanBuildFrom if the result is explicitly typed in 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 VectorBuilder , and the result class is Vector .

Therefore, I clearly wanted to create Seq , but the result is a List that needs more RAM, according to the Scala characteristics of the memory collection memory ,

So why does Seq.newBuilder return a ListBuffer , which eventually gives a List ?

Answer 1

The Scala Collection API is very complex and its hierarchy is rich in depth. Each level represents some new abstraction. The Seq trait is divided into two different subheadings that give different performance guarantees ( ref. ):

• An IndexedSeq provides quick random access to items and a quick-length operation. One representative of this IndexedSeq is Vector .

• A LinearSeq provides quick access only to the first element through the head, but also has quick tail operation. One representative of this LinearSeq is List .

Since the current default implementation of Seq is List , Seq.newBuilder will return a ListBuffer . However, if you want to use Vector , you can 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 

Answer 2

Seq default implementation List :

 Seq(1, 2, 3) // -> List(1, 2, 3) 

... so ListBuffer is the right builder. If you want Vector , use Vector.newBuilder or IndexedSeq.newBuilder .

Answer 3

Good, but you won’t believe it. Enabling -Yinfer-debug for your counter CanBuildFrom example,

 [search] $line14.$read.$iw.$iw.build[scala.this.Int, Seq[scala.this.Int]](1, 2) with pt=generic.this.CanBuildFrom[scala.this.Nothing,scala.this.Int,Seq[scala.this.Int]] in module class $iw, eligible: fallbackStringCanBuildFrom: [T]=> generic.this.CanBuildFrom[String,T,immutable.this.IndexedSeq[T]] [solve types] solving for T in ?T inferExprInstance { tree scala.this.Predef.fallbackStringCanBuildFrom[T] tree.tpe generic.this.CanBuildFrom[String,T,immutable.this.IndexedSeq[T]] tparams type T pt generic.this.CanBuildFrom[scala.this.Nothing,scala.this.Int,Seq[scala.this.Int]] targs scala.this.Int tvars =?scala.this.Int } [search] considering no tparams (pt contains no tvars) trying generic.this.CanBuildFrom[String,scala.this.Int,immutable.this.IndexedSeq[scala.this.Int]] against pt=generic.this.CanBuildFrom[scala.this.Nothing,scala.this.Int,Seq[scala.this.Int]] [success] found SearchResult(scala.this.Predef.fallbackStringCanBuildFrom[scala.this.Int], ) for pt generic.this.CanBuildFrom[scala.this.Nothing,scala.this.Int,Seq[scala.this.Int]] [infer implicit] inferred SearchResult(scala.this.Predef.fallbackStringCanBuildFrom[scala.this.Int], ) 

and indeed

  implicit def fallbackStringCanBuildFrom[T]: CanBuildFrom[String, T, immutable.IndexedSeq[T]] = new CanBuildFrom[String, T, immutable.IndexedSeq[T]] { def apply(from: String) = immutable.IndexedSeq.newBuilder[T] def apply() = immutable.IndexedSeq.newBuilder[T] } 

What do you mean, your Iterable is not a string?

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

Such is evil, deducing neither Nothing nor Any.

Edit: Sorry, I was wrong, I see that you did not say anything.

Update:

Since CBF is contravariant in From , CBF of String serves as CBF of Nothing .

 scala> typeOf[CanBuildFrom[Nothing,Int,Seq[Int]]] <:< typeOf[CanBuildFrom[String,Int,Seq[Int]]] res0: Boolean = false scala> typeOf[CanBuildFrom[String,Int,Seq[Int]]] <:< typeOf[CanBuildFrom[Nothing,Int,Seq[Int]]] res1: Boolean = true 

For example, if you need to build from immutable.Map , you need the CBF from collection.Map work.

As someone else commented, it's just weird for Nothing . But you get what you asked for. That is, you did not specify, which means that you do not mind that you will return, Vector or something else.

Answer 4

I agree that this is strange. Why don't you just use Vector.newBuilder if this is what you are looking for?

 scala> val sb = Vector.newBuilder[Int] sb: scala.collection.mutable.Builder[Int,scala.collection.immutable.Vector[Int]] = scala.collection.immutable.VectorBuilder@1fb7482a scala> println(sb.getClass.getName) scala.collection.immutable.VectorBuilder scala> sb += 1 res1: sb.type = scala.collection.immutable.VectorBuilder@1fb7482a scala> sb += 2 res2: sb.type = scala.collection.immutable.VectorBuilder@1fb7482a scala> val s = sb.result() s: scala.collection.immutable.Vector[Int] = Vector(1, 2) scala> println(s.getClass.getName) scala.collection.immutable.Vector