Scala for scalable software: collections, mutability, modularity

1. Where do OOP and FP meet in Scala?

By this point of the course both halves of Scala are on the table. The FP half has function types and literals, higher-order functions, genericity, pattern matching without mutation, modules and ADTs (product and sum types) and lazy evaluation. The OOP half is Java's, made purer: traits, inheritance and delegation, class parameters and auxiliary constructors, object as a singleton that also collects what Java would make static, and uniform access, where every operation is a method call.

The resulting shape is: classes and objects are the main constructs, and methods are filled in functional style. The deck describes Scala as three stacked levels:

Collections are the running example of this lesson. Every application manages sets and iterations of objects. In Scala collections also connect to lazy lists, options and monads, and writing one teaches how to write any structure that combines data and behaviour.

2. How do you build a functional data type the Scala way?

A good data type should be immutable when performance allows. It should report "non-bug" failures, such as asking for the head of an empty list, with Option rather than exceptions, and it should support declarative map, filter and foreach. There are three ways to organise it:

• Fully functional (lessons 3 and 4): an enum for the data, and operations as functions in a separate module, possibly behind an opaque type.
• Fully OO, as in Java: an interface with the operations, and one class per implementation.
• Scala's OO/FP mixture: one enum declares the constructors and the OO-style operation signatures, and a single implementation of each algorithm pattern-matches on this. Factories and FP-style helpers go in the companion object.

The :: trick

The example is the cons list, the simplest structure and the most used in FP because it is easy to match. Its cons case is called :: instead of Cons, and a method with the same name prepends an element:

object RightAssociativeConstruction extends App:

  enum List[A]: // a type with two implementations and methods
    case ::(h: A, t: List[A]) // just a different name for Cons
    case Nil()
    def ::(h: A): List[A] = List.::(h, this)
    def isEmpty: Boolean = this == Nil() // another method

  object List:
    def head(l: List[Int]): Option[Int] = l match
      case h :: _ => Some(h) // same as ::(h, _) => Some(h)
      case _ => None

  import List.*

  val l: List[Int] = ::(10, ::(20, ::(30, Nil()))) // using case ::(h, t)
  val l2: List[Int] = Nil().::(30).::(20).::(10)   // using def ::
  val l3: List[Int] = 10 :: 20 :: 30 :: Nil()      // using infix notation
  // recall that operators ending with : are right-associative

  println(s"$l, $l2, $l3, ${l.isEmpty}")
  // ::(10,::(20,::(30,Nil()))), ::(10,::(20,::(30,Nil()))), ::(10,::(20,::(30,Nil()))), false
  println(head(l))   // Some(10): FP-like call
  println(l.isEmpty) // false: OO-like call

Two rules make this work. First, a method whose name ends in : is right-associative, and its receiver is the operand on the right: 10 :: l means l.::(10). So 10 :: 20 :: 30 :: Nil() groups as 10 :: (20 :: (30 :: Nil())), which is Nil().::(30).::(20).::(10). The expression reads left to right while the list is built right to left, one O(1) prepend at a time. With ordinary left associativity, 10 :: 20 would call :: on the Int 10, which has no such method. Second, in a pattern, the infix form p op q means op(p, q), so case h :: t is the case class pattern ::(h, t). One name therefore serves construction, prepending and extraction. Inside the enum the method writes List.::(h, this) to call the case constructor rather than itself.

The type: contract and algorithms in one place

enum List[A]:
  case ::(h: A, t: List[A])
  case Nil()
  def ::(h: A): List[A] = List.::(h, this)

  def head: Option[A] = this match
    case h :: t => Some(h)  // pattern for scala.Option
    case _ => None          // pattern for scala.Option

  def tail: Option[List[A]] = this match
    case h :: t => Some(t)
    case _ => None

  def append(list: List[A]): List[A] = this match
    case h :: t => h :: t.append(list)
    case _ => list

  def foreach(consumer: A => Unit): Unit = this match
    case h :: t => consumer(h); t.foreach(consumer)
    case _ =>

  def get(pos: Int): Option[A] = this match
    case h :: t if pos == 0 => Some(h)
    case h :: t if pos > 0 => t.get(pos - 1)
    case _ => None

  def filter(predicate: A => Boolean): List[A] = this match
    case h :: t if predicate(h) => h :: t.filter(predicate)
    case _ :: t => t.filter(predicate)
    case _ => Nil()

  def map[B](fun: A => B): List[B] = this match
    case h :: t => fun(h) :: t.map(fun)
    case _ => Nil()

Every operation is a method with an OO signature, and every body is a pattern match on the receiver. head, tail and get return Option, and get uses guards to walk the list. The companion object adds a varargs factory and a replicating one:

object List:  // factories
  def apply[A](elems: A*): List[A] =
    var list: List[A] = Nil()
    for e <- elems.reverse do list = e :: list
    list

  def of[A](elem: A, n: Int): List[A] =
    if n == 0 then Nil() else elem :: of(elem, n - 1)

object Test extends App:
  import List.*

  println(List(10, 20, 30, 40))        // ::(10,::(20,::(30,::(40,Nil()))))
  val l = 10 :: 20 :: 30 :: 40 :: Nil() // same as above
  println(l.head)                      // Some(10)
  println(l.tail)                      // Some(::(20,::(30,::(40,Nil()))))
  println(l.append(l))                 // 10,20,30,40,10,20,30,40 (as nested ::)
  println(l append l)                  // the same: infix call of a one-argument method
  println(l get 2)                     // Some(30)
  println(of("a", 3))                  // ::(a,::(a,::(a,Nil())))
  println(l filter (_ <= 20) map ("a" + _))   // ::(a10,::(a20,Nil()))
  println(l.filter(_ <= 20).map("a" + _))     // the same, with dots
  for i <- l do println(i)             // 10 20 30 40, one per line: uses foreach
  println(l.append(l) == l)            // false: append built a new list, l is unchanged

A one-argument method can be called infix (l get 2, l append l), so chains like l filter (_ <= 20) map ("a" + _) read like Java streams. Because the type has foreach, for i <- l do … works on it. Adding map and flatMap would enable for … yield with several generators, and a withFilter (for instance a filter aliased as withFilter) would enable guards: Scala 3 desugars if guards to withFilter only (the desugaring is in lesson 7). The last line prints false: append built a new list and left l unchanged.

Inside, the design separates the contract, construction and extraction, and the algorithms. Some algorithms can still be written OO-style, and many look alike, which calls for a refactoring into folds (next section). The question left open is encapsulation: here the representation is public. FP's answer is to encapsulate behaviour rather than data, through type classes (lesson 4).

3. How do foldLeft and foldRight differ?

map, filter, append and size all walk the list with the same recursion. Folds capture that recursion once:

enum List[A]:
  case ::(h: A, t: List[A])
  case Nil()
  def ::(h: A): List[A] = List.::(h, this)

  // foldLeft captures left-to-right accumulation, typical of reductions
  @tailrec final def foldLeft[B](init: B)(f: (B, A) => B): B = this match
    case h :: t => t.foldLeft(f(init, h))(f)
    case _ => init

  def size(init: Int = 0): Int = foldLeft(init)((acc, _) => acc + 1)

  override def toString: String = foldLeft("|")((acc, h) => acc + h.toString + "|")

  // foldRight captures right-to-left construction
  def foldRight[B](init: B)(op: (A, B) => B): B = this match
    case h :: t => op(h, t.foldRight(init)(op))
    case _ => init

  def map[B](f: A => B): List[B] = foldRight(Nil())(f(_) :: _)

  def concat(l: List[A]): List[A] = foldRight(l)(_ :: _)

  // right-to-left construction with tail recursion needs a reverse
  def reverse: List[A] = foldLeft(Nil[A]())((acc, h) => h :: acc)

  def mapTail[B](f: A => B): List[B] =
    foldLeft(Nil[B]())((acc, h) => f(h) :: acc).reverse

@main def play =
  val l = List(10, 20, 31, 40, 50)
  println(l.size())          // 5
  println(l)                 // |10|20|31|40|50|  (toString via foldLeft)
  println(l.reverse)         // |50|40|31|20|10|
  println(l.mapTail(_ + 1))  // |11|21|32|41|51|
  println(l.map(_ + 1))      // |11|21|32|41|51|
  println(l.concat(l))       // |10|20|31|40|50|10|20|31|40|50|
  println(l.foldLeft(0)((b, a) => b + a))           // 151
  println(l.foldLeft(false)((b, a) => b || a == 30)) // false: 31 is not 30

foldLeft combines the accumulator with the head before recursing, so the recursive call is the last action and @tailrec compiles it to a loop. foldRight must first fold the tail and only then combine it with the head, so each element keeps a stack frame open until the recursion returns. On List(10, 20, 30) with + and 0:

• foldLeft: 0 + 10 = 10, then 10 + 20 = 30, then 30 + 30 = 60. The result is ((0 + 10) + 20) + 30, with the parentheses nesting on the left.
• foldRight: 10 waits for the fold of [20, 30], which waits for that of [30], which waits for that of Nil, which is 0. On the way back: 30 + 0 = 30, 20 + 30 = 50, 10 + 50 = 60. The result is 10 + (20 + (30 + 0)), with three frames pending at the deepest point.

The difference shows in practice. With the JVM's default stack, foldLeft sums a 100,000-element list of this type without trouble, while foldRight on the same list throws StackOverflowError (a few thousand elements are fine; the exact limit depends on the stack size and on JIT warm-up, and in our runs a cold foldRight already overflowed at 7,000–10,000). For + the two results coincide because addition is associative. With :: they do not: foldRight(Nil())(_ :: _) rebuilds the list in order (|10|20|30|), while foldLeft(Nil())((acc, h) => h :: acc) reverses it (|30|20|10|). This is why map and concat use foldRight, and why reverse and the stack-safe mapTail use foldLeft. mapTail pays with two passes, fold and reverse, to use constant stack.

def zipWithValue[B](v: B): List[(A, B)] = map((_, v))

def length: Int = foldLeft(0)((n, _) => n + 1)

def indices: List[Int] =         // accumulator: (next index, reversed result)
  foldLeft((0, Nil[Int]()))((acc, _) => (acc._1 + 1, acc._1 :: acc._2))._2.reverse

def zipWithIndex: List[(A, Int)] = // right to left: indices count down from length - 1
  foldRight((length - 1, Nil[(A, Int)]()))((a, acc) => (acc._1 - 1, (a, acc._1) :: acc._2))._2

def partition(p: A => Boolean): (List[A], List[A]) =
  foldRight((Nil[A](), Nil[A]()))((a, acc) =>
    if p(a) then (a :: acc._1, acc._2) else (acc._1, a :: acc._2))

def span(p: A => Boolean): (List[A], List[A]) = // a failing element sends everything after it right
  foldRight((Nil[A](), Nil[A]()))((a, acc) =>
    if p(a) then (a :: acc._1, acc._2) else (Nil(), a :: acc._1.concat(acc._2)))

def takeRight(k: Int): List[A] =
  foldRight((0, Nil[A]()))((a, acc) => if acc._1 < k then (acc._1 + 1, a :: acc._2) else acc)._2

def collect[B](pf: PartialFunction[A, B]): List[B] =
  foldRight(Nil[B]())((a, acc) => if pf.isDefinedAt(a) then pf(a) :: acc else acc)

@main def runLab06 =
  println(List(1, 2, 3).zipWithValue("a"))                 // |(1,a)|(2,a)|(3,a)|
  println(List(1, 2, 3).length)                            // 3
  println(List("a", "b", "c").indices)                     // |0|1|2|
  println(List("a", "b", "c").zipWithIndex)                // |(a,0)|(b,1)|(c,2)|
  println(List(5, 2, 3, 4).partition(_ % 2 == 0))          // (|2|4|,|5|3|)
  println(List(2, 4, 3, 6).span(_ % 2 == 0))               // (|2|4|,|3|6|)
  println(List(1, 2, 3, 4).takeRight(2))                   // |3|4|
  println(List(1, 2, 3, 4).collect { case x if x % 2 == 0 => x * 10 }) // |20|40|

4. What changes when the list is mutable?

An idiomatic mutable list is an object holding an optional pair (head, tail), with the invariant that an empty head means an empty tail. It cannot be an algebraic data type. An ADT value is one fixed case forever, whereas a mutable list must turn from empty into non-empty in place while keeping its identity. The structure is therefore a trait, plus a companion object that hides the implementation:

trait MutableList[A]:
  def head: Option[A]
  def tail: Option[MutableList[A]]
  def prepend(h: A): MutableList[A]
  def append(l: MutableList[A]): MutableList[A]
  def map[B](f: A => B): MutableList[B]
  def toList: List[A]

object MutableList:

  def apply[A](): MutableList[A] = MutableListImpl(None)

  private case class MutableListImpl[A](
      var ht: Option[(A, MutableList[A])]) extends MutableList[A]:

    override def head: Option[A] = ht.map(_._1)

    override def tail: Option[MutableList[A]] = ht.map(_._2)

    override def prepend(h: A): MutableList[A] =
      ht = Some((h, MutableListImpl(ht)))
      this

    override def append(l: MutableList[A]): MutableList[A] =
      ht match
        case None if l.head.isEmpty => {}                    // [],[] --> []
        case None => ht = Some((l.head.get, l.tail.get))     // [],[H|T] --> [H|T]
        case Some((h, t)) if t.head.isEmpty => ht = Some((h, l)) // [H],L --> [H|L]
        case Some((h, t)) => ht = Some((h, t.append(l)))     // [H|T],L --> [H|T.append(L)]
      this

    override def map[B](f: A => B): MutableList[B] =
      MutableListImpl(ht.map((h, t) => (f(h), t.map(f))))

    override def toList: List[A] = ht match
      case None => List()               // here List is scala's own list
      case Some((h, t)) => h :: t.toList

object TestMutableList extends App:
  val l: MutableList[Int] = MutableList()
  l.prepend(40).prepend(30).prepend(20).prepend(10)
  println(l.toList)          // List(10, 20, 30, 40)
  println(l.head)            // Some(10)
  println(l.tail.get.toList) // List(20, 30, 40)
  val l2: MutableList[Int] = MutableList()
  l2.prepend(60).prepend(50)
  l.append(l2)               // what would happen with l.append(l)???
  println(l.toList)          // List(10, 20, 30, 40, 50, 60)
  println(l.map(_ + 1).toList) // List(11, 21, 31, 41, 51, 61)

prepend moves the old content into a fresh node and stores the new pair in this, so the list object keeps its identity. append walks to the last node and links l there, with one case for each shape of the two lists ([], [H], [H|T]). Both return this, so calls can be chained fluently. The signatures are those of the immutable version, so in principle mutable and immutable lists could share an interface, but the implementation is trickier. (The deck's toList returns the lesson's own enum list; here it returns Scala's.)

The slide asks what l.append(l) would do. The last node of l is linked to l itself, so the list becomes a cycle and every traversal runs forever:

object SelfAppend extends App:
  val l: MutableList[Int] = MutableList()
  l.prepend(20).prepend(10)
  l.append(l)                // the last node now points back to l itself
  println(l.tail.get.tail.get.head) // Some(10): after 10, 20 comes 10 again
  println(try l.toList catch case _: StackOverflowError => "StackOverflowError")

With the immutable list the same call just builds a longer list. The aliasing problem cannot arise, because nothing can be changed through a shared reference.

Immutability and performance

Mutable structures are faster when they change often. Well-designed immutable structures still update in logarithmic time by sharing most of the old structure (immutable red-black trees, or Vector). The simplest case is 5 :: l, which allocates one node and reuses all of l. Immutable collections are also thread-safe, can be shared freely, and are easy to query with pipelines of operations. Side effects on mutable structures can be tricky, as the cycle above shows.

5. How is the collection framework organised?

The standard library's collection framework (reference: the "Collections" chapter of the Scala 3 book) declares six goals: easy, concise, safe, fast, parallel, universal. Its traits live in scala.collection and every abstraction exists in two versions, in scala.collection.immutable and scala.collection.mutable.

• IterableOnce declares little more than the abstract iterator method. Iterable adds the template methods (map, flatMap, fold, …) on top of it.
• Seq models sequences, roughly Java's lists. A LinearSeq optimises head and tail, an IndexedSeq optimises apply (indexing) and length.
• Set models collections without duplicates, Map key-value pairs, and a view is a lazy Iterable (below).

Joining the framework

A class becomes a full collection by extending Iterable and implementing only iterator. The hundred or so template methods (map, filter, sum, toList, …) then come for free:

object WorkingWithIterable extends App:

  class Fibonacci(n: Int) extends Iterable[Int]:
    override def iterator: Iterator[Int] = new Iterator[Int]():
      var counter = 0
      var prev = (0, 1)
      override def next(): Int =
        prev = (prev._2, prev._1 + prev._2)
        counter = counter + 1
        prev._1
      override def hasNext: Boolean = counter <= n

  val fibs = Fibonacci(10)
  println(fibs.toList)    // List(1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89)
  println(fibs.map(i => s"<$i>").take(3)) // List(<1>, <1>, <2>)
  println(fibs.filter(_ % 2 == 0).sum)    // 44
  println(fibs)           // Iterable(1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89)

Since hasNext tests counter <= n, Fibonacci(10) yields eleven numbers.

Aliases and default implementations

Without any import, Iterable, Seq, IndexedSeq, Set, Map and List are aliases for the immutable versions. Set means scala.collection.immutable.Set, and so on (aliases are made with the type construct of lesson 7). Mutable collections must be named explicitly. Each trait's companion has a varargs apply that picks a default implementation, visible through getClass:

object Collections extends App:
  def print[A](coll: Iterable[A]) = println(s"$coll, ${coll.getClass.getName}")

  print(Seq(10,20,30))                                   // List(10, 20, 30), ...immutable.$colon$colon
  print(scala.collection.immutable.LinearSeq(10,20,30))  // List(10, 20, 30), ...immutable.$colon$colon
  print(IndexedSeq(10,20,30))                            // Vector(10, 20, 30), ...immutable.Vector1
  print(Set(10,20,30,40,50))                             // HashSet(10, 20, 50, 40, 30), ...immutable.HashSet
  print(scala.collection.immutable.SortedSet(30,10,20))  // TreeSet(10, 20, 30), ...immutable.TreeSet
  print(Map(10 -> 11, 20 -> 21, 30 -> 31, 40 -> 41))     // Map(...), ...immutable.Map$Map4

  print(Array(10,20,30))                 // ArraySeq(10, 20, 30), ...mutable.ArraySeq$ofInt

  print(scala.collection.mutable.Seq(10,20,30))          // ArrayBuffer(10, 20, 30), ...mutable.ArrayBuffer
  print(scala.collection.mutable.IndexedSeq(10,20,30))   // ArrayBuffer(10, 20, 30), ...mutable.ArrayBuffer
  print(scala.collection.mutable.Set(10,20,30))          // HashSet(10, 20, 30), ...mutable.HashSet
  print(scala.collection.mutable.SortedSet(30,10,20))    // TreeSet(10, 20, 30), ...mutable.TreeSet
  print(scala.collection.mutable.Map(10 -> 11, 20 -> 21)) // HashMap(10 -> 11, 20 -> 21), ...mutable.HashMap

Immutable Seq and LinearSeq give a List; a non-empty list's class is :: ($colon$colon on the JVM), the same trick as section 2. IndexedSeq gives a Vector, Set a HashSet and Map a HashMap, except that sets and maps of up to four elements use the special classes Set1…Set4 and Map1…Map4. The mutable Seq and IndexedSeq give an ArrayBuffer. An Array used as a collection is wrapped in a mutable.ArraySeq. (The deck's summary slide says WrappedArray, which is the Scala 2.12 name.)

6. How do you use the main collections?

Each block below is one of the deck's examples, run with Scala 3.3.6; the comments show the actual output. Where the deck's comments differ (older library versions print Set(…) where 2.13+ prints HashSet(…), for instance), the comments here follow the real run.

Lists and list buffers

object UseLists extends App:
  // List is an immutable linear sequence, optimising head and tail access
  val l: List[Int] = List(10,20,30,40,50)  // works without imports
  println(l.getClass)    // class scala.collection.immutable.$colon$colon
  println(l.isInstanceOf[scala.collection.immutable.List[?]]) // true
  println(l.reverse)     // List(50, 40, 30, 20, 10)
  println(l.zipWithIndex) // List((10,0), (20,1), (30,2), (40,3), (50,4))
  println(l.splitAt(3))  // (List(10, 20, 30),List(40, 50)): a tuple
  println(l(2))          // 30
  println(5 :: l)        // List(5, 10, 20, 30, 40, 50)
  println(l ::: l)       // List(10, 20, 30, 40, 50, 10, 20, 30, 40, 50)
  println(l :+ 51)       // List(10, 20, 30, 40, 50, 51)
  println((l :+ 11).sortWith(_ < _))         // List(10, 11, 20, 30, 40, 50)
  println(l collect { case i if i > 20 => i + 1 }) // List(31, 41, 51)
  println(List.range(0, 10))      // List(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
  println(List.iterate(0, 5)(_ + 3)) // List(0, 3, 6, 9, 12)

  // working with mutable lists: a buffer for lists
  import scala.collection.mutable.ListBuffer
  val fruits = ListBuffer[String]()  // mutable buffer to list
  fruits += "Apple"                  // means: fruits.+=("Apple")
  fruits += "Banana"
  fruits += ("Strawberry", "Kiwi")   // deprecated since 2.13: prefer ++= List(...)
  fruits -= "Apple"
  println(fruits)                    // ListBuffer(Banana, Strawberry, Kiwi)
  println(fruits.toList)             // List(Banana, Strawberry, Kiwi)

::: concatenates and :+ appends, both returning new lists. collect takes a partial function and filters and maps in one pass. l(2) works, but on a linear sequence it costs linear time. ListBuffer is the mutable buffer used to build a list incrementally before calling toList. Its += is a method call (fruits.+=("Apple")).

Lazy lists

object UseLazyLists extends App:
  val s: LazyList[Int] = LazyList(10,20,30,40,50)
  println(s.getClass)  // class scala.collection.immutable.LazyList
  println(s)           // LazyList(<not computed>)
  println(s(2))        // 30
  println(s)           // LazyList(10, 20, 30, <not computed>)
  val s2 = s.zipWithIndex
  println(s2)          // LazyList(<not computed>)
  println(s2(2))       // (30,2)
  println(s2)          // LazyList((10,0), (20,1), (30,2), <not computed>)
  println(s.toList)    // List(10, 20, 30, 40, 50)
  println(s)           // LazyList(10, 20, 30, 40, 50)

A LazyList computes elements only when they are needed and memoises them: s(2) forces the first three, and toList forces the rest. Operations such as zipWithIndex build another unevaluated lazy list.

Vectors, arrays and array buffers

object UseVectorsArrays extends App:
  // Vector is the default immutable indexed sequence
  val v: Vector[Int] = Vector(10,20,30,40,50)
  println(v.getClass)  // class scala.collection.immutable.Vector1
  println(v.reverse)   // Vector(50, 40, 30, 20, 10): all List operations work
  println(v(2))        // 30

  // scala.Array is backed by a Java array: mutable, with constant length
  val a: Array[Int] = Array(10,20,30)
  println(a)           // [I@<hash>: Java's toString
  println(a.getClass)  // class [I, namely an int[]
  println(a.reverse.toList) // List(30, 20, 10): all List operations work
  a(0) = 99            // in-place update
  println(a.mkString(",")) // 99,20,30

  import collection.*
  // ArrayBuffer is the default (fully) mutable indexed sequence
  val b: mutable.ArrayBuffer[Int] = mutable.ArrayBuffer[Int]()
  println(b.getClass)  // class scala.collection.mutable.ArrayBuffer
  b.addAll(List(10,20,30,40))
  println(b)           // ArrayBuffer(10, 20, 30, 40)
  println(b.toVector)  // Vector(10, 20, 30, 40): to an immutable sequence

Vector is the default immutable indexed sequence, with effectively constant-time indexing and updates. Array is a real Java array (class [I is int[]): mutable, fixed length, printed with Java's toString, yet every sequence operation works on it through an implicit wrapper. ArrayBuffer is the default fully mutable indexed sequence.

Sets and maps

object UseSets extends App:
  // an immutable set: no sequencing and no duplicates
  val s: Set[Int] = Set(10,20,30,40,50)
  println(s.getClass)       // class scala.collection.immutable.HashSet
  println(s)                // HashSet(10, 20, 50, 40, 30)
  println(s + 60 + 70)      // HashSet(10, 20, 60, 70, 50, 40, 30)
  println(s & Set(10,30))   // HashSet(10, 30): intersection
  println(s.contains(10))   // true

  import collection.*
  val b: mutable.Set[Int] = mutable.Set(10,20,30)  // a mutable HashSet
  println(b.getClass)       // class scala.collection.mutable.HashSet
  b += 40                   // means b.+=(40)
  b += 40                   // no effect: already there
  println(b)                // HashSet(40, 10, 20, 30)

object UseMaps extends App:
  // an immutable map, i.e., a key-value store
  val m: Map[Int, String] = Map(10 -> "a", 20 -> "b", 30 -> "c")
  println(m.getClass)  // class scala.collection.immutable.Map$Map3
  println(m)           // Map(10 -> a, 20 -> b, 30 -> c)
  println(m.toVector)  // Vector((10,a), (20,b), (30,c))
  println(m.values)    // Iterable(a, b, c)
  println(m.keys)      // Set(10, 20, 30)
  println(m(10))       // a
  println(m.get(40))   // None: the safe lookup
  println(m.map { case (k, v) => (v, k + ".") }) // Map(a -> 10., b -> 20., c -> 30.)
                                                 // (Int + String is deprecated: s"$k." is preferred)
  println(m.map { case (k, v) => v + v })        // List(aa, bb, cc)

  import collection.*
  val mm: mutable.Map[Int, String] = mutable.Map[Int, String]()
  println(mm.getClass) // class scala.collection.mutable.HashMap
  mm += (10 -> "a")
  mm += (20 -> "b")
  mm += (30 -> "c")
  println(mm)          // HashMap(20 -> b, 10 -> a, 30 -> c)

A set has no order and no duplicates, so the printed order is the hash order, and adding 40 twice changes nothing. k -> v is just a pair (k, v). m(10) throws if the key is missing, while m.get(10) returns an Option. Mapping a map to pairs gives a map again, and mapping it to anything else gives an Iterable.

Options

object UseOption extends App:
  val some: Option[Int] = Some(10)
  val none: Option[Int] = None

  println(some.isDefined)        // true
  println(some.fold(-1)(_ + 1))  // 11
  println(none.fold(-1)(_ + 1))  // -1
  println(some map (_ + 1))      // Some(11)
  println(none map (_ + 1))      // None
  println(some filter (_ > 0))   // Some(10)
  println(Some(-5) filter (_ > 0)) // None

  println(some.flatMap(x => if x > 0 then Some(1) else None)) // Some(1)
  println(some.flatMap(x => Some(1) filter (i => x > 0)))     // Some(1): better than the above
  println(none.flatMap(x => Some(0) filter (i => x > 0)))     // None

  val some2: Option[Int] = Some(20)
  println(some flatMap (x => some2 flatMap (y => Some(x * y)))) // Some(200)
  println(for x <- some; y <- some2 yield x * y)               // Some(200): the same, as a for

Option is "somewhat part" of the framework: a collection of zero or one elements with map, filter, flatMap and fold. The idiom is to chain these calls and leave the empty case to them instead of testing isDefined. The last line shows that the nested flatMap is exactly what a for over options means.

Views

object Views extends App:
  val list = collection.mutable.ListBuffer(10, 20, 30, 40)
  val view = list.view

  println(view)                    // SeqView(<not computed>)
  println(view.map(_ + 1))         // SeqView(<not computed>)
  println(view.map(_ + 1).toList)  // List(11, 21, 31, 41)

  list.addOne(50)
  println(list)                    // ListBuffer(10, 20, 30, 40, 50)
  println(view.toList)             // List(10, 20, 30, 40, 50): the view sees the change
  // view.addOne(60)               // does not compile: a view has no mutators

A view is another Iterable: a lazy, immutable representation of a collection. Transformations on it are not computed until it is traversed or converted. It has no mutating methods, but it reads the underlying collection live, so it sees changes made to a mutable one. That makes it the right way to expose a private mutable collection read-only (section 7).

7. How should a mutable domain concept be organised?

A logger is naturally stateful: it accumulates strings. The deck writes it three ways and asks which is better:

// a mutable class, using a mutable val
class Logger:
  private val strings = collection.mutable.ListBuffer[String]()
  def log(string: String): Unit = strings.addOne(string)
  def getLog: Iterable[String] = strings.view // a lazy, immutable wrapper

// a mutable class, using an immutable var
class Logger2:
  private var strings = Seq[String]() // a List
  def log(string: String): Unit = strings = strings :+ string
  def getLog: Iterable[String] = strings

// an immutable class, using an immutable val
class Logger3 private (private val strings: List[String]):
  def this() = this(List[String]())
  def log(string: String): Logger3 = Logger3(strings :+ string)
  def getLog: Iterable[String] = strings.view // a lazy, immutable wrapper

object TryLogger extends App: // which one is better??
  val logger = new Logger()
  logger.log("str1")
  logger.log("str2")
  logger.getLog foreach (println(_))  // str1 str2

  var logger3 = new Logger3()
  logger3 = logger3.log("str1")
  logger3 = logger3.log("str2")
  logger3.getLog foreach (println(_)) // str1 str2

The rule behind the table is "always put side-effects outwards: the core should be declarative". In case 3 the mutation has not disappeared: it moved to the client, which reassigns var logger3. Logger3 also shows a private primary constructor with a public auxiliary one, so clients can only start from an empty log. Case 2 beats case 1 for a reason the next run makes concrete. Logger.getLog returns a view of the private buffer, which is read-only but live, while Logger2.getLog returns the immutable sequence itself, a true snapshot:

object Leak extends App:
  val logger = new Logger()
  logger.log("a")
  val snapshot = logger.getLog     // a view over the private buffer
  logger.log("b")
  println(snapshot.toList)         // List(a, b): the "snapshot" changed under our feet
  val logger2 = new Logger2()
  logger2.log("a")
  val snapshot2 = logger2.getLog   // the immutable Seq itself
  logger2.log("b")
  println(snapshot2.toList)        // List(a): a true snapshot
  // snapshot.asInstanceOf[collection.mutable.ListBuffer[String]] would fail:
  println(snapshot.isInstanceOf[collection.mutable.Buffer[?]]) // false: callers cannot mutate

With case 2 the class state is still mutable, but every value that escapes is immutable, so it can be shared, stored and iterated without surprises. Lab 06's second exercise, a small management application ported from a Java exam, applies these guidelines.

8. How do constructs, packages and imports nest?

Scala is scalable because its constructs nest arbitrarily: class (a template for objects), abstract class (a partial template), object (a singleton or module), trait (a mixin or interface) and def (a method). Packages nest too and behave much like objects. Common nestings are:

• anything inside an object (for instance one extending App);
• classes inside classes, like Java inner classes, and the basis of family polymorphism;
• classes inside objects, like Java static nested classes;
• methods inside methods, frequent with recursive helpers;
• anonymous classes inside methods, as local helpers.

object Constructs extends App:
  // nestable constructs
  class C
  abstract class D
  object O
  trait T
  def f(): Unit = {}

  val d = new D() {}   // essentially, anonymous classes
  val t = new T {}     // essentially, anonymous classes

  // nestable constructs with some content (in Scala 2 syntax)
  class C2 { def a: Int = 1 }
  abstract class D2 { def b: Int }
  object O2 { def c: Int = 3 }
  trait T2 { def d(): Int }   // a function interface
  def f2(): Unit = print("hello")
  val d2 = new D2():          // anonymous class, Scala 3 syntax
    override def b = 2
  val t2: T2 = () => 4        // Java-like fill of a functional interface

  println(s"${new C2().a}, ${d2.b}, ${O2.c}, ${t2.d()}") // 1, 2, 3, 4

new D() {} instantiates an anonymous subclass. A trait with a single abstract method, like T2, can be filled with a lambda, as with Java functional interfaces.

Inner classes and local functions

object Inner extends App:
  class C(var v: Int):
    class D:
      def g(n: Int): Int =
        n + C.this.v       // using the outer instance

  val c: C = new C(5)      // enclosing instance
  println(new c.D().g(4))  // 9

  object O:
    var v: Int = 10
    class D:               // a "static" nested class
      def g(n: Int): Int =
        n + O.v

  println(new O.D().g(4))  // 14

A class nested in a class belongs to an enclosing instance: it is created as new c.D() and reaches the outer fields as C.this.v. A class nested in an object needs no instance, like a Java static nested class. In Scala the type of an inner class depends on its instance: c1.D and c2.D are different types (a path-dependent type), and C#D means "a D of any C":

object PathDependent extends App:
  class C(var v: Int):
    class D:
      def g(n: Int): Int = n + C.this.v
  val c1 = new C(1)
  val c2 = new C(100)
  val d1: c1.D = new c1.D()
  // val wrong: c2.D = new c1.D()   // type mismatch: c1.D is not c2.D
  val any: C#D = d1                 // C#D: a D of any C
  c1.v = 50
  println(d1.g(1))                  // 51: d1 reads its own outer instance

object Anonymous extends App:
  trait Comparator[A]:
    def compare(a: A, b: A): Int

  // a function inside a function
  def min[A](list: List[A], comp: Comparator[A]): Option[A] =
    @annotation.tailrec
    def min2(list: List[A], minSoFar: A): A = list match
      case h :: t if comp.compare(h, minSoFar) > 0 => min2(t, minSoFar)
      case h :: t => min2(t, h)
      case _ => minSoFar
    // if list.isEmpty then None else Some(min2(list.tail, list.head))
    Some(list) filter (!_.isEmpty) map (l => min2(l.tail, l.head))

  // instantiating an anonymous class
  val comp = new Comparator[Int]():
    override def compare(a: Int, b: Int): Int = a - b

  println(min(List(10, 20, 5, 40), comp))   // Some(5)
  println(min(List(), comp))                // None
  println(min(List(10, 20, 5, 40), _ - _))  // Some(5): a lambda fills the functional interface

min hides its tail-recursive helper inside itself, where it can see comp without passing it along. The final expression turns "empty or not" into an Option without an if. The comparator is an anonymous class, or just a lambda.

Packages

Scala packages are fully compatible with Java's, but a source file need not sit in a directory matching its package. One file can open several packages as namespaces (as in C#), and Scala 3 allows top-level vals and defs directly in a package:

package u06.pack  // the package of all definitions below

val v1 = 1        // a top-level val: when is it initialised?

package a:        // entering a subpackage as a namespace
  object O1
  package b:      // entering a further subpackage as a namespace
    def f2() = 1
    object O2
    object A:     // I keep nesting stuff
      object O3
      object B:
        object O4
        class C:
          println(s"$O1,$O2,$O3,$O4,$A,$B") // note visibility of everything above
          println(s"${u06.pack.a.b.A.B.O4}") // full qualification
        def f(): Unit =
          println(s"$v1,${f2()},${new C}")

package a:        // re-entering package u06.pack.a
  object O1B:
    val v = O1    // using u06.pack.a.O1

object Packages extends App:
  println(u06.pack.a.b.A.B.O4)   // u06.pack.a.b.A$B$O4$@<hash>
  println(u06.pack.a.O1B.v)      // u06.pack.a.O1$@<hash>
  u06.pack.a.b.A.B.f()

Code inside C sees O1, O2, A, B and the rest without qualification, because being nested in a package or object means having its definitions in scope. A package can be re-opened later (the second package a:). (The deck's version also calls f() from C's body and new C from f, a mutual recursion that never terminates if either is used; it is cut here.)

Imports

package u06.structure

package p1:
  package p2:
    object O:
      val v = 1

object Import extends App:
  println(u06.structure.p1.p2.O.v) // full qualification
  println(p1.p2.O.v)               // relative qualification

  import p1.*                      // importing u06.structure.p1
  println(p2.O.v)

  import p2.*                      // the same as: import u06.structure.p1.p2.*
  println(O.v)

  import u06.structure.p1.p2.O.*   // "static import" of O's members
  println(v)

  import u06.structure.p1.p2.{O => TheObject} // alias (Scala 3 also: O as TheObject)
  println(TheObject.v)

  import scala.collection.mutable.{Seq => MutableSeq} // renaming Seq
  println(s"${Seq(10,20,30)}, ${MutableSeq(10,20,30)}") // List(10, 20, 30), ArrayBuffer(10, 20, 30)

Imports can appear anywhere, which keeps them close to their use. They can bring in a whole package, one or more members, or the members of an object or value (a "static import"), and they can rename, which helps when two packages export the same name. scala.*, java.lang.* and scala.Predef.* are always imported; Predef provides println, ??? and the Map and Set aliases; List, Seq, IndexedSeq, Iterable and the other collection aliases live in the scala package object.

At any point of the code, then, the visible identifiers are those of every enclosing package and object, the imports written so far, and the default imports. Imports control which methods, objects, classes and types you can name, and also which given instances and extension methods are available (lesson 7). Access modifiers then restrict this set further.

9. Who can see what?

Public is the default and not a keyword. A class and its companion object share even their private members. The levels are:

package u06.structure

package pa1:
  package pa2:

    class C:
      private object pri            // visible only by C's instances (and object C)
      private[pa2] object pri_pa2   // visible only up to pa2
      protected object pro          // visible to subclasses
      protected[pa2] object pro_pa2 // visible to subclasses, or up to pa2
      def f(c: C) =
        print(C.g())                // WORKS: can see the companion's private stuff

    object C:
      print(new C().pri)            // WORKS: can see the class' private stuff
      private def g() = 1

    class D extends C:
      //print(pri)                  // ERROR: private is not inherited-visible
      print(pro)                    // WORKS: subclass

    class E(c: C):
      //print(c.pri, c.pro)         // ALL ERRORS
      print(c.pri_pa2, c.pro_pa2)   // WORKS: same package pa2
  end pa2

  class F extends pa2.C:
    //print(pri_pa2)                // ERROR: outside pa2
    print(pro_pa2)                  // WORKS: subclass
end pa1

Each commented line was compiled on its own. c.pri from E fails with "private object pri can only be accessed from class C", and c.pro with "protected object pro can only be accessed from class C … or one of its subclasses". pri_pa2 from F fails because F is in pa1, outside pa2. pro_pa2 works there because F is a subclass.

private is less common than in Java, for three reasons. The pattern "private field plus public getter" is unnecessary with uniform access: a public val is already read-only, and it can later become a def without changing clients. Private helpers used by a single public method can be nested inside it. And instead of scattering many private members, you can gather them in one private nested abstraction:

class C2: // many private helpers, refactored into one private nested object
  import ImplementationHelpers.*   // to ease the calls

  def f(): Unit =
    g1()
    g2()

  private object ImplementationHelpers:
    def g1(): Unit = println("g1")
    def g2(): Unit = println("g2")

Qualified privacy also gives a clean factory pattern. The implementation's constructor is visible only inside the package, so clients must go through the trait's companion:

trait Counter:
  def increment(): Unit
  def getValue(): Int

object Counter:
  def apply(): Counter = new CounterImpl

class CounterImpl private[structure] () extends Counter:
  var count = 0
  override def increment(): Unit = count += 1
  override def getValue(): Int = count

object TryCounters extends App:
  val c = Counter()
  c.increment()
  println(c.getValue())  // 1
  println(c)             // u06.structure.CounterImpl@<hash>

From another package, new u06.structure.CounterImpl() is rejected: "private[structure] constructor CounterImpl can only be accessed from package u06.structure". Java's package-private default is not optimal either. In Scala the level of accessibility is a design decision to be taken explicitly for each abstraction, together with what to put in each source file, how to nest it, and what scope the client code should get.

Check your understanding