Collections

Scala ships two families of collections. The immutable ones — List, Vector, Set, Map — are what you get by default, with no import. An immutable collection never changes: "adding" an element returns a new collection and leaves the old one exactly as it was. The mutable ones live in scala.collection.mutable — ArrayBuffer, ListBuffer, mutable.Map, mutable.Set — and change in place.

import scala.collection.mutable

@main def run(): Unit =
  val nums = List(1, 2, 3)
  val more = nums :+ 4
  println(nums)
  println(more)

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

  val frozen = buf.toList
  buf.clear()
  println(frozen)
  println(buf)

List(1, 2, 3)
List(1, 2, 3, 4)
ArrayBuffer(100, 2, 3, 4)
List(100, 2, 3, 4)
ArrayBuffer()

@main def run(): Unit =
  val scores = List(10, 20, 30)
  scores(0) = 99
  println(scores)

-- [E008] Not Found Error: Main.scala:3:2
3 |  scores(0) = 99
  |  ^^^^^^
  |  value update is not a member of List[Int] - did you mean scores.updated?
1 error found
Compilation failed

@main def run(): Unit =
  val scores = List(10, 20, 30)
  val fixedScores = scores.updated(0, 99)
  println(fixedScores)

A List is a singly linked list: each cell holds one element and a pointer to the rest. The empty list is Nil, and :: (called "cons") puts one element in front of a list. List(1, 2, 3) is just a friendly way to write 1 :: 2 :: 3 :: Nil. head is the first element and tail is everything after it.

@main def run(): Unit =
  val xs = 1 :: 2 :: 3 :: Nil
  println(xs)
  println(xs == List(1, 2, 3))
  println(xs.head)
  println(xs.tail)
  println(xs.isEmpty)

  val withZero = 0 :: xs
  val withFour = xs :+ 4
  println(withZero)
  println(withFour)
  println(xs ++ List(8, 9))
  println(xs.length)

List(1, 2, 3)
true
1
List(2, 3)
false
List(0, 1, 2, 3)
List(1, 2, 3, 4)
List(1, 2, 3, 8, 9)
3

Why prepend is cheap and append is not

Putting an element in front makes one new cell that points at the existing list: constant time, O(1), whatever the length. Adding at the end with :+ has to copy every cell, because the old last cell cannot be changed to point somewhere new: O(n). Indexing xs(i) and length also walk the list. The standard pattern when building a list in a loop is to prepend and reverse once at the end — or to use a Vector.

@main def run(): Unit =
  val todo = List.empty[String]
  println(s"next: ${todo.head}")

Exception in thread "main" java.util.NoSuchElementException: head of empty list
	at scala.collection.immutable.Nil$.head(List.scala:664)
	at scala.collection.immutable.Nil$.head(List.scala:664)
	at Main$package$.run(Main.scala:3)
	at run.main(Main.scala:1)

@main def run(): Unit =
  val todo = List.empty[String]
  println(s"next: ${todo.headOption.getOrElse("nothing")}")

Vector is the immutable, general-purpose sequence: fast at both ends and fast to index. If you do not know which sequence you need, Vector is a safe choice. Array is the JVM array: fixed length, mutable in place, and the fastest option for number crunching or for calling Java code. It is the one mutable collection you get without an import.

@main def run(): Unit =
  val v = Vector(10, 20, 30)
  val v2 = v :+ 40
  val v3 = 0 +: v2
  println(v3)
  println(v3(2))
  println(v3.updated(2, 99))
  println(v3)

  val arr = Array(5, 3, 8)
  arr(0) = 1
  println(arr.mkString("[", ", ", "]"))
  println(arr.length)

Vector(0, 10, 20, 30, 40)
20
Vector(0, 10, 99, 30, 40)
Vector(0, 10, 20, 30, 40)
[1, 3, 8]
3

A Set holds each value at most once and answers "is this in here?" in effectively constant time. A Map associates keys with values; "a" -> 1 is just a tuple ("a", 1) written so it reads like an arrow. Both are immutable by default: +, -, updated and removed return new collections.

@main def run(): Unit =
  val tags = Set("scala", "jvm", "scala", "fp")
  println(tags.size)
  println(tags.contains("jvm"))
  println(tags("rust"))

  val a = Set(1, 2, 3, 4)
  val b = Set(3, 4, 5)
  println((a intersect b).toList.sorted)
  println((a union b).toList.sorted)
  println((a diff b).toList.sorted)
  println((a + 9 - 1).toList.sorted)

3
true
false
List(3, 4)
List(1, 2, 3, 4, 5)
List(1, 2)
List(2, 3, 4, 9)

The most important Map method is get. It returns an Option: Some(value) if the key is there, None if not. That forces you to decide what a missing key means. getOrElse(key, default) does the common case in one call. Calling the map like a function — prices("tea") — returns the bare value and throws if the key is missing.

@main def run(): Unit =
  val prices = Map("tea" -> 20, "coffee" -> 35)
  println(prices.get("tea"))
  println(prices.get("juice"))
  println(prices.getOrElse("juice", 0))
  println(prices.contains("coffee"))
  println(prices("coffee"))

  val updated = prices.updated("tea", 25) + ("juice" -> 40)
  println(updated)
  println(updated.removed("coffee"))
  println(prices)

  for (item, price) <- updated.toList.sortBy(_._2) do
    println(s"$item costs $price")

Some(20)
None
0
true
35
Map(tea -> 25, coffee -> 35, juice -> 40)
Map(tea -> 25, juice -> 40)
Map(tea -> 20, coffee -> 35)
tea costs 25
coffee costs 35
juice costs 40

@main def run(): Unit =
  val stock = Map("apple" -> 5, "pear" -> 2)
  println(stock("apple"))
  println(stock("mango"))

5
Exception in thread "main" java.util.NoSuchElementException: key not found: mango
	at scala.collection.immutable.Map$Map2.apply(Map.scala:343)
	at Main$package$.run(Main.scala:4)
	at run.main(Main.scala:1)

@main def run(): Unit =
  val stock = Map("apple" -> 5, "pear" -> 2)
  println(stock.getOrElse("mango", 0))
  val counts = stock.withDefaultValue(0)
  println(counts("mango"))

A Range is a sequence of evenly spaced integers that stores only its start, end and step — 1 to 1000000 takes no more memory than 1 to 3. to includes the end, until excludes it, by sets the step (negative to count down). A range is a full collection, so every operation in the next lesson works on it.

@main def run(): Unit =
  val r = 1 to 10
  println(r)
  println(r.sum)
  println((1 until 10 by 3).toList)
  println((5 to 1 by -1).toList)
  println(r.filter(_ % 4 == 0))
  println(List.range(0, 5))
  println(List.tabulate(4)(i => i * i))
  println(List.fill(3)("ab"))

Range 1 to 10
55
List(1, 4, 7)
List(5, 4, 3, 2, 1)
Vector(4, 8)
List(0, 1, 2, 3, 4)
List(0, 1, 4, 9)
List(ab, ab, ab)

Scala collections share one large set of methods, so what you learn on a List works on a Vector, Set, Map, Range or Array. Each returns a new collection. Here they are on one small data set; Module 07 looks at the functions you pass to them.

case class Sale(city: String, item: String, amount: Int)

@main def run(): Unit =
  val sales = List(
    Sale("Pune", "tea", 120),
    Sale("Delhi", "coffee", 300),
    Sale("Pune", "coffee", 180),
    Sale("Goa", "tea", 90),
    Sale("Delhi", "tea", 60)
  )
  println(sales.map(_.amount))
  println(sales.filter(_.amount > 100).map(_.city))
  println(sales.map(_.amount).sum)
  println(sales.map(_.item).distinct)
  println(sales.sortBy(_.amount).map(_.amount))
  println(sales.sortBy(s => -s.amount).head)
  println(sales.maxBy(_.amount).city)
  println(sales.count(_.item == "tea"))
  println(sales.exists(_.city == "Goa"))
  println(sales.forall(_.amount > 50))

List(120, 300, 180, 90, 60)
List(Pune, Delhi, Pune)
750
List(tea, coffee)
List(60, 90, 120, 180, 300)
Sale(Delhi,coffee,300)
Delhi
3
true
true

Folding: foldLeft and reduce

foldLeft(start)(op) walks the collection left to right, carrying an accumulator: it starts at start, and each element is combined into it with op. sum, count and max are all folds under the hood. reduce is a fold that uses the first element as the start — so it throws on an empty collection, and reduceOption is the safe version.

@main def run(): Unit =
  val xs = List(3, 1, 4, 1, 5)
  println(xs.foldLeft(0)(_ + _))
  println(xs.foldLeft("")((acc, x) => acc + x))
  println(xs.foldLeft(List.empty[Int])((acc, x) => x :: acc))
  println(xs.reduce(_ max _))
  println(List.empty[Int].reduceOption(_ + _))
  println(xs.scanLeft(0)(_ + _))

14
31415
List(5, 1, 4, 1, 3)
5
None
List(0, 3, 4, 8, 9, 14)

Grouping, splitting and pairing

@main def run(): Unit =
  val words = List("apple", "avocado", "banana", "blueberry", "cherry")
  val byLetter = words.groupBy(_.head)
  for (k, v) <- byLetter.toList.sortBy(_._1) do println(s"$k -> $v")

  val (short, long) = words.partition(_.length <= 6)
  println(short)
  println(long)

  val ranks = words.zip(1 to 10)
  println(ranks.take(2))
  println(words.zipWithIndex.last)

  val nums = (1 to 7).toList
  println(nums.take(3))
  println(nums.drop(5))
  println(nums.takeWhile(_ < 4))
  println(nums.grouped(3).toList)
  println(nums.sliding(3).toList.take(3))

a -> List(apple, avocado)
b -> List(banana, blueberry)
c -> List(cherry)
List(apple, banana, cherry)
List(avocado, blueberry)
List((apple,1), (avocado,2))
(cherry,4)
List(1, 2, 3)
List(6, 7)
List(1, 2, 3)
List(List(1, 2, 3), List(4, 5, 6), List(7))
List(List(1, 2, 3), List(2, 3, 4), List(3, 4, 5))

@main def run(): Unit =
  val todayOrders = List.empty[Int]
  println(todayOrders.reduce(_ + _))

Exception in thread "main" java.lang.UnsupportedOperationException: empty.reduceLeft
	at scala.collection.IterableOnceOps.reduceLeft$(IterableOnce.scala:876)
	at scala.collection.AbstractIterable.reduceLeft(Iterable.scala:979)
	at scala.collection.AbstractIterable.reduce(Iterable.scala:979)
	at Main$package$.run(Main.scala:3)
	at run.main(Main.scala:1)

@main def run(): Unit =
  val todayOrders = List.empty[Int]
  println(todayOrders.foldLeft(0)(_ + _))
  println(todayOrders.reduceOption(_ + _).getOrElse(0))

Every collection so far is strict: map computes every element immediately. A LazyList computes elements only when something asks for them, and remembers each one after it is computed. That makes infinite sequences possible — describe all of them, then take the few you need.

@main def run(): Unit =
  val naturals = LazyList.from(1)
  println(naturals.filter(_ % 7 == 0).take(3).toList)

  lazy val fibs: LazyList[BigInt] =
    BigInt(0) #:: BigInt(1) #:: fibs.zip(fibs.tail).map((a, b) => a + b)
  println(fibs.take(10).toList)
  println(fibs(90))

  val powers = LazyList.iterate(1)(_ * 2)
  println(powers.takeWhile(_ < 100).toList)

List(7, 14, 21)
List(0, 1, 1, 2, 3, 5, 8, 13, 21, 34)
2880067194370816120
List(1, 2, 4, 8, 16, 32, 64)

A view makes an ordinary collection lazy for one chain of operations. xs.map(f).filter(p).take(3) builds two full intermediate lists; xs.view.map(f).filter(p).take(3).toList runs f only on as many elements as it needs.

@main def run(): Unit =
  var calls = 0
  def slowSquare(n: Int): Int =
    calls += 1
    n * n

  val strict = (1 to 1000).map(slowSquare).filter(_ > 50).take(2)
  println(s"$strict after $calls calls")

  calls = 0
  val lazyResult = (1 to 1000).view.map(slowSquare).filter(_ > 50).take(2).toList
  println(s"$lazyResult after $calls calls")

Vector(64, 81) after 1000 calls
List(64, 81) after 9 calls

Every collection converts to every other with a to... method: toList, toVector, toSet, toArray, toMap (from pairs), and the general to(SomeCollection). mkString turns any collection into a String, optionally with a start, separator and end.

import scala.collection.immutable.SortedSet

@main def run(): Unit =
  val xs = List(3, 1, 3, 2)
  println(xs.toVector)
  println(xs.toSet.size)
  println(xs.to(SortedSet))
  println(xs.toArray.mkString(" | "))

  val pairs = List("a" -> 1, "b" -> 2)
  val m = pairs.toMap
  println(m)
  println(m.toList)
  println(m.keys.toList)
  println(m.values.sum)
  println(m.map((k, v) => (v, k)))

  println("hello".toList)
  println(List('h', 'i').mkString)
  println(xs.mkString("<", ", ", ">"))

Vector(3, 1, 3, 2)
3
TreeSet(1, 2, 3)
3 | 1 | 3 | 2
Map(a -> 1, b -> 2)
List((a,1), (b,2))
List(a, b)
3
Map(1 -> a, 2 -> b)
List(h, e, l, l, o)
hi
<3, 1, 3, 2>

Immutable collection

A collection that never changes; operations return a new collection and the old one stays valid.

Mutable collection

A collection from scala.collection.mutable that changes in place, such as ArrayBuffer or mutable.Map.

Cons (::)

The operator that puts one element in front of a List in constant time.

Nil

The empty List.

head / tail

The first element of a sequence, and everything after it. head throws on an empty list; headOption does not.

Vector

The immutable indexed sequence with effectively constant-time index, prepend and append.

Map.get

Looks up a key and returns Some(value) or None, instead of throwing.

foldLeft

Combines the elements left to right into an accumulator that starts at a given value.

groupBy

Splits a collection into a Map from a computed key to the elements with that key.

LazyList

A sequence whose elements are computed only when needed and then remembered; can be infinite.

View

A lazy wrapper over a strict collection so a chain of operations only does the work its result needs.