Scala Collection Hierarchy

If you've been working with Python, you know how liberating it is to reach for a list, dict, or set without a second thought. Scala offers a similarly vast collection library, but its type hierarchy can seem intimidating at first — and choosing the wrong structure can cost you performance or even cause subtle bugs. This lesson demystifies Scala's collection hierarchy, mapping each concept to a Python equivalent, so you can pick the right tool confidently and write idiomatic Scala code that scales.

The problem this lesson solves

Every Python developer has enjoyed the simplicity of my_list.append(...) or my_dict['key'] = value. When you step into Scala, you're greeted by names like Seq, IndexedSeq, LinearSeq, Vector, and List — and the question “Which one should I use?” becomes a daily obstacle. The problem is not a lack of options; it's the overload of options without a mental map.

Python's collections are pragmatic and loosely typed. Scala's collections are typed, immutable by default, and organized in a rich hierarchy. If you ignore this hierarchy, you might inadvertently pick a List for random access and suffer O(n) performance, or try to mutate an immutable collection and get confusing compile errors. To be productive in Scala — and to eventually leverage libraries like Apache Spark — you need to understand how the hierarchy works, not just memorize a few collection names.

Core concept / mental model

Think of Scala's collection hierarchy as a family tree where each branch shares a common set of methods and behaviors. At the top is Iterable, which is the root trait for all collections that can be iterated. Under it, you have three main branches:

• Seq – ordered sequences (like Python's list)
• Set – unordered unique elements (like Python's set)
• Map – key-value pairs (like Python's dict)

Each branch has immutable and mutable versions. The immutable versions are the default and are persistent — operations return a new collection without modifying the original, similar to Python's tuple but with full sequence operations.

Let's compare the top-level structure:

Iterable
 ├── Seq
 │   ├── IndexedSeq (Vector, Range, ArraySeq)
 │   └── LinearSeq (List, Stream, Queue)
 ├── Set
 │   ├── HashSet
 │   └── SortedSet (TreeSet)
 └── Map
     ├── HashMap
     └── SortedMap (TreeMap)

Mental model: Python's list is a concrete implementation. In Scala, Seq is an abstract trait; Vector and List are concrete implementations. You usually code against the most general type (e.g., Seq) and let the exact implementation be chosen by the context or a factory method.

How it works step by step

When you create a collection in Scala, the companion object's apply method smartly chooses the best concrete implementation for you. For example, Seq(1, 2, 3) returns an immutable List by default, while IndexedSeq(1, 2, 3) returns a Vector. This is because List is optimal for sequential access (head-to-tail), while Vector is optimized for random access.

Follow these steps to understand the decision process:

1. Start from Iterable – Every collection you can loop over is an Iterable.
2. Choose the branch – Seq, Set, or Map, depending on your data shape.
3. Decide mutability – Prefer immutable unless you need in-place updates for performance.
4. Pick the implementation – Inside each branch, choose the concrete type based on your access pattern (sequential vs. indexed).

Here's how the default factory methods map to implementations:

Hands-on walkthrough

Let's get your hands dirty. Open a Scala REPL (or your project with a main method) and follow along.

1. Basic hierarchy exploration

Start by exploring which concrete types the default factories return:

val seq = Seq(1, 2, 3)
println(seq.getClass)   // class scala.collection.immutable.$colon$colon (i.e., List)

val indexed = IndexedSeq(1, 2, 3)
println(indexed.getClass)   // class scala.collection.immutable.Vector

val set = Set(1, 2, 3)
println(set.getClass)       // class scala.collection.immutable.Set$Set3

val map = Map("a" -> 1, "b" -> 2)
println(map.getClass)       // class scala.collection.immutable.Map$Map2

Expected output:

class scala.collection.immutable.$colon$colon
class scala.collection.immutable.Vector
class scala.collection.immutable.Set$Set3
class scala.collection.immutable.Map$Map2

2. Working with immutable collections

Immutable collections are the default. Operations like +, -, and :: return a new collection:

val list = List(1, 2, 3)
val newList = 0 :: list   // prepend
println(newList)          // List(0, 1, 2, 3)
println(list)             // List(1, 2, 3) — unchanged

val vector = Vector(1, 2, 3)
val bigger = vector :+ 4  // append
println(bigger)           // Vector(1, 2, 3, 4)

3. Sequential vs indexed access

Choose List when you'll do head-first recursion; choose Vector when you need random access. Here's a quick performance test:

val list = List.range(1, 1000000)
val vector = Vector.range(1, 1000000)

// Sequential access (fast for List)
def sumSeq(seq: Seq[Int]): Int = seq.foldLeft(0)(_ + _)
println("List sum: " + sumSeq(list))
println("Vector sum: " + sumSeq(vector))

// Random access (fast for Vector)
val listElem = list(500000)   // O(n) - slow!
val vectorElem = vector(500000) // O(log n) - fast

Pro tip: When performance matters, use Vector for indexed access and List for recursion patterns (e.g., head :: tail style). The difference is logarithmic vs. linear complexity.

4. Mutable collections (use with caution)

Sometimes you truly need mutable state. Scala provides scala.collection.mutable:

import scala.collection.mutable

val buf = mutable.ArrayBuffer(1, 2, 3)
buf += 4
println(buf)  // ArrayBuffer(1, 2, 3, 4)

val mMap = mutable.Map("a" -> 1)
mMap("b") = 2
println(mMap) // Map("a" -> 1, "b" -> 2)

In Scala, prefer immutable by default — it aligns with functional programming and avoids shared-state bugs. Reach for mutable only when profiling shows a bottleneck.

Compare options / when to choose what

Here's a quick decision table for choosing the right collection:

Key differences from Python: - Arrays are mutable, but Seq is immutable by default. - List is a linked list, not an array; random access is O(n). - Scala distinguishes between IndexedSeq and LinearSeq to optimise operations.

Troubleshooting & edge cases

1. Trying to mutate an immutable collection

val list = List(1,2,3)
list(0) = 99  // Compile error! value update is not a member of List[Int]

Fix: Use updated or create a new list with :: and ++.

2. Performance surprises

val list = List(1,2,3)
val bad = list(1) // O(n) — works but slow for large lists

Fix: Use Vector or IndexedSeq for random access.

3. Mutable vs immutable type mismatch

When passing a mutable collection where an immutable Seq is expected, you'll get a type error. Prefer immutable types as function parameters to avoid surprises.

4. Range is also a collection

Range(1, 10) is an IndexedSeq — don't convert unnecessarily; it preserves memory.

What you learned & what's next

You now understand Scala's collection hierarchy: Iterable -> Seq/Set/Map, with immutable and mutable variants. You know how to pick the right implementation based on access patterns, and how to avoid common pitfalls like mutating immutable collections or misusing List for random access. This solid foundation will make your transition to Scala's functional programming features smooth.

In the next lesson, you'll explore pattern matching — a powerful feature that simplifies data extraction and control flow. Bring your understanding of collections, because pattern matching is often used to destructure them elegantly.