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

Question

In Scala Collection documentation, there is some clue to this question:

Trait Seq has two subtraits LinearSeq, and IndexedSeq. These do not add any new operations, but each offers different performance characteristics: A linear sequence has efficient head and tail operations, whereas an indexed sequence has efficient apply, length, and (if mutable) update operations.

But this does not address me when to use IndexedSeq instead of Seq? I need some real example of IndexedSeq or LinearSeq where these collections do better than Seq.

Answer 1

Seq is the super-trait, so it's more generic, it has the characteristics common to all sequences, both Linear and Indexed.

If you're wondering what kind of sequence is created by the Seq.apply method in the companion object of Seq, we can have a look at the implementation.

Keep in mind that if you use Seq.apply, you're implying that you just need a Seq and that your code doesn't care if it's Linear or Indexed

The tl;dr answer is then: you use LinearSeq or IndexedSeq when you need to have a certain performance characteristics, you use the more general Seq when you don't care about the difference

This is the companion object of Seq:

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's used to build the Seq, as you can verify in the Seq.apply method (defined on the trait 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 an immutable.Seq.newBuilder[A] build? Let's go see, this time on the immutable.Seq companion object:

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

It builds a mutable ListBuffer! Why is that? That's because a mutable.ListBuffer also happens to be a Builder[A, Seq[A]], that is a class that is used by the collection library to build new collections.

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

b.result()

So, what's the return type of the ListBuffer.result()? Let's go see in the ListBuffer:

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

here you go: It's a list.

Seq(1,2,3) returns a List[Int] under hood, but the whole point here is that if you're using Seq(), you don't need to know what kind of collection you have because you're implying that the more abstract interface is enough for your needs