Sequences

The rest of the page takes them one by one. The cost numbers come from the performance table in the official 2.13 guide, with C for constant, eC for effectively constant, aC for amortised constant and L for linear in the size:

Source: Collections 2.13: Performance characteristics

List is an immutable singly linked list built from two cases: Nil, the empty list, and :: ("cons"), a cell holding a head and a tail that is itself a List. Because a cell never changes, any list can share its tail with other lists: x :: xs allocates a single new cell and reuses xs in full. That makes prepending, head and tail constant time, and it makes indexing, length, last and appending linear.

Reading the output: :: and ::: end with a colon, so they are right-associative and are methods of the right operand ("Start" :: stops is stops.::("Start")); 1 :: 2 :: Nil is Nil.::(2).::(1). The line printing true shows that two lists built with "A" :: stops and "B" :: stops share the very same tail object (eq is reference equality). :+ appends but copies the whole list, so a loop that appends to a List is quadratic; prepend and reverse at the end instead, or use a ListBuffer.

Source: Scala 3 Book: List and Collections 2.13: Lists

The natural fit for List is recursion over its front, with the pattern case first :: rest, covered on Pattern Matching and Recursion & Tail Calls. It is a LinearSeq: the cost of xs(i) grows with i, so avoid index loops over a List.

Vector is the immutable sequence for everything that is not "recursion over the front". It is a wide, shallow tree (a trie with branching factor 32), so all of apply, updated, :+ and +: take effectively constant time, and an "update" copies only a handful of small arrays and shares the rest.

The class names at the end (Vector1, Vector2) are the internal depth: a Vector of up to 32 elements is a single array, up to 1024 elements two levels, and so on up to six levels. The updated vector big.updated(500, -1) has a different element at index 500 while big itself is unchanged.

Source: Scala 3 Book: Vector and Collections 2.13: Vectors

When in doubt about which immutable sequence to use, use Vector. Use List when you consume the sequence from the front, and Vector when you index into it or append to it. Seq(...) builds a List by default; if you want a Vector write Vector(...) or declare the type IndexedSeq.

When you build a sequence in a loop, or need in-place updates, use a mutable buffer. A Buffer is a growable Seq with += and ++= to append, prepend and insert to add elsewhere, -= and remove to delete, and in-place variants of the transformations (filterInPlace, mapInPlace, dropInPlace).

ArrayBuffer keeps the elements in an array that doubles when full, so append is amortised constant time and indexing is constant time, while prepend, insert and remove in the middle shift elements and are linear. ListBuffer keeps a linked list with a pointer to its last cell, so prepend and append are constant time and toList is constant time too (it hands over the list and marks the buffer as shared); indexing is linear. The Builder returned by List.newBuilder[Int] is the generic form of the same pattern: += elements, then result().

Source: Scala 3 Book: ArrayBuffer and Collections 2.13: Array buffers

A buffer is mutable, so a val buf = ArrayBuffer(...) still lets you change buf: val fixes the reference, not the contents. Immutable collections with val cannot be changed at all, which is why they need no -=:

(The compiler lists look-alike members because there is no += on List; the intended fix is a mutable collection, a var with xs :+= x, or building a new list.) Seq is also not assignable to mutable.Buffer, the first error above, for the reason explained in Pitfalls.

Source: Collections 2.13: List buffers

Array[T] is the JVM array. It is mutable, has a fixed size, is accessed and updated with parentheses (a(0) = 10, which the compiler turns into a.update(0, 10)), and unlike every other collection it is reified: Array[Int] is a real int[] and Array[String] is a real String[]. It is invariant in T (see Variance), where Java arrays are covariant. It is not a Seq; the operations (map, sorted, toList, …​) come from an implicit conversion to an array wrapper, so they work on arrays too and map returns an Array.

Source: Scala 3 Book: Array and Collections: Immutable ArraySeqs

Points to note in the output: printing an Array prints an identity string, so go through mkString or toList; Array(1, 2) == Array(1, 2) is false because arrays use reference equality, while sameElements and a conversion to Seq compare contents; Array.ofDim[Int](2, 3) creates a two-dimensional array; and ArraySeq.unsafeWrapArray(a) shares storage with a, which the printed ArraySeq(10, 99, 3) shows after a(1) = 99. For performance with primitives, Array[Int] avoids boxing completely.

Because an array’s element type is needed at run time to create it, generic code that creates arrays needs a ClassTag:

Source: Collections: Arrays

The fix is a context bound, def make[T: reflect.ClassTag](x: T): Array[T], as the 3.10 message says (3.9.0 and 3.3.8 only print "No ClassTag available for T"). Generic code that is happy with any sequence should use Vector, List or ArraySeq.

IArray[T] (Scala 3) is an immutable array: an opaque type whose only difference from Array is the missing update method. At run time it is a plain JVM array with no wrapper, which makes it the cheapest way to hold a read-only table of primitives.

Source: Scala API: IArray

updated, ++ and map return fresh IArray values, as for any collection; map on a primitive array needs a ClassTag for the result, which is found automatically for Int. Mutation through the type is rejected:

Source: Scala 3 Book: Array, Collections 2.13: Arrays and Collections 2.13: Immutable ArraySeqs

A Range is an immutable sequence of integers described by a start, an end and a step. It is an IndexedSeq that never stores the numbers: (1 to 1000000000).size is computed instantly. to includes the end, until excludes it, by sets the step (negative to count down), and the same syntax works for Char and, through BigDecimal, for decimals.

Ranges are the standard way to loop (for i <- 0 until n, see Conditionals & Loops) and are used in a for comprehension (For Comprehensions). A Floating point has no Range: 1.0 to 2.0 by 0.5 is rejected with "value to is not a member of Double", so write the bounds as BigDecimal (which gives a NumericRange, as in the output above) or use a plain loop. map on a Range returns a Vector, as the fifth output line shows.

Source: Scala 3 Book: Range and Collections 2.13: Ranges

Scala has an immutable Queue (two lists, so enqueue and dequeue are amortised constant time) and a mutable scala.collection.mutable.Queue, which since 2.13 is a thin subclass of ArrayDeque. ArrayDeque is the mutable double-ended queue implemented as a circular buffer; it is also the right choice for a stack (append and removeLast). StringBuilder builds a String in place and is the mutable Seq[Char]; it is the only mutable collection name in scope without an import.

The immutable Queue returns a new queue from enqueue and a pair (head, rest) from dequeue, so a state machine over it is a fold. The mutable queue returns the element and changes itself. ArrayDeque supports prepend and append in amortised constant time and removeHead and removeLast, plus constant time indexing. scala.collection.mutable.Stack exists (it was deprecated in 2.12 and reimplemented in 2.13) but ArrayDeque is the usual choice.

Source: Collections 2.13: Immutable queues and Collections 2.13: Mutable queues

Seq adds position-based operations to the Iterable vocabulary: apply, isDefinedAt, lift, indexOf, contains, padTo, updated, patch, prepended/appended, sorted, reverse/reverseIterator, search (binary search in a sorted sequence), startsWith, combinations, diff, intersect and concat. A few are worth seeing in action. Note the last line: s(10) on a three element Seq throws.

lift is the safe version of apply: it returns an Option instead of throwing, which is the idiomatic way to read a position that may not exist. search returns Found(index) or InsertionPoint(index). union is deprecated since 2.13.0 in favour of concat ("Use concat instead"). The exception from s(10) on a List is an IndexOutOfBoundsException; the stack frames show that List reaches the element through LinearSeqOps.apply, walking the list.

Source: Collections 2.13: The sequence traits Seq, IndexedSeq and LinearSeq

Every Seq can be matched with the Seq(...) extractor pattern, including a trailing wildcard that captures the rest, and the extractors +: and :+ match the first and last element (on Vector and other sequences; :: is List only). The extractor machinery is described on Extractors & Pattern Bindings.

Source: Scala 3 Reference: Sequence Match

In case Seq(first, rest*), rest* binds the remaining elements as a Seq. In Scala 2 the same pattern was written rest @ _*; the Scala 3 spelling is rest*, and the old spelling still compiled without any warning on 3.10.0 (checked with and without -source:future). The pattern init : last+ is cheap on a Vector; on a List it would walk the entire list.

Where Java code uses Optional the Scala code uses Option, which is why lift is natural; see Optional and Option & Null Safety for that side, and Kotlin Null Safety for the Kotlin approach with ?.

The sequence classes and operations behave identically on 3.3.8, 3.9.0 and 3.10.0: every program on this page was compiled and run on all three and produced the same output. The one visible difference is the compiler message for a missing ClassTag when creating a generic array, error E172: 3.10.0 says "No reflect.ClassTag available for T. You can fix this by changing [T] to [T: reflect.ClassTag]." while 3.9.0 and 3.3.8 only say "No ClassTag available for T". The other error messages on this page (E007, E008 for IArray, and E008 for +=) are identical on the three versions.