Scala Collections — Immutable First, Mutable When Needed

Three packages, and why one of them is the default

The library is split across scala.collection, scala.collection.immutable and scala.collection.mutable. The root package holds the general traits — Iterable, Seq, Set, Map — and those traits make no promise about mutability: a collection.Seq may well be an ArrayBuffer that somebody else is still writing to. The two sub-packages hold implementations that do promise something, and the promise is the entire point. An immutable.Map cannot change after construction, so it can be shared across threads, used as a key, memoised, or returned from a method without a defensive copy.

Which one you get without asking is decided by Predef and the scala package object. List, Vector, Set, Map, Iterable and — since 2.13 — Seq all resolve to the immutable versions with no import at all, while anything mutable has to be written out or imported. The asymmetry is deliberate: the ergonomically cheapest option is the safe one, and reaching for mutability is a visible act in the source.

That 2.13 re-aliasing of Seq quietly closed a real hole. In 2.12 an unqualified Seq meant collection.Seq, so def f(xs: Seq[Int]) accepted an ArrayBuffer and had no way to stop the caller mutating it afterwards — including through the varargs path, where the array behind xs: _* was still reachable. Since 2.13 a bare Seq is immutable.Seq, and code that genuinely wants "any sequence, possibly mutable" has to spell out collection.Seq. When reading pre-2.13 code, treat every bare Seq in a public signature as a place where the immutability you assumed was never actually enforced.

The hierarchy is a set of contracts, not a class diagram

At the root sits IterableOnce, which promises exactly one thing: it can hand you an iterator. Both Iterator and Iterable extend it, and the difference between them is whether traversing twice is meaningful. Iterable adds that guarantee; nearly every other method in the library is derived from iterator, with per-implementation overrides purely for efficiency.

Below Iterable sit the three shapes, and each of them is a function:

Seq[A]     extends PartialFunction[Int, A]   // index   -> element
Set[A]     extends (A => Boolean)            // element -> membership
Map[K, V]  extends PartialFunction[K, V]     // key     -> value

This is not documentation garnish, it is load-bearing. It is why ids.map(byId) type-checks when byId is a Map, why xs.filter(allowedSet) works with a Set where a predicate was expected, and why applying a Seq to a sequence of indices gives you a permutation. Any time a collection appears where a function was demanded, this is the mechanism doing the work.

Equality is likewise defined at the trait level rather than per implementation. Two sequences are equal when they hold the same elements in the same order regardless of representation, so List(1, 2, 3) == Vector(1, 2, 3) is true. Collections from different branches are never equal: Seq(1, 2) == Set(1, 2) is false, and it stays false even though both hold 1 and 2, because canEqual rejects the cross-branch comparison before element comparison begins. The exception is Array, which is not in the hierarchy at all and therefore compares by reference.

IndexedSeq vs LinearSeq - the marker that predicts cost

Seq has two direct sub-traits, IndexedSeq and LinearSeq, and neither one adds a method you would ever call. They exist to carry a cost promise into the type system, and they are the single most useful thing in the hierarchy for predicting how code will behave.

LinearSeq says head and tail are cheap and everything positional is a walk; List is the canonical member. IndexedSeq says apply(i) and length are cheap; Vector, ArraySeq, Range and String (through StringOps) all qualify.

You can watch the library trusting its own markers. Because length on a LinearSeq traverses, comparing a size against a small constant would otherwise cost a full walk, so the library ships lengthCompare(n) and sizeIs, which stop as soon as the comparison is decided:

xs.size > 3        // walks the whole list: O(n)
xs.sizeIs > 3      // stops after four cells: O(min(n, 4))
xs.lengthCompare(3) // same idea, returns -1 / 0 / 1

On a very long or infinite LazyList that is not a micro-optimisation, it is the difference between terminating and not.

The practical lesson is about signatures rather than call sites. A method declaring def f(xs: Seq[A]) that then indexes has accepted a type which never promised indexing would be cheap, and nothing will warn you. Declare IndexedSeq when you index, List or LinearSeq when you destructure head :: tail, and plain Seq only when you truly just iterate. The asymptotic behaviour of the body then follows from a type the caller can read. What it costs when the marker is wrong is developed in collections performance.

What the concrete implementations are actually shaped like

List is a two-field cons cell — a head and a tail reference — terminated by Nil. Each cell is its own heap object, so an n-element list is n objects strung on pointers, with no memory locality whatsoever during traversal.

Vector is a shallow tree with a branching factor of 32. Up to 32 elements it is a single array; up to 1024 it is two levels; six levels covers more elements than any JVM will hold. Scala 2.13 replaced the older single-class version with a family of depth-specialised classes carrying fast-access prefix and suffix arrays at both ends, which is what makes append and prepend cheap rather than only indexed access.

immutable.HashMap and immutable.HashSet are CHAMP tries — hash-array mapped prefix tries keyed on successive slices of the element hash, with a compact bitmap-indexed node layout. Below five entries the library does not build a trie at all: Map1 through Map4 and Set1 through Set4 are hand-written classes holding their entries in plain fields, which is why small maps are so cheap to create and read.

TreeMap and TreeSet are red-black trees over an Ordering. You trade lookup for order: iteration follows key order, and you get range operations — rangeFrom, rangeUntil, minAfter — that a hash structure cannot offer at any price.

immutable.ArraySeq (introduced in 2.13 to replace WrappedArray) wraps one flat array and never mutates it, with primitive subclasses such as ofInt and ofDouble. It is the immutable, indexed, unboxed option, and it is what an Array becomes whenever something demands a Seq.

On the mutable side, ArrayBuffer is a growable array with amortised constant append, while ListBuffer assembles a List in order by keeping a handle on the final cell and mutating its tail, then freezing the structure so that toList hands over the chain rather than copying it.

Structural sharing - why an immutable update is not a copy

The reason immutable collections are not absurd is that "return a modified copy" almost never copies.

x :: xs allocates exactly one cons cell whose tail field points at xs itself. The old list remains a perfectly valid list, the new one is one object larger, and every element is shared between them. That is why prepending is the natural List operation, and why building a list by repeated prepending is genuinely cheap in a way that appending is not.

vector.updated(i, x) copies only the nodes on the path from the root down to the leaf holding index i — at most a handful of small arrays, independent of the collection's size — and points every untouched branch at the original nodes. Update one element of a 100,000-element vector and the result shares essentially all of the original's storage. The same path-copying argument covers the CHAMP maps and the red-black trees: the shape of the update is logarithmic in the size, not linear.

The consequence people miss is retention. Sharing makes old versions cheap to keep, but it equally means that holding a reference to any one version keeps the shared interior alive. Retaining every intermediate state of a long fold is not free merely because each individual step was.

Builders, CanBuildFrom, and the 2.13 redesign

The design goal that made this library famous is the uniform return type: map is defined once, high in the hierarchy, and yet List(1, 2).map(_ + 1) yields a List, BitSet(1, 2).map(_ + 1) yields a BitSet, and "abc".map(_.toUpper) yields a String. Something has to know how to construct the result.

Through Scala 2.12 that something was CanBuildFrom[From, Elem, To], an implicit threaded through nearly every transforming method:

def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Repr, B, That]): That

It worked, and it cost the library its readability. Every signature in the scaladoc carried a stray That and a bf; type errors quoted a CanBuildFrom the user had never written; adding a new collection meant supplying a family of implicits; and whether map on a Map returned a Map or a plain Iterable was settled by implicit priority rather than by anything visible in the code.

Scala 2.13 moved the answer into the class. The operation templates — IterableOps[A, CC[_], C] and its siblings — take the collection's own type constructor as parameters, so map can simply be declared to return CC[B] with no implicit involved. BuildFrom survives, but only for genuinely cross-type construction where the target is not derivable from the source: Future.traverse, sorted builders that need an Ordering, generic library code parametric at both ends.

Builder itself is unchanged in spirit — addOne (spelled +=), an optional sizeHint, then result(). Two properties are worth carrying around: a builder is single-use after result(), and sizeHint is what turns a build into one allocation instead of a sequence of doublings when the final size is already known.

The rewrite arrived with the rest of the 2.13 migration: Traversable and TraversableOnce became Iterable and IterableOnce, to[List] became to(List), Stream was deprecated for LazyList, JavaConverters moved to scala.jdk.CollectionConverters, and views were made uniformly lazy. See the Scala overview for where this sits in the language's history.

Strict, lazy, and single-use

Standard operations are strict: they run immediately and produce a real collection. Three types opt out, in three different ways, and conflating them is a reliable source of bugs.

View - lazy and not memoised

A View stores its source plus the pending operations and re-runs them on every traversal. Force the same view twice and every function in the chain executes twice; if any of them logs, increments a counter, or calls a service, you get that twice too. A view also retains a live reference to its source, so a view over an ArrayBuffer observes mutations made after the view was created, and a view over a large array pins that array for as long as the view is reachable. Scala 2.12's views were half-strict and inconsistent between types; 2.13 made them uniformly lazy and dropped force in favour of an explicit .to(Seq) or .toList. Their allocation payoff is developed in collections performance.

LazyList - lazy and memoised

LazyList is lazy in both head and tail, which is exactly the difference from the deprecated Stream, whose head was evaluated eagerly. That head laziness is what allows a LazyList to be defined by a self-referential val and what makes an infinite generator practical. Memoisation is the hazard rather than the feature: a LazyList retains every element it has yielded, so holding the head while walking to the end retains all of it. Bind an infinite source to a def, not a val, unless you actually want the cache.

Iterator - a cursor with a collection's API

An Iterator is neither lazy nor a collection; it is a mutable cursor wearing a collection-shaped interface, and the shape is the trap. it.size and it.length consume it and leave it empty, so a debug line that prints the size silently breaks every line after it. next() past the end throws NoSuchElementException. duplicate returns two iterators but buffers whatever they drift apart by. partition and span return halves backed by the same underlying source, so consuming one out of order buffers the other without bound. An iterator over a mutable collection is invalidated by mutating that collection underneath it.

IterableOnce is the type that means "this may be consumable". Accepting an IterableOnce parameter and then traversing it twice is precisely the bug the type was there to warn about; if two passes are needed, materialise once at the boundary with .toSeq and pay for it deliberately.

Array is a JVM array wearing a Scala API

Array[T] is not a member of the collection hierarchy. It compiles to a genuine JVM array — Array[Int] is int[] — and everything collection-like about it arrives by implicit conversion. Four consequences show up in real code.

Equality is reference equality. Array(1, 2) == Array(1, 2) is false, and an Array field inside a case class makes the generated equals and hashCode useless, which is a genuinely nasty bug when the case class is a map key. Use sameElements, or hold an immutable.ArraySeq, which is exactly the gap it was added to fill.

Variance differs from Java's. Scala's Array is invariant, so Array[String] is not an Array[Any]. Java's T[] is covariant, which is why the JVM has an ArrayStoreException at all. Scala's invariance protects code written in Scala; it does not protect an array that arrived from Java already aliased at a supertype.

Generic array creation needs a ClassTag. new Array[T](n) inside a generic method will not compile without an implicit ClassTag[T], because erasure leaves the emitted bytecode with no way to choose between newarray int and anewarray Object. The tag carries the component type at runtime, and the requirement propagates up through every generic signature that allocates.

The collection API is a wrapper. ArrayOps is a value class, so arr.map(f) normally allocates no wrapper and returns another Array. When a Seq is genuinely required — a Seq parameter, a xs: _* splat, storing it in a field — the conversion goes to ArraySeq, which wraps without copying but is a distinct object with distinct equality. And arr.toString is still the JVM's [I@1b6d3586; reach for mkString.

Crossing to Java

scala.jdk.CollectionConverters (scala.collection.JavaConverters before 2.13) supplies .asScala and .asJava. Two properties govern everything else.

They are wrappers, not copies. javaList.asScala is a constant-time operation returning a mutable.Buffer view onto the very same object: write through either side and both see it. Round-tripping unwraps rather than double-wrapping, so l.asScala.asJava eq l holds. When you want a snapshot you must ask for one explicitly with something like .asScala.toList, and when you are handing a collection across a trust boundary you almost always do want the snapshot.

The static type can lie. immutableMap.asJava compiles to a java.util.Map, and calling put on it throws UnsupportedOperationException at runtime, because the Scala map underneath has no such capability. If the Java side will mutate, convert from a mutable Scala collection or copy into a java.util.HashMap and accept the cost.

The long-removed JavaConversions did all of this implicitly and invisibly, and it was deprecated for the reason you would expect: conversions materialised in code that never asked for them, and the wrapper's mutability semantics surprised people at runtime rather than at compile time. Sibling converters live in the same package — scala.jdk.OptionConverters for Option and Optional (including the primitive OptionalInt family), and scala.jdk.StreamConverters for java.util.stream. Java null crosses every one of these unchanged, so the boundary is where wrapping into Option belongs.

Parallel collections, and why they left the library

Through Scala 2.12, every standard collection carried a .par method producing a parallel counterpart, after which the same map, filter and fold calls ran across a fork-join pool. In 2.13 they are absent from the standard library: they live in the separate scala-parallel-collections module, and .par does not compile until you add that dependency and import scala.collection.parallel.CollectionConverters._.

The proximate cause was the 2.13 modularisation, the same pass that moved scala-xml and scala-swing out of the core distribution. But parallel collections were the piece nobody argued hard to keep, because .par is a one-token edit that changes evaluation semantics. Element order is no longer the order of effects, so a closure that touches anything shared now races. A reduce with a non-associative function returns a different answer depending on how the input was split. Exceptions raised in workers arrive wrapped rather than propagating as written. Because the edit looks local and the failures are nondeterministic, the bugs it produced surfaced in production instead of in review.

The shared pool made it worse: one blocking element inside one .par chain could starve every other parallel operation running in the JVM. Where the work is truly CPU-bound and the closure is truly pure, the module still does its job. Where it is not, an explicit Future, a bounded-parallelism traversal from Cats Effect or ZIO, or a real streaming library gives you a scheduler you can reason about and configure.

Choosing from the access pattern, not from habit

The choice that matters most is the one written into the signature, because that is the one every caller inherits.

A handful of rules survive contact with real systems. Default to immutable and keep mutability local and unexported: build with a buffer inside the method and return the frozen result. Never put collection.Seq or a mutable type in a public signature, because that is handing out a mutation channel that no reviewer will notice. Prefer a Map over a sequence you intend to search — once a lookup happens more than a couple of times, it is the structure that is wrong, not the loop. And treat "whatever I typed last time" as the failure mode it is: the constructor most Scala developers reach for by reflex is List, and List is the wrong default for anything that gets indexed.

The related pieces sit nearby: collections performance for allocation, boxing and the cost of getting the structure wrong, and higher-order functions for what the combinators themselves cost.