Scala Collections

What this skill does

# Scala Collections

## Introduction

Scala's collections library is one of its most powerful features, providing a
rich, unified API for working with sequences, sets, and maps. The library
emphasizes immutability by default while offering mutable alternatives when
needed for performance-critical code.

The collections hierarchy distinguishes between immutable and mutable variants,
with immutable collections being the default. Key collection types include List,
Vector, Set, Map, Array, and their specialized variants. The library provides
consistent transformation operations across all collection types.

This skill covers immutable vs mutable collections, sequences (List, Vector,
Array), sets and maps, collection operations (map, filter, fold), for-comprehensions,
lazy evaluation, parallel collections, and performance characteristics.

## Immutable vs Mutable Collections

Immutable collections provide thread safety and predictability, while mutable
collections offer performance benefits for intensive updates.

```scala
// Immutable List (default)
val immutableList = List(1, 2, 3, 4, 5)
val newList = immutableList :+ 6  // Creates new list
val prepended = 0 :: immutableList  // Prepends element

// Original unchanged
println(immutableList)  // List(1, 2, 3, 4, 5)
println(newList)        // List(1, 2, 3, 4, 5, 6)

// Mutable ListBuffer
import scala.collection.mutable

val mutableList = mutable.ListBuffer(1, 2, 3)
mutableList += 4        // Mutates in place
mutableList ++= List(5, 6)
mutableList -= 2

println(mutableList)    // ListBuffer(1, 3, 4, 5, 6)

// Immutable Set
val immutableSet = Set(1, 2, 3)
val addedSet = immutableSet + 4
val removedSet = immutableSet - 2

// Mutable Set
val mutableSet = mutable.Set(1, 2, 3)
mutableSet += 4
mutableSet -= 2

// Immutable Map
val immutableMap = Map("a" -> 1, "b" -> 2, "c" -> 3)
val updatedMap = immutableMap + ("d" -> 4)
val removedMap = immutableMap - "b"

// Mutable Map
val mutableMap = mutable.Map("a" -> 1, "b" -> 2)
mutableMap("c") = 3
mutableMap += ("d" -> 4)
mutableMap -= "b"

// Converting between immutable and mutable
val immutable = List(1, 2, 3)
val asMutable = immutable.toBuffer  // Mutable copy
asMutable += 4

val backToImmutable = asMutable.toList

// Immutable Vector (efficient random access)
val vector = Vector(1, 2, 3, 4, 5)
val updatedVector = vector.updated(2, 10)  // Efficiently creates new vector

// Choosing between immutable and mutable
// Use immutable for:
// - Default choice
// - Concurrent access
// - Functional transformations
// - Public APIs

// Use mutable for:
// - Performance-critical loops
// - Large-scale updates
// - Local scope only
// - Builder patterns

// Builder pattern with immutable result
def buildList(): List[Int] = {
  val builder = List.newBuilder[Int]
  for (i <- 1 to 100) {
    builder += i
  }
  builder.result()
}

// Immutable collection with updates
case class User(name: String, age: Int, email: String)

val users = List(
  User("Alice", 30, "[email protected]"),
  User("Bob", 25, "[email protected]")
)

val updatedUsers = users.map { user =>
  if (user.name == "Alice") user.copy(age = 31)
  else user
}
```

Prefer immutable collections by default for safety and simplicity, using mutable
collections only when profiling shows performance bottlenecks.

## Sequences: List, Vector, and Array

Different sequence types offer varying performance characteristics for different
access patterns.

```scala
// List: Linked list, O(1) prepend, O(n) random access
val list = List(1, 2, 3, 4, 5)

val prepended = 0 :: list           // O(1)
val concatenated = list ::: List(6, 7)  // O(n)
val appended = list :+ 6            // O(n)

// Pattern matching on lists
def sumList(list: List[Int]): Int = list match {
  case Nil => 0
  case head :: tail => head + sumList(tail)
}

// List construction
val range = List.range(1, 11)       // List(1, 2, ..., 10)
val filled = List.fill(5)(0)        // List(0, 0, 0, 0, 0)
val tabulated = List.tabulate(5)(i => i * i)  // List(0, 1, 4, 9, 16)

// Vector: Indexed sequence, O(log32 n) for all operations
val vector = Vector(1, 2, 3, 4, 5)

val vectorUpdated = vector.updated(2, 10)  // O(log n)
val vectorAppended = vector :+ 6            // O(log n)
val vectorPrepended = 0 +: vector           // O(log n)

// Random access
println(vector(3))  // O(log n) - efficient

// Vector is better for:
// - Random access
// - Both-end operations
// - Large collections

// Array: Mutable, fixed-size, O(1) random access
val array = Array(1, 2, 3, 4, 5)

array(2) = 10  // Mutable update
println(array.mkString(", "))

// Array operations return Arrays
val doubled = array.map(_ * 2)

// ArrayBuffer: Mutable, resizable
import scala.collection.mutable.ArrayBuffer

val buffer = ArrayBuffer(1, 2, 3)
buffer += 4
buffer ++= Array(5, 6)
buffer.insert(0, 0)
buffer.remove(2)

// Seq: General sequence trait
def processSeq(seq: Seq[Int]): Int = seq.sum

println(processSeq(List(1, 2, 3)))
println(processSeq(Vector(1, 2, 3)))
println(processSeq(Array(1, 2, 3)))

// IndexedSeq for efficient random access
def processIndexed(seq: IndexedSeq[Int]): Int = {
  var sum = 0
  for (i <- seq.indices) {
    sum += seq(i)
  }
  sum
}

// LinearSeq for efficient head/tail operations
def processLinear(seq: collection.LinearSeq[Int]): Int = seq match {
  case head :: tail => head + processLinear(tail)
  case _ => 0
}

// Range: Lazy, memory-efficient sequences
val range1 = 1 to 10          // 1 to 10 inclusive
val range2 = 1 until 10       // 1 to 9
val range3 = 1 to 100 by 10   // 1, 11, 21, ..., 91

// Stream (deprecated, use LazyList)
val lazyList = LazyList.from(1).take(5)
println(lazyList.toList)

// Choosing the right sequence:
// List - Default, functional style, prepend-heavy
// Vector - Large, random access, both-end operations
// Array - Interop with Java, mutable, performance-critical
// ArrayBuffer - Mutable, frequent updates
```

Choose List for functional programming, Vector for random access, and Array for
Java interop or performance-critical code.

## Sets and Maps

Sets provide unique element storage while maps store key-value pairs, both with
efficient lookup operations.

```scala
// Immutable Set
val set1 = Set(1, 2, 3, 4, 5)
val set2 = Set(4, 5, 6, 7, 8)

// Set operations
val union = set1 union set2         // Set(1, 2, 3, 4, 5, 6, 7, 8)
val intersection = set1 intersect set2  // Set(4, 5)
val difference = set1 diff set2     // Set(1, 2, 3)

// Set methods
println(set1.contains(3))           // true
println(set1(3))                    // true (same as contains)

val added = set1 + 6
val removed = set1 - 3
val multiAdd = set1 ++ Set(6, 7, 8)

// Mutable Set
import scala.collection.mutable

val mutableSet = mutable.Set(1, 2, 3)
mutableSet += 4
mutableSet ++= Set(5, 6)
mutableSet -= 2

// Different Set implementations
val hashSet = mutable.HashSet(1, 2, 3)      // Unordered, fast
val linkedHashSet = mutable.LinkedHashSet(1, 2, 3)  // Maintains insertion order
val treeSet = collection.immutable.TreeSet(1, 2, 3)  // Sorted

// SortedSet
val sortedSet = collection.immutable.SortedSet(5, 2, 8, 1)
println(sortedSet)  // TreeSet(1, 2, 5, 8)

// Immutable Map
val map = Map(
  "Alice" -> 30,
  "Bob" -> 25,
  "Charlie" -> 35
)

// Map access
println(map("Alice"))               // 30
println(map.get("Alice"))           // Some(30)
println(map.get("David"))           // None
println(map.getOrElse("David", 0))  // 0

// Map operations
val updated = map + ("David" -> 28)
val removed = map - "Bob"
val merged = map ++ Map("Eve" -> 32)

// Map transformations
val ages = map.values.toList
val names = map.keys.toList
val pairs = map.toList

val incremented = map.map { case (name, age) => (name, age + 1) }
val filtered = map.filter { case (_, age) => age > 30 }

// Mutable Map
val mutableMap = mutable.Map("a" -> 1, "b" -> 2)
mutableMap("c") = 3
mutableMap += ("d" -> 4)
mutableMap.update("e", 5)

// Map variants
val hashMap = mutable.HashMap("a" -> 1, "b" -> 2)  // Unordered, fast
val linkedHashM