What is the difference between Seq and IndexedSeq / LinearSeq in Scala?

Question

In the Scala Documentation Collection Documentation , there are a few tips for this question:

Trait Seq has two signatures LinearSeq and IndexedSeq. They do not add any new operations, but each of them offers different performance characteristics. A linear sequence has efficient head and tail operations, while an indexed sequence has effective applications, length, and (if mutable) update operations.

But it does not concern me, when to use IndexedSeq instead of Seq ? I need a real example IndexedSeq or LinearSeq where these collections are better than Seq .

Answer 1

Seq is a super-sign, so it is more general, it has characteristics common to all sequences, both linear and indexed.

If you are interested in the sequence generated by the Seq.apply method in the companion Seq object, we can take a look at the implementation.

Keep in mind that if you use Seq.apply, you mean that you just need Seq, and that your code does not care whether it is linear or indexed

Answer tl; dr then: you use LinearSeq or IndexedSeq when you need to have certain performance characteristics, you use more general Seq when you don't need a difference

This is a companion Seq object:

 object Seq extends SeqFactory[Seq] { implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, Seq[A]] = ReusableCBF.asInstanceOf[GenericCanBuildFrom[A]] def newBuilder[A]: Builder[A, Seq[A]] = immutable.Seq.newBuilder[A] } 

The newBuilder[A] method is what is used to create Seq, as you can check in the Seq.apply method (defined in the GenericCompanion ):

 def apply[A](elems: A*): CC[A] = { if (elems.isEmpty) empty[A] else { val b = newBuilder[A] b ++= elems b.result() } } 

Now the question is: what does the immutable.Seq.newBuilder[A] assembly do? Let’s go and see, this time on an immutable.Seq companion object:

 object Seq extends SeqFactory[Seq] { // stuff def newBuilder[A]: Builder[A, Seq[A]] = new mutable.ListBuffer } 

It creates a mutable ListBuffer ! Why is this? This is because a mutable.ListBuffer also a Builder[A, Seq[A]] , that is, a class that the collection library uses to create new collections.

The actual output collection comes from this line (as you can see above):

 b.result() 

So what is the return type of ListBuffer.result() ? Release in ListBuffer:

 // Implementation of abstract method in Builder def result: List[A] = toList 

here you go: this is a list.

Seq(1,2,3) returns List[Int] under the hood, but the whole point here is that if you use Seq (), you don’t need to know which collection you have, because you are assuming a more abstract interface enough for your needs

Answer 2

Seq is simply the super-value of IndexedSeq and LinearSeq. Seq is an ordered list, unlike Set, which is usually unique and disordered, but as opposed to Map, which is a pair of key values.
Now comes IndexedSeq vs LinearSeq.
IndexedSeq subclasses, i.e. Vector, Range, String, are index-based quick access and usually fast updates. This is possible because they use data structures that are suitable for this, for example, an array inside (for example, in String) or a tree (actually it is 32 branches of the tree used by Vector .. for more details see this ), or Range which represents just three numbers. begin, end, step .., of which index calculations are simple.
In contrast, LinearSeq is all slow, index-based and access-based, and slow updates. Usually because they have an associated list structure. Prepend fast for all of them, i.e. Queue, Stack, List .., but append is known to be slow because it must go to the edge of the structure of the internal linked list. Except for the queue, which uses a trick with its own problems. The trick is described here .
In general, IndexedSeq are those data structures that have quick access and updating by index, and LinearSeq are those data structures that have quick addition.