378

I've seen in many examples that sometimes a Seq is being used, while other times is the List...

Is there any difference, other than the former one being a Scala type and the List coming from Java?

Jonik
  • 80,077
  • 70
  • 264
  • 372
opensas
  • 60,462
  • 79
  • 252
  • 386

5 Answers5

495

In Java terms, Scala's Seq would be Java's List, and Scala's List would be Java's LinkedList.

Note that Seq is a trait, which is similar to Java's interface, but with the equivalent of up-and-coming defender methods. Scala's List is an abstract class that is extended by Nil and ::, which are the concrete implementations of List.

So, where Java's List is an interface, Scala's List is an implementation.

Beyond that, Scala's List is immutable, which is not the case of LinkedList. In fact, Java has no equivalent to immutable collections (the read only thing only guarantees the new object cannot be changed, but you still can change the old one, and, therefore, the "read only" one).

Scala's List is highly optimized by compiler and libraries, and it's a fundamental data type in functional programming. However, it has limitations and it's inadequate for parallel programming. These days, Vector is a better choice than List, but habit is hard to break.

Seq is a good generalization for sequences, so if you program to interfaces, you should use that. Note that there are actually three of them: collection.Seq, collection.mutable.Seq and collection.immutable.Seq, and it is the latter one that is the "default" imported into scope.

There's also GenSeq and ParSeq. The latter methods run in parallel where possible, while the former is parent to both Seq and ParSeq, being a suitable generalization for when there is no concern for code parallelism. They are both relatively new, so people don't use them as much.

Community
  • 1
  • 1
Daniel C. Sobral
  • 295,120
  • 86
  • 501
  • 681
  • 3
    RE *"Java has no equivalent to immutable collections"*, although `String` is not a collection, it is an example of immutable classes familiar to Java programmers. – huynhjl Jun 03 '12 at 02:19
  • 19
    @huynhjl That's beside the point. I was drawing parallels between what exists in Java and what exists in Scala, and there just isn't any concept of mutable/immutable collections in Java. – Daniel C. Sobral Jun 03 '12 at 07:03
  • 1
    ParSeq is probably little used because its use cases are limited by Amdahl's Law - your speedup from parallelism is limited if the execution time is dominated by its sequential bits. Use with care. – Rick-777 Jun 07 '12 at 22:22
  • 2
    Java actually has the equivalent of immutable collections. Its not that 'well advertised' but its there and when you use generics heavily you are likely to hit some `UnsupportedOperationException` because of this. To create an immutable list in Java you use the Collections.unmodifiableList() and similarly there are other methods for Sets, Maps etc. http://docs.oracle.com/javase/6/docs/api/java/util/Collections.html#unmodifiableList(java.util.List) – jbx Nov 14 '13 at 16:16
  • 32
    @jbx Not true. If you use these methods, you get something an object that will throw exceptions on methods that modify it, but not an _immutable_ object. If the original object gets modified after the unmodifiable object got created, the unmodifiable object will reflect that. So, unmodifiable, yes, immutable, no. – Daniel C. Sobral Nov 14 '13 at 19:30
  • Well, yes and no. Agreed the language is not designed for pure immutability. I said 'equivalent' because in most cases it can be used to suit the purpose. In fact when you have a generic collection parameter of a certain super type with `extends` and the actual concrete class passed is of a sub-type Java makes use of an unmodifiable collection to enforce the receiving method not to modify it, thus avoiding insertion of an object of a different subtype. Yes the case you are mentioning allows you to modify the object contained in the collection, but for the sake of type safety it still holds. – jbx Nov 14 '13 at 20:07
  • 4
    @jbx The receiving method cannot keep a reference to the collection it received and assume it will never change, and there's no type in the standard Java library that will guarantee that -- that is immutability. So, for instance, that receiving method cannot guarantee thread safety. And this doesn't even touch the persistent characteristics enabled by immutability. Without all that, it cannot be called "equivalent". – Daniel C. Sobral Nov 14 '13 at 22:46
  • Though it's hinted at, it's probably worth noting that Scala's List is O(n) for element lookup using indices; so if you need non-sequential lookup use something else, like an IndexedSeq or a Vector. – DK_ Nov 18 '13 at 22:44
  • "Vector is a better choice than List" is too general. List has constant time for head, tail and prepend whilst for Vector they are "effectively constant". I'd use List where these 3 operations are enough since it has a little less overhead – justinhj Feb 11 '16 at 17:01
  • 1
    @justinhj Which ignores locality of reference. Yes, it is too general, but it happens to be true in all but edge cases. – Daniel C. Sobral Feb 12 '16 at 22:58
  • If `Seq` is a trait, then why can I instantiate it? e.g., why is `var x = Seq(1, 2, 3)` legal? – Chris Prince Sep 01 '16 at 01:09
  • @ChrisPrince The `Seq` object inherits an `apply` method. – musiKk Sep 05 '16 at 05:45
  • 2
    @ChrisPrince Because `Seq` is both a trait and an object. When you write `var x = Seq(1, 2, 3)`, you are calling the `apply` method on the object. – Daniel C. Sobral Sep 14 '16 at 17:10
  • Is important to point out that Seq is a lazy operation representation while List is a concrete data structure that stores the values in memory. I think this is the most valuable difference. – hdkrus Nov 03 '18 at 01:35
  • @hdkrus `Seq` is not a lazy operation. It's an interface, which `List` implements. – Daniel C. Sobral Nov 06 '18 at 01:32
  • @Daniel, you're completely right. I was thinking in Immutable.js but this is Scala, my bad – hdkrus Nov 07 '18 at 02:28
130

A Seq is an Iterable that has a defined order of elements. Sequences provide a method apply() for indexing, ranging from 0 up to the length of the sequence. Seq has many subclasses including Queue, Range, List, Stack, and LinkedList.

A List is a Seq that is implemented as an immutable linked list. It's best used in cases with last-in first-out (LIFO) access patterns.

Here is the complete collection class hierarchy from the Scala FAQ:

enter image description here

Ceasar
  • 22,185
  • 15
  • 64
  • 83
  • 5
    Where Array (and ArrayBuffer)? It is not kind of Iterable – Peter Krauss Oct 05 '19 at 15:38
  • 1
    [This answer](https://stackoverflow.com/a/3634190) shows Array – Topa Jan 28 '22 at 21:10
  • If you're curious about the affirmative _It's best used in cases with last-in first-out (**LIFO**) access patterns_ think of using `prepend()` and `head()` operations as O(1) vs `append()` OR `last()`, which is O(n) of number of elements in the list. – Ricardo Jul 21 '22 at 23:57
36

Seq is a trait that List implements.

If you define your container as Seq, you can use any container that implements Seq trait. 

scala> def sumUp(s: Seq[Int]): Int = { s.sum }
sumUp: (s: Seq[Int])Int

scala> sumUp(List(1,2,3))
res41: Int = 6

scala> sumUp(Vector(1,2,3))
res42: Int = 6

scala> sumUp(Seq(1,2,3))
res44: Int = 6

Note that 

scala> val a = Seq(1,2,3)
a: Seq[Int] = List(1, 2, 3)

Is just a short hand for:

scala> val a: Seq[Int] = List(1,2,3)
a: Seq[Int] = List(1, 2, 3)

if the container type is not specified, the underlying data structure defaults to List.

Akavall
  • 82,592
  • 51
  • 207
  • 251
18

In Scala, a List inherits from Seq, but implements Product; here is the proper definition of List : 

sealed abstract class List[+A] extends AbstractSeq[A] with Product with ...

[Note: the actual definition is a tad bit more complex, in order to fit in with and make use of Scala's very powerful collection framework.]

Thomas Grainger
  • 2,271
  • 27
  • 34
zakelfassi
  • 2,936
  • 1
  • 22
  • 20
2

As @daniel-c-sobral said, List extends the trait Seq and is an abstract class implemented by scala.collection.immutable.$colon$colon (or :: for short), but technicalities aside, mind that most of lists and seqs we use are initialized in the form of Seq(1, 2, 3) or List(1, 2, 3) which both return scala.collection.immutable.$colon$colon, hence one can write:

var x: scala.collection.immutable.$colon$colon[Int] = null
x = Seq(1, 2, 3).asInstanceOf[scala.collection.immutable.$colon$colon[Int]]
x = List(1, 2, 3).asInstanceOf[scala.collection.immutable.$colon$colon[Int]]

As a result, I'd argue than the only thing that matters are the methods you want to expose, for instance to prepend you can use :: from List that I find redundant with +: from Seq and I personally stick to Seq by default.

Profiterole
  • 167
  • 1
  • 4