Advanced Scala: types, mixins, variance, contextual abstractions

1. What are abstract types and aliases for?

A trait or abstract class can declare an abstract type member, type T or the bounded type T <: R. A subclass must make it concrete, type T = R, before objects can be created. This is type parameterisation where the abstracted types are members instead of parameters in brackets, and a type member can itself be generic (type MySeq[T] = List[T]). It has three uses:

1. aliases, possibly abstract and made concrete in subclasses. This is like import renaming, but it also works for generic types;
2. abstract modelling of the concepts of a domain, as with ADTs;
3. path-dependent types, the basis of family polymorphism, discussed at the end of the course.

The collection aliases of lesson 6 are defined this way: Map and Set in scala.Predef (below), List, Seq and the others in the scala package object.

// an extract of scala.Predef
class Predef:
  type Class[T] = java.lang.Class[T]
  type Function[-A, +B] = (A) => B
  type Map[A, +B] = collection.immutable.Map[A, B]
  type Set[A] = collection.immutable.Set[A]
  type String = java.lang.String

An alias is often paired with a same-named factory method, so that the new name works both as a type and as a constructor. The deck's version has a bug worth seeing, because it compiles and runs:

// aliases and corresponding constructors, as in the deck
object MyAliases:
  type MySeq[T] = collection.immutable.Vector[T]
  def MySeq[T](elems: T*) = collection.immutable.Vector(elems)
  type MySet[T] = collection.immutable.HashSet[T]
  def MySet[T](elems: T*) = collection.immutable.HashSet(elems)
  type MyMap[A, +B] = collection.immutable.HashMap[A, B]
  def MyMap[A, B](elems: (A, B)*) = collection.immutable.HashSet(elems)

object Aliases extends App:
  import MyAliases.*
  val seq = MySeq(10, 20, 30)
  println(s"$seq, ${seq.getClass}")
  val set = MySet(10, 20, 30)
  println(s"$set, ${set.getClass}")
  val map = MyMap(10 -> "a", 20 -> "b", 30 -> "c")
  println(s"$map, ${map.getClass}")

It prints Vector(ArraySeq(10, 20, 30)), HashSet(ArraySeq(10, 20, 30)) and HashSet(ArraySeq((10,a), (20,b), (30,c))). Vector(elems) passes the varargs sequence as one element, and MyMap builds a HashSet. Since the factories have no declared result type, the compiler cannot catch either mistake. The fix is to spread the arguments with elems* and to declare the result types:

object MyAliasesFixed:
  type MySeq[T] = collection.immutable.Vector[T]
  def MySeq[T](elems: T*): MySeq[T] = collection.immutable.Vector(elems*)
  type MySet[T] = collection.immutable.HashSet[T]
  def MySet[T](elems: T*): MySet[T] = collection.immutable.HashSet(elems*)
  type MyMap[A, +B] = collection.immutable.HashMap[A, B]
  def MyMap[A, B](elems: (A, B)*): MyMap[A, B] = collection.immutable.HashMap(elems*)

object AliasesFixed extends App:
  import MyAliasesFixed.*
  val seq: MySeq[Int] = MySeq(10, 20, 30)
  println(seq)   // Vector(10, 20, 30)
  val set = MySet(10, 20, 30)
  println(set)   // HashSet(10, 20, 30)
  val map = MyMap(10 -> "a", 20 -> "b", 30 -> "c")
  println(map)   // HashMap(10 -> a, 20 -> b, 30 -> c)

The Exams case study

Abstract types let one trait describe a whole system. Exams leaves students, teachers, courses and evaluations abstract, defines the concepts built on them, and declares the operations:

trait Exams:
  // abstracted types
  type Student
  type Teacher
  type Course
  type Evaluation
  trait Session:
    def id: Int

  // defined types
  case class Exam(course: Course, session: Session, student: Student)
  type Registration = (Exam, Evaluation)

  // methods
  def register(registration: Registration): Unit
  def evaluation(student: Student, course: Course): Evaluation

abstract class AbstractExams extends Exams:
  private var registrations: Set[Registration] = Set()

  override def register(registration: Registration) =
    registrations = registrations + registration

  override def evaluation(student: Student, course: Course) =
    registrations
      .collect:
        case (Exam(`course`, call, `student`), eval) => (call.id, eval)
      .maxBy(_._1)._2

AbstractExams implements the operations without knowing any concrete type. It keeps the registrations in a private immutable var, the guideline of lesson 6. evaluation uses collect with a pattern in which the backquoted `course` and `student` match the values of the parameters (without backquotes they would be fresh variables matching anything), while call binds the session. maxBy then selects the latest session. A last class fixes the types:

class BasicExamsImpl extends AbstractExams:
  override type Student = String
  override type Teacher = String
  override type Course = String
  override type Evaluation = Int

  case class SessionWithId(id: Int) extends Session
  def session(id: Int): Session = SessionWithId(id)

object WorkWithExams extends App:
  val exams = new BasicExamsImpl()
  exams.register((exams.Exam("oop", exams.session(0), "mirko"), 20))
  exams.register((exams.Exam("oop", exams.session(1), "mirko"), 25))
  exams.register((exams.Exam("sisop", exams.session(0), "mirko"), 30))

  println(exams.evaluation("mirko", "oop"))   // 25: the latest session wins
  println(exams.evaluation("mirko", "sisop")) // 30

object ExamsExtra extends App:
  val exams = new BasicExamsImpl()
  exams.register((exams.Exam("oop", exams.session(0), "mirko"), 20))
  println(scala.util.Try(exams.evaluation("mirko", "pps")))
  // Failure(java.lang.UnsupportedOperationException: empty.maxBy)
  val other = new BasicExamsImpl()
  // exams.register((other.Exam("oop", other.session(0), "luca"), 18)) // type mismatch

Two details. Exam is a class nested in the system, so exams.Exam and other.Exam are different path-dependent types, and the compiler rejects registering one system's exam in another ("Found: other.Exam, Required: exams.Exam"). And maxBy on an empty set throws, so a student with no exam for the course makes evaluation fail. Returning Option[Evaluation] would be the idiomatic fix.

The deck calls this the approach to complex abstractions: define a system as a trait of concepts, then refine it step by step. It is hard to reproduce in mainstream languages. Three techniques extend it: mixins to compose a system from several "slices" (section 3), self-types to let a slice declare what it expects without inheriting it (section 4), and family polymorphism for mutually dependent concepts.

2. Trait or abstract class?

Traits serve five purposes: abstract concepts (Java-like interfaces with only methods); rich interfaces, with a few abstract methods and many template methods derived from them (Iterable is the prime example); interfaces for strategies and type classes, such as Ordered[T] or any FunctionN type like (Int, Double) => String; class templates, partial classes extended many times; and stackable modifications, the key mixin property (next section).

Rich interfaces

case class Point(x: Int, y: Int)

trait Rectangular:
  // abstract methods
  def topLeft: Point
  def bottomRight: Point
  // template methods
  def left: Int = topLeft.x
  def right: Int = bottomRight.x
  def top: Int = topLeft.y
  def bottom: Int = bottomRight.y

case class Rectangle(
  override val topLeft: Point,
  override val bottomRight: Point) extends Rectangular

object TryRichInterface extends App:
  val r = Rectangle(Point(0, 0), Point(10, 20))
  println(s"${r.left},${r.right}")  // 0,10
  println(s"${r.top},${r.bottom}")  // 0,20

A Rectangle implements the two abstract methods, here directly as constructor fields with override val, and gets left, right, top and bottom for free. The same idea is behind Ordered: one abstract comparison, four derived operators. The deck's simplified version extends Java's Comparable, so Java's own sorting accepts it:

trait Ordered[T] extends Comparable[T]:  // a simplified scala.math.Ordered
  def compareTo(that: T): Int
  def <(that: T): Boolean = (this compareTo that) < 0
  def >(that: T): Boolean = (this compareTo that) > 0
  def <=(that: T): Boolean = (this compareTo that) <= 0
  def >=(that: T): Boolean = (this compareTo that) >= 0

case class MyInt(n: Int) extends Ordered[MyInt]:
  override def compareTo(that: MyInt) = this.n - that.n

object TryOrdered extends App:
  println(MyInt(5) < MyInt(7))   // true
  println(MyInt(5) <= MyInt(7))  // true
  println(MyInt(5) > MyInt(7))   // false
  println(MyInt(5) >= MyInt(7))  // false
  // a Java Comparable, so Java's sorting works too:
  val l = java.util.ArrayList[MyInt](java.util.List.of(MyInt(3), MyInt(1), MyInt(2)))
  java.util.Collections.sort(l)
  println(l)                     // [MyInt(1), MyInt(2), MyInt(3)]

In the library, scala.math.Ordered[T] plays the role of Java's Comparable (the ordering is part of the object), while scala.math.Ordering[T] plays the role of Comparator (a separate strategy object). Ordering comes back as a type class in section 8.

3. How do mixins stack?

A mixin is a unit of code, possibly partially implemented, that is combined with other mixins to form a class. The class must provide whatever the mixins leave missing. Mixins are "included" or "stacked in" rather than inherited: they give reuse, not necessarily substitutability. Scala traits work as mixins, a class can extend several of them, and inside a trait super behaves specially, so that traits can be chained by composition as well as by inheritance.

abstract class Parser[T]:
  def parse(t: T): Boolean  // accept the token! did it work?
  def end: Boolean          // tokens are over! is this ok?
  def parseAll(seq: Seq[T]): Boolean = (seq forall (parse(_))) & end // could use & or &&

// a parser consuming any sequence of elements in `chars`
case class BasicParser(chars: Set[Char]) extends Parser[Char]:
  override def parse(t: Char) = chars contains t
  override def end = true

// a mixin rejecting empty strings (see: a sort of decorator!)
trait NonEmpty[T] extends Parser[T]:
  private var empty = true
  abstract override def parse(t: T) = { empty = false; super.parse(t) } // who is super??
  abstract override def end = !empty && super.end

class NonEmptyBasicParser(chars: Set[Char]) extends BasicParser(chars) with NonEmpty[Char]

object TryParsers extends App:
  println(BasicParser(Set('a','b','c')).parseAll("aabc".toList))   // true
  println(BasicParser(Set('a','b','c')).parseAll("aabcdc".toList)) // false
  println(BasicParser(Set('a','b','c')).parseAll("".toList))       // true
  // NonEmpty is "stacked" on to a concrete class
  println(NonEmptyBasicParser(Set('0','1')).parseAll("0101".toList)) // true
  println(NonEmptyBasicParser(Set('0','1')).parseAll("0123".toList)) // false
  println(NonEmptyBasicParser(Set('0','1')).parseAll(List()))        // false

Parser is an abstract class with a functional template method, parseAll. BasicParser is a baseline implementation. NonEmpty is a mixable decoration that only adds the non-emptiness check, and NonEmptyBasicParser stacks it on top of BasicParser. Inside NonEmpty, super.parse does not mean Parser.parse, which is abstract. It means "whichever implementation comes next in the class this trait is eventually mixed into", which is unknown when the trait is written. Nothing like this exists in Java. The modifier abstract override says exactly that: the method overrides, but still needs a concrete implementation below it. With a plain override the compiler refuses the super call. Mixing NonEmpty into a class that has no concrete parse (such as Parser itself) is rejected too, because the class "needs to be abstract".

Linearization

On the JVM, multiple inheritance with traits is rendered by decoration, that is, inheritance plus delegation. An object of NonEmptyBasicParser is a NonEmpty decorating a BasicParser, which extends Parser. The order is fixed by the linearization of the class, a list of the class and all its ancestors in which each super refers to the next element:

L(C) = C, then the linearizations of C's parents taken from right to left and concatenated, keeping only the last occurrence of each type.

No class appears twice, and the shared ancestors sink to the end. The course's smallest example makes the order visible through a string:

trait T:
  def f: String = "T"
trait A extends T:
  val x = "A"
  override def f: String = super.f + x
trait B extends T:
  override def f: String = super.f + "B"

class C extends A with B   // linearization: C, B, A, T, AnyRef, Any

object Traits extends App:
  println(new C().f)       // TAB

The parents of C, right to left, are B (L = B, T, AnyRef, Any) and A (L = A, T, AnyRef, Any). The concatenation is B, T, AnyRef, Any, A, T, AnyRef, Any. Dropping the earlier copies leaves C, B, A, T, AnyRef, Any. So f starts in B, whose super.f is A's, whose super.f is T's: "T" + "A" + "B". The deck points to the classic example of Odersky, Spoon and Venners' book, checked here with super calls:

class Animal:
  def chain: List[String] = List("Animal")
trait Furry extends Animal:
  override def chain = "Furry" :: super.chain
trait HasLegs extends Animal:
  override def chain = "HasLegs" :: super.chain
trait FourLegged extends HasLegs:
  override def chain = "FourLegged" :: super.chain
class Cat extends Animal with Furry with FourLegged:
  override def chain = "Cat" :: super.chain

object TryCat extends App:
  println(new Cat().chain.mkString(" -> ")) // Cat -> FourLegged -> HasLegs -> Furry -> Animal

For everyday programming "things just work". Linearization matters when stacked traits override the same method, as decorations do. The calculator recomputes it for any declarations you type (Scala 2 with or Scala 3 commas; a last line new … with … makes an anonymous class), shows which copies are dropped and where each super leads, and rejects what the compiler rejects: a class in second position, cycles, and a trait whose superclass is not a superclass of the class.

trait NotTwoConsecutive[T] extends Parser[T]:
  private var last: Option[T] = None
  abstract override def parse(t: T) =
    val ok = !last.contains(t)
    last = Some(t)
    ok && super.parse(t)

class NotTwoConsecutiveParser(chars: Set[Char])
  extends BasicParser(chars) with NotTwoConsecutive[Char]

extension (s: String)             // exercise 2: a parser from a String
  def charParser(): Parser[Char] = BasicParser(s.toSet)

object TryLab extends App:
  def parserNTC = NotTwoConsecutiveParser(Set('X', 'Y', 'Z'))
  println(parserNTC.parseAll("XYZ".toList))      // true
  println(parserNTC.parseAll("XYYZ".toList))     // false
  println(parserNTC.parseAll("".toList))         // true
  def parserNTCNE = new BasicParser(Set('X', 'Y', 'Z')) with NotTwoConsecutive[Char] with NonEmpty[Char]
  println(parserNTCNE.parseAll("XYZ".toList))    // true
  println(parserNTCNE.parseAll("XYYZ".toList))   // false
  println(parserNTCNE.parseAll("".toList))       // false
  println("abc".charParser().parseAll("aabc".toList)) // true

4. What does a self-type add?

The syntax trait T { name: Type => … } declares a self-type. T can be instantiated only when mixed into something of type Type, and inside T the name name is this, typed as Type. The trait is not a subtype of Type. It is inheritance without subtyping, realised internally by decoration, and the typical way to write pure "decorations" that declare a dependency instead of inheriting it:

trait Producer:
  def get(): String

// not a subtype of Producer, but truly a mixin!
trait ProducerUtils:
  producer: Producer =>
  def getMany(n: Int): Seq[String] =
    for i <- 0 to n yield producer.get()

class RandomProducer extends Producer:
  override def get(): String = Math.random().toString

class ConstantProducer(s: String) extends Producer:
  override def get(): String = s

class FullRandomProducer extends RandomProducer with ProducerUtils

@main def tryProducers =
  // attaching utils to any Producer
  val producer = new FullRandomProducer
  val producer2 = new RandomProducer() with ProducerUtils
  val producer3 = new ConstantProducer("a") with ProducerUtils
  println(producer.getMany(2).size)  // 3: note 0 to n is inclusive
  println(producer3.getMany(2))      // Vector(a, a, a)
  // val u = new ProducerUtils {}  // error: the self-type Producer is not satisfied
  // def asProducer(u: ProducerUtils): Producer = u  // error: no subtyping

ProducerUtils can be attached to any producer, at class definition or on the fly with new … with ProducerUtils. The two commented lines were compiled separately. new ProducerUtils {} fails with "illegal inheritance: self type … does not conform to self type Producer", and treating a ProducerUtils as a Producer fails with a type mismatch. Compare trait ProducerUtils extends Producer: that version would be a producer, part of every client's view of it, whereas the self-type keeps the dependency internal.

If the type is omitted (self =>), the name is just an alias for this, useful in inner or anonymous classes where this means the inner object:

trait FunctionOption[-A, +B]:
  self =>
  def apply(a: A): Option[B]

  final def andThen[C](f: FunctionOption[B, C]): FunctionOption[A, C] =
    new FunctionOption[A, C]:
      override def apply(a: A): Option[C] =
        self.apply(a).flatMap(b => f.apply(b))
        // this.apply(a).flatMap(b => f.apply(b)) // would not compile

@main def mainFunction =
  val f: FunctionOption[Int, Int] = n => Some(n) filter (_ % 2 == 0) map (_ / 2)
  val g: FunctionOption[Int, Int] = n => Some(n + 1)

  val h: FunctionOption[Int, Int] = f andThen g
  println(h(5)) // None
  println(h(6)) // Some(4)

Inside the anonymous FunctionOption[A, C], this.apply(a) would be the new function's own apply, returning Option[C]. The compiler rejects the commented line ("Found: C, Required: B"). self names the outer function. The composed h halves even numbers and adds one: h(6) is Some(4), and h(5) fails at the first step.

5. Why prefer delegation, and what does export do?

The modern recipe is to consider delegation instead of inheritance, following the principle of least power. Inheritance opens a class too much to its subclasses and handles multiple reuse poorly. Substitutability is better obtained through traits alone, focusing on the contract. Delegation combined with fine-grained access modifiers is preferable, and its one drawback, the boilerplate of forwarding methods, is what Scala 3's export removes. Written inside a class or object with import-like syntax, an export makes members of a stable value visible from outside, by generating the forwarders:

object Exports extends App:

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

  class BasicCounter extends Counter:
    private[Exports] var counterValue = 0
    def value: Int = counterValue
    def increment(): Unit = counterValue = counterValue + 1
    def reset(): Unit = counterValue = 0

  class MultiCounter extends Counter:          // no inheritance, just substitutability
    private val counter = new BasicCounter()   // no inheritance, just delegation
    export counter.*                           // export value, increment, reset, counterValue
    def decrement(): Unit = counterValue -= 1

  class FancyCounter extends Counter:          // no inheritance, just substitutability
    private val counter = new BasicCounter()   // no inheritance, just delegation
    private val initDate = java.util.Calendar.getInstance()
    export counter.{reset as _, *}             // export all but reset
    export initDate.getTime as creationTime    // export with alias

  val c: Counter = new FancyCounter()          // no inheritance, just substitutability
  c.increment()
  c.increment()
  println(c.value)                             // 2
  val c2 = new FancyCounter()
  // c2.decrement()                            // won't compile: FancyCounter has no decrement
  // c2.reset()                                // won't compile: reset was not exported
  println(c2.creationTime().getClass)          // class java.util.Date
  val m = new MultiCounter()
  m.increment(); m.increment(); m.decrement()
  println(m.value)                             // 1

MultiCounter and FancyCounter are Counters by substitutability only: they reuse BasicCounter by delegation, with no implementation inheritance. export counter.* forwards everything accessible, including counterValue, which is private[Exports] precisely so that decrement can reach it. {reset as _, *} exports all but reset, and getTime as creationTime renames. Only exported members exist on the outside: both c2.decrement() and c2.reset() fail with "not a member of Exports.FancyCounter".

Since exports make names available to importers of the object, one object can serve as a reusable import unit:

object MyStandardExports:
  export scala.collection.mutable.{
    ListBuffer => StandardList,
    HashSet => StandardSet,
    HashMap => StandardMap
  }
  export scala.Array.*
  export java.lang.Math.*
  export java.util.Date

@main def tryExports =
  import MyStandardExports.*
  println(StandardSet(10, 20, 30).getClass)            // class scala.collection.mutable.HashSet
  println(sin(PI / 2))                                 // 1.0: using Math.*
  println(concat(Array(10, 20), Array(30, 40)).toList) // List(10, 20, 30, 40): using Array.*
  println(new Date().getClass)                         // class java.util.Date

6. How do variance and bounds work?

Classes, traits, type aliases and methods can take type parameters, used in the definition as types and usually inferred at the call site. Two mechanisms go further than plain generics.

• Declaration-site variance. A type parameter is declared covariant (+A: C[Cat] <: C[Animal]), contravariant (-A: C[Animal] <: C[Cat]) or, by default, invariant. The decision is taken once, where the type is defined, instead of at every use as with Java's wildcards (List<? extends Number>); the deck cites Igarashi and Viroli, ECOOP 2002. The compiler checks that the annotation respects Liskov's substitution principle. With List[+T] we have List[Int] <: List[AnyVal], but a setter taking a T is rejected, because T would occur in a contravariant position.
• Bounds. An upper bound [A <: Upper], a lower bound [A >: Lower], or both restrict how a type parameter can be instantiated.

The rule of thumb is that covariant parameters may appear only in outputs (results) and contravariant ones only in inputs (method parameters). Functions show both: a Function1[-T1, +R] that accepts Any and returns String can be used wherever a function from String to Any is expected. The library is annotated accordingly:

object Variance extends App:
  /* from the library:
  package scala
  abstract class Option[+A]
  trait PartialFunction[-T1, +R]  // { case x => ... }
  trait Function0[+R]             // () => R
  trait Function1[-T1, +R]        // (T1) => R
  trait Function2[-T1, -T2, +R]   // (T1, T2) => R
  case class Tuple2[+T1, +T2](_1: T1, _2: T2) // (T1, T2)

  package scala.collection
  trait Iterator[+A]
  trait Set[A]                    // ... extends (A) => Boolean
  trait Seq[+A] extends PartialFunction[Int, A] ... // extends (Int) => A
  trait Map[K, +V] extends PartialFunction[K, V] ... // and Iterable[(K, V)]
  */
  val v: Option[List[Any]] = Some[List[Int]](List(10, 20, 30))  // covariance, twice
  val w: Option[Iterable[Any]] = Some[Set[Int]](Set(10, 20, 30))
  val f: String => Any = (s: Any) => s.toString  // contravariant input, covariant output
  val s: String => Boolean = Set("a", "b", "c")  // a Set is a predicate
  val seq: Int => String = List("a", "b", "c")   // a Seq is a function from indices
  val m: String => Int = Map("a" -> 1, "b" -> 2, "c" -> 3) // a Map is a function from keys
  println(s("b"))    // true
  println(seq(2))    // c
  println(m("c"))    // 3
  // val bad: Set[Any] = Set[Int](1, 2)  // error: Set is invariant

A Set is a predicate and is invariant, since its element type is used as an input by contains. A Seq[+A] is a function from indices, and a Map[K, +V] a function from keys, covariant in the values.

Making a stack covariant

trait Stack[T]:
  def top: Option[T]
  def pop: Option[(T, Stack[T])]
  def push(t: T): Stack[T]
  def toList: List[T]

object Stack:
  def apply[T](elems: T*): Stack[T] = StackImpl(elems.toList)

  private class StackImpl[T](val list: List[T]) extends Stack[T]:
    override def top = list.headOption
    override def pop = top map ((_, StackImpl(list.tail)))
    override def push(t: T) = StackImpl(t :: list)
    override def toList = list

object TryStacks extends App:
  var stack = Stack(10)
  stack = stack push 20
  println(stack.top)        // Some(20)
  stack = stack.pop.get._2  // [10]
  println(stack.top)        // Some(10)
  stack = stack.pop.get._2  // []
  println(stack.top)        // None

  // COVARIANCE PROBLEM
  // var generalStack: Stack[Any] = Stack[Int](10, 20, 30) // does not compile: Stack is invariant
  // generalStack = generalStack.push("a string")          // if it did, this would corrupt the stack

If Stack were covariant, a Stack[Int] could be used as a Stack[Any] and a string pushed into it, corrupting a stack that its other owners still see as integers. The compiler prevents this. The invariant stack refuses the assignment ("Found: Stack[Int], Required: Stack[Any]"), and declaring trait Stack[+T] with push(t: T) fails with "covariant type T occurs in contravariant position in type T of parameter t". The fix is to make push more general with a lower bound: pushing an R that is a supertype of T returns a CoStack[R], so the type widens instead of lying:

trait CoStack[+T]:                      // a covariant stack
  def top: Option[T]
  def pop: Option[(T, CoStack[T])]
  def push[R >: T](r: R): CoStack[R]    // a more general push is needed
  def toList: List[T]

object CoStack:                         // same implementation as Stack
  def apply[T](elems: T*): CoStack[T] = CoStackImpl(elems.toList)

  private case class CoStackImpl[+T](list: List[T]) extends CoStack[T]:
    override def top = list.headOption
    override def pop = top map ((_, CoStackImpl(list.tail)))
    override def push[R >: T](r: R) = CoStackImpl(r :: list)
    override def toList = list

object TryCoStacks extends App:
  var stack: CoStack[Any] = CoStack[Int](10, 20, 30)
  stack = stack push "a string"
  val list: List[Any] = stack.toList
  println(list)                         // List(a string, 10, 20, 30)
  val ints = CoStack(1, 2)
  val widened = ints.push(3.5)          // R inferred as Int | Double: a CoStack[Int | Double]
  println(widened.toList)               // List(3.5, 1, 2)

Pushing a string on a CoStack[Int] is legal and yields a stack of a wider type. With an Int stack and a Double, Scala 3 infers R = Int | Double, a union type. The original stack is untouched either way.

Covariance also allows a single empty-list object. Nil is a CoList[Nothing], and since Nothing is a subtype of every type, it is a CoList[T] for every T:

// alternative approach: a sealed trait and case classes/objects
// sealed trait CoList[+T]
// case class Cons[+T](head: T, tail: CoList[T]) extends CoList[T]
// case object Nil extends CoList[Nothing]  // a single-object case

enum CoList[+T]:
  case Cons(head: T, tail: CoList[T])
  case Nil

object CoList:
  def apply[T](elems: T*): CoList[T] =
    elems.foldRight[CoList[T]](Nil)(Cons(_, _)) // functional trick

object TryCoList extends App:
  // would not type-check with CoList[T] instead of CoList[+T]
  val ll: CoList[CoList[Any]] = CoList(
    CoList(10, 20, 30),
    CoList("a", "b", "c"),
    CoList(10, 3.5, "a string"))
  println(ll)

7. What are extension methods for?

Extension methods, given instances and conversions are the three features, all FP-oriented, that make Scala more flexible. They are to be used with care, making sure the abstraction is captured and documented correctly.

Extension methods apply the adapter pattern without an adapter class. When an interface must gain methods after its definition, and only in some contexts, the classic adapter wraps the object in a new class that delegates to it. An extension method is instead defined outside the class, translated to a method taking the receiver as first argument, and callable with dot notation wherever it is in scope:

case class Point2D(x: Double, y: Double)

extension (p: Point2D)
  def length: Double = Math.sqrt(p.x * p.x + p.y * p.y)
  def isZero: Boolean = p.x == 0.0 && p.y == 0

object Point2DOperators:
  extension (p: Point2D)
    def +(q: Point2D): Point2D = Point2D(p.x + q.x, p.y + q.y)
    def -(q: Point2D): Point2D = Point2D(p.x - q.x, p.y - q.y)

@main def main() =
  // using methods defined separately from the implementation
  val p = Point2D(10, 20)
  println(p.length)        // 22.360679774997898
  println(p.isZero)        // false
  println(length(p))       // 22.360679774997898: what p.length is translated to

  // importing and using a desired set of additional operators
  import Point2DOperators.*
  println(p + p)           // Point2D(20.0,40.0)
  println(p - p)           // Point2D(0.0,0.0)
  println((p - p).isZero)  // true

  // extending and using a library class
  extension [T](l: List[T])
    def second: T = l.tail.head

  println(List(10, 20, 30).second) // 20

The compiler rewrites p.length to length(p) only if Point2D has no member length and the extension is visible (defined in scope or imported). Operators live in Point2DOperators and exist only after import Point2DOperators.*. Extensions work on library classes too (second on List). Their typical uses are adding operators to existing classes, separating data from operations and recombining them freely, and giving an OO flavour to pure FP code.

Do we really need OOP?

The last use can be taken far. Here a list is only data, an enum, and all its operations are extensions in the companion. Clients still write l map (…) filter (…) reduce (…):

object OOPFPLists extends App:

  enum MyList[+A]:
    case Cons(h: A, t: MyList[A])
    case Empty

  object MyList:
    import MyList.*
    def apply[A](a: A*) = a.foldRight[MyList[A]](Empty)(Cons(_, _))
    extension [A](list: MyList[A])
      def foldRight[B](init: => B)(op: (A, B) => B): B = list match
        case Empty => init
        case Cons(h, t) => op(h, t.foldRight(init)(op))
      def foldLeft[B](init: => B)(op: (B, A) => B): B = list match
        case Empty => init
        case Cons(h, t) => t.foldLeft(op(init, h))(op)
      def map[B](f: A => B): MyList[B] =
        list.foldRight[MyList[B]](Empty)((a, b) => Cons(f(a), b))
      def filter(p: A => Boolean) =
        list.foldRight[MyList[A]](Empty)((a, b) => if p(a) then Cons(a, b) else b)
      def reduce(op: (A, A) => A): A = list match
        case Cons(h, t) => t.foldLeft(h)(op)

  import MyList.*
  val l = MyList(10, 20, 30, 40, 50)
  println(l map (_ - 1) filter (_ < 30) reduce (_ + _)) // 57: 9 + 19 + 29

(The compiler warns that reduce does not handle Empty, and on an empty list it would throw a MatchError.) The recipe is: define types by aliases, case classes and enums; add OO-like operations as extension methods in companion objects; keep trait implementations private, mostly as product types; and always prefer delegation to inheritance. "Receiver plus method" becomes "context argument plus pure function". It works surprisingly often, and when it works it gives solid, controlled designs, with type classes such as monads adding further power. It is not universal: sometimes FP is a stretch, and some things are naturally objects, such as controllers and stateful models.

8. How does contextual abstraction work?

The arguments of a function often fall into two groups: inputs, the data turned into the output, and context, which influences how the output is produced (a strategy, a configuration, an ordering). The split is neither universal nor unique, but it recurs often, and context can often be inferred from the scope of the call instead of being passed every time. This is term inference: in certain scopes, the program tells the compiler how to synthesise a canonical term of a given type. Scala 2 did it with the much-criticised, opaque implicit mechanism. Scala 3 uses the more direct and intent-revealing given/using:

• def f(using ctx: Context)(input: Input): Output declares a context parameter;
• f(using ctx)(input) passes it explicitly, f(input) lets the compiler find it;
• given Context = … defines the canonical instance for a scope, and import obj.given imports the givens of an object (a plain import obj.* does not).

object Parameters extends App:

  trait MyOrdering[A]:
    def greater(x: A, y: A): Boolean

  def max[T](elem: T, elems: T*)(using ordering: MyOrdering[T]): T =
    elems.foldLeft(elem)((m, e) => if ordering.greater(e, m) then e else m)

  val myStringOrdering = new MyOrdering[String]:
    override def greater(x: String, y: String) = x.compareTo(y) > 0

  println(max("a", "b")(using myStringOrdering)) // b: using a provided ordering

  // givens, with different styles of definition
  given implicitOrdering: MyOrdering[String] = myStringOrdering
  // without a name it would shrink to: given MyOrdering[String] = ...
  // with an in-line implementation of the trait:
  given MyOrdering[Int] with
    def greater(x: Int, y: Int): Boolean = x > y
  // with a lambda, since MyOrdering has a single abstract method:
  given MyOrdering[List[Int]] = _.size > _.size

  // recovering the canonical instance of MyOrdering[String]
  println(summon[MyOrdering[String]] eq myStringOrdering) // true

  println(max("a", "b"))                // b: using the given ordering in scope
  println(max(10, 20))                  // 20
  println(max(List(10, 20), List(30)))  // List(10, 20): the longer list

Three styles of given appear: an alias to an existing value (given implicitOrdering: … = myStringOrdering), an in-line implementation (given … with), and, for a trait with one abstract method, a lambda. summon[T] retrieves the given of type T in scope, here the very same object. (The deck's comment on the last line says 20. The result is List(10, 20), the longer list.)

Context bounds and ad-hoc polymorphism

def m[A: B](…) can be called with a type A only if a given of type B[A] is in scope. B is a context bound on A: A must come with a "context" describing additional behaviour, which the method recovers with summon[B[A]]. This is not a trick. It gives ad-hoc polymorphism, a method applicable to exactly the selected types that have the context, and it paves the way to hierarchies of contexts as type classes (lesson 4):

object Parameters2 extends App:

  trait MyOrdering[A]:
    def greater(x: A, y: A): Boolean

  // equivalent to the previous formulation, using a context bound
  def max[T: MyOrdering](elem: T, elems: T*): T =
    elems.foldLeft(elem)((m, e) => if summon[MyOrdering[T]].greater(e, m) then e else m)

  object GivenOrderings:  // all shrinkable to literals
    given MyOrdering[String] with
      override def greater(x: String, y: String) = x.compareTo(y) >= 0
    given MyOrdering[Int] with
      override def greater(x: Int, y: Int) = x >= y
    // a generic given: a name is needed
    given listOrdering[A]: MyOrdering[List[A]] with
      override def greater(x: List[A], y: List[A]) = x.size >= y.size

  import GivenOrderings.given

  println(max("a", "d", "b", "c"))    // d
  println(max(10, 40, 20, 30))        // 40
  println(max(List(10, 20), List(30, 40, 50), List("a", "b"))) // List(30, 40, 50)
  // println(max(1.5, 2.5))           // error: no given instance of type MyOrdering[Double]

The generic given listOrdering[A] provides an ordering for lists of any element type. In the last call the three lists are unified to List[Int | String], which it also covers. For max(1.5, 2.5) the compiler reports "No given instance of type MyOrdering[Double] was found". The standard library's Ordering is the same type class, already given for the usual types:

object Bounds extends App:
  // the same idea with the library's type class scala.math.Ordering
  def max2[T: Ordering](t1: T, t2: T): T = summon[Ordering[T]].max(t1, t2)
  println(max2("a", "b"))                          // b
  println(max2(3.5, 2.5))                          // 3.5: Ordering[Double] is given by the library
  println(List(3, 1, 2).sorted)                    // List(1, 2, 3): sorted takes a using Ordering
  println(List(3, 1, 2).sorted(using Ordering[Int].reverse)) // List(3, 2, 1)

Given conversions: automatic adapters

Extension methods add methods to a class that lacked them. Legacy libraries that must interoperate with new code built on different assumptions need something more. The adapter pattern works, but it wraps every legacy value by hand. A given instance of scala.Conversion[-I, +O], a subtype of I => O, automates it: wherever an I is used where an O is expected, the compiler inserts the conversion. The companion object of the target type is the proper place for it, since givens there are always visible:

object Conversions extends App:
  import scala.language.implicitConversions // otherwise each use gives a feature warning
  case class Point(n: Int, m: Int)
  object Point: // the companion object is a proper place for conversions
    // a conversion from tuple to point, by an apply method
    given Conversion[(Int, Int), Point] with
      def apply(t: (Int, Int)): Point =
        println("converting tuple " + t + " to a point..") // a debug print
        Point(t._1, t._2)
    // a conversion by a literal
    given Conversion[List[Int], Point] = l => Point(l.head, l.tail.head)

  def pointToRadius(p: Point) = Math.sqrt(p.n * p.n + p.m * p.m)

  println(pointToRadius(Point(3, 4)))  // 5.0
  val tup = (3, 4)
  println(pointToRadius(tup))          // converting tuple (3,4) to a point.. then 5.0
  println(pointToRadius(List(3, 4)))   // 5.0

  // checking (e.g. in the REPL) whether a conversion is active
  println(summon[((Int, Int)) => Point]((10, 20)))       // converting tuple (10,20) ... then Point(10,20)
  println(summon[List[Int] => Point](List(20, 30, 40)))  // Point(20,30)

Each use of a conversion produces a feature warning unless scala.language.implicitConversions is imported. That friction is deliberate, because conversions make code harder to read. (Among the deck's summon checks, the comment "Point(10,20)" for List(20,30,40) is a slip: the result is Point(20,30).) The deck's example of a legitimate use is a facade over Swing:

import java.awt.event.*
import javax.swing.*
import scala.language.implicitConversions

object ScalaSwingFacade:

  def createPanel(comps: JComponent*): JPanel =
    comps.foldLeft(new JPanel()): (p, c) =>
      p.add(c); p

  given Conversion[ActionEvent => Unit, ActionListener] = f => f(_)
  // i.e. f => new ActionListener(){ def actionPerformed(e: ActionEvent) = f(e) }
  // i.e. f => e => f(e)

  extension (b: JButton)
    def addActionListener(action: => Unit): Unit = b.addActionListener(e => action)

object TrySwing extends App:
  import ScalaSwingFacade.{*, given}

  val f = new JFrame("title")
  val text = new JTextField(10)
  val bok = new JButton("OK")
  val bevt = new JButton("Event")
  val bquit = new JButton("Quit")
  val p = createPanel(text, bok, bevt, bquit)
  bok.addActionListener(JOptionPane.showMessageDialog(f, s"Text: ${text.getText}"))
  bevt.addActionListener(JOptionPane.showMessageDialog(f, _))
  bquit.addActionListener(System.exit(0))
  val log: ActionEvent => Unit = e => println(e.getActionCommand)
  bok.addActionListener(log)   // a Scala function value: needs the given Conversion
  f.getContentPane.add(p)
  f.pack()
  f.setVisible(true)

Two mechanisms cooperate. The extension adds an addActionListener taking a by-name block, so bquit.addActionListener(System.exit(0)) reads naturally. Java's own method still takes precedence when a listener-shaped lambda is passed. The given conversion turns any Scala function ActionEvent => Unit into an ActionListener. The import ScalaSwingFacade.{*, given} matters: with import ScalaSwingFacade.* alone, bok.addActionListener(log) fails with "Found: ActionEvent => Unit, Required: ActionListener", and the compiler suggests importing the given.

9. How do these features make DSLs?

ScalaTest is the course's example of a "pretty DSL", or library pimping. The AnyFunSuite style resembles JUnit, and the AnyFlatSpec style reads as a specification. The should matchers turn assertions into near-English, and give readable failure messages:

import org.scalatest.matchers.should.Matchers.*

class ScalaTestShowcase extends org.scalatest.funsuite.AnyFunSuite:

  test("List operations, and should matchers"):
    val testedList: List[Int] = 10 :: 20 :: 30 :: 40 :: Nil
    assert(testedList.size == 4)   // JUnit-like assertion
    testedList.size shouldBe 4     // from here, should matchers...
    testedList.size should be (4)
    testedList should have size 4
    testedList should not be empty
    testedList.forall(_ > 5) should be (true)
    a [IndexOutOfBoundsException] should be thrownBy testedList(5)
    testedList.collect { case i if i > 20 => i + 1 } should contain allOf (31, 41)
    "val l = 10 :: 20 :: Nil" should compile

class SetSpec extends org.scalatest.flatspec.AnyFlatSpec:

  "A mutable Set" should "correctly add elements" in:
    val s: collection.mutable.Set[Int] = collection.mutable.Set()
    s += 10
    s += 20
    s += 30
    assert(s == Set(10, 20, 30))
    s should be (Set(10, 20, 30))

Run with ScalaTest 3.2.19, both suites pass. A deliberately failing List(10, 20) should contain (30) reports "List(10, 20) did not contain element 30". Almost every token is one of this lesson's mechanisms. testedList should have size 4 is a chain of infix method calls, and should is added to any value by a conversion that Matchers.* brings into scope. thrownBy testedList(5) takes a by-name argument, so the exception is raised inside the matcher. The indented block after test(…): is the by-name body of the test, and "…" should compile is checked at compile time by a macro. In sbt the dependency goes in the test scope (the deck's line: libraryDependencies += "org.scalatest" %% "scalatest" % "3.2.18" % "test").

10. What does a for-comprehension mean?

The weak reading of for is "an iteration construct with several variables", something like foreach, or perhaps map/flatMap. The stronger reading, which the course builds on, is that it is a way to encode exploration-like computations, to define a notion of sequentiality in FP, and to encapsulate monads. For now: for/yield is sugar for map, flatMap and filtering.

object Comprehension extends App:

  val l = List(10, 20, 30)
  println(l map (_ * 2))          // List(20, 40, 60)
  println(l flatMap (List(_, 0))) // List(10, 0, 20, 0, 30, 0)
  println(l filter (_ > 10))      // List(20, 30)

  // Problem: give all quartets (x, y, z, x*y*z) such that:
  // 1) x, y, z in 1..8; 2) x + y + z == 10; 3) x < y < z
  val l2 = for
    x <- 1 until 9
    y <- 1 until 9
    z <- 1 until 9
    if x + y + z == 10
    if x < y && y < z
    w = x * y * z
  yield
    (x, y, z, w)
  println(l2) // Vector((1,2,7,14), (1,3,6,18), (1,4,5,20), (2,3,5,30))

  // desugared version (as in Scala 2)
  val l3 = (1 until 9)
    .flatMap(x => (1 until 9)
      .flatMap(y => (1 until 9)
        .filter(z => x + y + z == 10)
        .filter(z => x < y && y < z)
        .map(z => (z, x * y * z))
        .map { case (z, w) => (x, y, z, w) }))
  println(l3 == l2) // true

(The deck's comment says x, y, z range over 1..9, but 1 until 9 stops at 8. The answers are the same because the sum is 10.) The translation rules, which the compiler applies before type checking and which work for any type with these methods:

Printing the compiler's tree for l2 (-Xprint:typer) shows exactly the deck's "Scala 2" version, with withFilter in place of filter: flatMap, flatMap, withFilter, withFilter, map(z => (z, w)), map { case (z, w) => (x, y, z, w) }. A smaller case, with the same rules applied to do and to Option:

object Small extends App:
  val a = for x <- List(1, 2); y <- List(3, 4) if x + y > 4 yield (x, y)
  val b = List(1, 2).flatMap(x => List(3, 4).withFilter(y => x + y > 4).map(y => (x, y)))
  println(a)       // List((1,4), (2,3), (2,4))
  println(a == b)  // true
  for x <- List(1, 2); y <- List("a") do print(s"$x$y ")  // 1a 2a
  println()
  List(1, 2).foreach(x => List("a").foreach(y => print(s"$x$y "))) // the same, desugared
  println()
  // the same sugar works on any type with map/flatMap/withFilter, e.g. Option
  println(for x <- Some(3); y <- Option.empty[Int] yield x + y)  // None

Exploring a search space: the n-queens

Place n queens on an n×n board so that none attacks another. placeQueens(n) returns every safe placement on rows 1..n. It takes each placement for n − 1 rows, tries every column of row n, keeps only the safe cells, and extends the placement. The base case is a single empty placement.

object Nqueen:
  type Queen = (Int, Int)            // type aliases improve readability
  type Solution = Iterable[Queen]
  type IterableFactory = Solution => Iterable[Solution]
  val size = 8
  given IterableFactory = LazyList(_) // could switch to Set(_), List(_), or List(_).view

  @main def run() = placeQueens().zipWithIndex foreach (printSolution(_))

  def placeQueens(n: Int = size)(using factory: IterableFactory): Iterable[Solution] = n match
    case 0 => factory(Set())
    case _ =>
      for
        queens <- placeQueens(n - 1)   // get a solution on a smaller grid
        y <- 1 to size                 // iterate over all columns
        queen = (n, y)                 // consider a new queen on any cell in the last row
        if isSafe(queen, queens)       // ...only a safe one
      yield
        queens.toSeq :+ queen          // construct the new solution

  def isSafe(queen: Queen, others: Iterable[Queen]) =
    others forall (!isAttacked(queen, _))

  def isAttacked(q1: Queen, q2: Queen) =
    q1._1 == q2._1 || q1._2 == q2._2 || (q2._1 - q1._1).abs == (q2._2 - q1._2).abs

  def printSolution(si: (Solution, Int)): Unit =
    println(); println(s"sol ${si._2}")
    for queen <- si._1; x <- 1 to size do
      print(if queen._2 == x then "Q " else ". ")
      if x == size then println()

The type aliases make the signature readable, and the collection used for the exploration is a context parameter. With the given LazyList(_) the search is lazy, so asking for the first solution computes little more than one path. Passing List(_), Set(_) or List(_).view changes the strategy without touching the algorithm:

@main def stats() =
  val all = placeQueens()
  println(all.getClass.getSimpleName)          // LazyList
  println(all.head)                            // List((1,1), (2,5), (3,8), (4,6), (5,3), (6,7), (7,2), (8,4))
  println(all.size)                            // 92
  printSolution((all.head, 0))
  println(placeQueens()(using List(_)).size)   // 92: the same search, eager

(stats prints the first solution as the board shown by printSolution: a queen in column 1 of row 1, column 5 of row 2, and so on. The deck sets size = 10, which gives 724 solutions; 8 gives the classic 92.)

type Position = (Int, Int)
type Solution = List[Position]        // most recent mark first

val moves = List((3, 0), (-3, 0), (0, 3), (0, -3), (2, 2), (2, -2), (-2, 2), (-2, -2))

def placeMarks(width: Int, height: Int): Iterable[Solution] =
  def inside(p: Position) = p._1 >= 0 && p._1 < width && p._2 >= 0 && p._2 < height
  def place(n: Int): Iterable[Solution] = n match
    case 1 => LazyList(List((width / 2, height / 2)))  // the first mark, in the centre
    case _ =>
      for
        sol <- place(n - 1)
        (dx, dy) <- moves
        next = (sol.head._1 + dx, sol.head._2 + dy)
        if inside(next) && !sol.contains(next)
      yield next :: sol
  place(width * height)

Check your understanding