Last updated on Wednesday, January 21, 2026

Week 5: Comprehensions, Variance and Specs

Welcome to week 5 of CS-214 — Software Construction!

As before, exercises or questions marked ⭐️ are the most important, 🔥 are the most challenging, and 🧪 are the most useful for this week’s lab.

Comprehensions

for comprehensions

Scala does not have for loops; instead, it has for comprehensions. Comprehensions are particularly powerful when you need to combine and filter results from multiple collections. Let’s see some examples!

Warm-up ⭐️

In previous weeks we saw how to filter, map over, and flatten lists using recursive functions and List API functions. This week, we have a new way to perform these computations: comprehensions.

Just 3 (filters) 🧪

Using a for comprehension, write a function that filters a list of words (represented as Strings), keeping only words of length 3:

def onlyThreeLetterWords(words: List[String]): List[String] =
  ???

def onlyThreeLetterWords(words: List[String]): List[String] =
  for
    word <- words
    if word.length() == 3
  yield word

LOUDER (maps)

Using a for comprehension, write a function that converts a list of words (represented as Strings) to uppercase, using the .toUpperCase() method:

def louder(words: List[String]): List[String] =
  ???

For example List("a", "bc", "def", "ghij") should become List("A", "BC", "DEF", "GHIJ").

def louder(words: List[String]): List[String] =
  for word <- words
  yield word.toUpperCase(Locale.ROOT)

Echo (flatMaps)

Using a for comprehension, write a function that repeats each word in a list of words n times. Write a comprehension with two separate <- clauses, and use either Iterable.fill(n)(word) to create an iterable of n times the value word, or (1 to n) to iterate n times.

def echo(words: List[String], n: Int): List[String] =
  ???

For example List("a", "bc", "def", "ghij") should become List("a", "a", "bc", "bc", "def", "def", "ghij", "ghij") if n == 2.

def echo(words: List[String], n: Int): List[String] =
  for
    word <- words
    _ <- (1 to n)
  yield word

All together now 🧪

Using a for comprehension, write a function that converts all words in a list to upper case, removes all words whose length is not three, and repeats all others n times:

def allTogether(words: List[String], n: Int): List[String] =
  ???

For example List("All", "together", "now") should become List("ALL", "ALL", "ALL", "NOW", "NOW", "NOW") if n is 3.

def allTogether(words: List[String], n: Int): List[String] =
  for
    word <- words
    if word.length() == 3
    upper = word.toUpperCase(Locale.ROOT)
    _ <- (1 to n)
  yield upper

Cross product

Reimplement the cross-product function from last week using a for comprehension.

Additionally, your function should now take Scala Lists as input, and return a Scala List as output.

def crossProduct[A, B](l1: List[A], l2: List[B]): List[(A, B)] =
  ???

def crossProduct[A, B](l1: List[A], l2: List[B]): List[(A, B)] =
  for
    a <- l1
    b <- l2
  yield (a, b)

Permutations

Reimplement the distinctPairs function from last week using a for comprehension.

def distinctPairs[A](items: Seq[A]): Seq[(A, A)] =
  ???

def distinctPairs[A](items: Seq[A]): Seq[(A, A)] =
  for
    a <- items
    b <- items
    if a != b
  yield (a, b)

Comprehensions on Option ⭐️

When thinking about a for comprehension, the most intuitive use of it would be on a list. But it can be used on any type that defines map, flatMap and, optionally, withFilter. In particular, we can use for comprehensions on Option values.

For this exercise, we provide you with a function that parses a string into an Option of integer. For example, parseInt("123") returns Some(123), but parseInt("abc") returns None. You do not need to understand the inner works of the function, as we will learn more about Try later 🔜.

def parseInt(s: String): Option[Int] =
  Try(s.toInt).toOption

Implement the validInts function, that parses a list of strings to integers and returns only valid integers.

def validInts(strings: List[String]): List[Int] =
  ???

def validInts(strings: List[String]): List[Int] =
  for
    s <- strings
    i <- parseInt(s)
  yield i

Glob matching (ungraded callback to find!)

The real Unix find command takes a “glob pattern” for its -name filter: it supports wildcards like ? and * to allow for partial matches. For example,

• find -name 2023-*.jpg finds all files whose name starts with 2023- and ends with .jpg, and
• find -name 20??-*.jp*g finds all files whose name starts with 20, then has two arbitrary characters, then a dash, any letter, and finally .jp followed by anything followed by g. This would allow users to find 2002-03-18T11:15.jpg or 2002-03-18 modified.jpeg, for example.

Write a function glob(pattern, input) that returns a boolean indicating whether a glob pattern matches a string (represented as a list of Chars):

def glob(pattern: List[Char], input: List[Char]): Boolean =
  ???

The rules are as follows:

• ? matches one arbitrary character
• * matches an arbitrary sequence of characters
• Other characters match themselves

The whole pattern must match the whole string: partial matches are not allowed.

Based on your implementation, can you prove that a pattern that does not contain wildcards matches only itself? That * matches all strings? That a pattern with only ?s matches all strings of the same length as the pattern? That repeated *s can be replaced by a single *?

def glob(pattern: List[Char], input: List[Char]): Boolean =
  (pattern, input) match
    case (Nil, Nil)             => true
    case (Nil, _)               => false
    case ('?' :: pat, i :: inp) => glob(pat, inp)
    case ('*' :: pat, Nil)      => glob(pat, input)
    case ('*' :: pat, i :: inp) => glob(pat, input) || glob(pattern, inp)
    case (p :: pat, Nil)        => false
    case (p :: pat, i :: inp)   => p == i && glob(pat, inp)

Des chiffres et des lettres

“Des chiffres et des lettres” is a popular TV show in French-speaking countries.

In this show, contestants take turns guessing the longest word that can be made from a list of letters, and finding a way to arrange a list of numbers into an arithmetic computation to get as close as possible to a target number. For example:

• For the letters G N Q E U T I O L Y C E P H, an excellent contestant would immediately propose the word “POLYTECHNIQUE”.

• For the numbers 2 5 3 9 100 9 and the target number 304, an excellent contestant would suggest 3 * (9 + 9) + 5 * 100 / 2, and exclaim “le compte est bon!”.

Des lettres 🧪

Write a function longestWord which, given a wordlist (a collection of words) represented as a List[String] and a collection of letters represented as a String, finds the longest word that can be made by reordering a subset of these strings. You can write your function directly, or follow the steps below.

def scramble(word: String): String =
  word.toUpperCase(Locale.ROOT).sorted

def scrambleList(allWords: Set[String]): Map[String, Set[String]] =
  allWords.groupBy(scramble)

def exactWord(allWords: Set[String], letters: String): Set[String] =
  scrambleList(allWords).getOrElse(scramble(letters), Set.empty)

def compatible(small: String, large: String): Boolean =
  (small, large) match
    case ("", _) => true
    case (_, "") => false
    case _ =>
      if small.head == large.head then compatible(small.tail, large.tail)
      else if small.head > large.head then compatible(small, large.tail)
      else false

def longestWord(allWords: Set[String], letters: String): Set[String] =
  val haystack = scramble(letters)
  val words =
    for
      (needle, words) <- scrambleList(allWords)
      if compatible(needle, haystack)
    yield words
  words.maxByOption(_.head.length).getOrElse(Set.empty)

Des chiffres 🔥

Write a function leCompteEstBon that takes a List of integers and a target number, and returns an arithmetic expression that evaluates to the target sum, if one exists. The allowable operators are +, - (only when the result is nonnegative), *, and / (only when the division is exact), as well as parentheses. For the purpose of this exercise, assume that we are only interested in exact results, using all provided integers. The result should be an expression of type Expr:

trait Expr:
  val value: Option[Int]

case class Num(n: Int) extends Expr:
  val value = Some(n)

abstract class Binop extends Expr:
  val e1, e2: Expr // Subexpressions
  def op(n1: Int, n2: Int): Option[Int] // How to evaluate this operator

val value: Option[Int] =
  for
    n1 <- e1.value
    n2 <- e2.value
    r <- op(n1, n2)
  yield r

case class Add(e1: Expr, e2: Expr) extends Binop:
  def op(n1: Int, n2: Int) =
    Some(n1 + n2)

case class Sub(e1: Expr, e2: Expr) extends Binop:
  def op(n1: Int, n2: Int) =
    if n1 < n2 then None else Some(n1 - n2)

case class Mul(e1: Expr, e2: Expr) extends Binop:
  def op(n1: Int, n2: Int) =
    Some(n1 * n2)

case class Div(e1: Expr, e2: Expr) extends Binop:
  def op(n1: Int, n2: Int) =
    if n2 != 0 && n1 % n2 == 0 then Some(n1 / n2) else None

def partitions[A](l: List[A]): List[(List[A], List[A])] =
  l match
    case List() => List((Nil, Nil))
    case h :: t =>
      for
        (l1, l2) <- partitions(t)
        partition <- List((h :: l1, l2), (l1, h :: l2))
      yield partition

def allTrees(ints: List[Int]): List[Expr] =
  ints match
    case Nil     => Nil
    case List(n) => List(Num(n))
    case _ =>
      val trees: List[Expr] =
        for
          (lints, rints) <- partitions(ints)
          if !lints.isEmpty && !rints.isEmpty
          ltree <- allTrees(lints)
          rtree <- allTrees(rints)
          op <- List(Add(_, _), Sub(_, _), Mul(_, _), Div(_, _))
          r = op(ltree, rtree)
          if !r.value.isEmpty
        yield r
      // Optimization: keep just one tree per feasible value
      trees.groupBy(_.value).values.map(_.head).toList

def leCompteEstBon(ints: List[Int], target: Int): Option[Expr] =
  allTrees(ints).find(_.value == Some(target))

Tracing code execution

Polish notation (from week 1) ⭐️

Use tracing to gain a better understanding of the following function, which computes the value of a polish-notation expression:

enum Operand[+T]:
  case Add extends Operand[Nothing]
  case Mul extends Operand[Nothing]
  case Num(t: T)

type OpStack[T] = List[Operand[T]]

def polishEval(ops: OpStack[Int]): (Int, OpStack[Int]) =
  ops match
    case Nil => throw IllegalArgumentException()
    case op :: afterOp =>
      op match
        case Operand.Num(n) =>
          (n, afterOp)
        case Operand.Add =>
          val (l, afterL) = polishEval(afterOp)
          val (r, afterR) = polishEval(afterL)
          (l + r, afterR)
        case Operand.Mul =>
          val (l, afterL) = polishEval(afterOp)
          val (r, afterR) = polishEval(afterL)
          (l * r, afterR)

/* A cute use of extension functions to save myself some typing */
extension [B](result: B)
  def andThenPrintResult(indent: String): B =
    println(f"${indent}← ${result}")
    result

def polishEval(ops: OpStack[Int], indent: String = ""): (Int, OpStack[Int]) = {
  println(f"${indent}→ ${ops}")
  val new_indent = "  " + indent
  ops match
    case Nil => throw IllegalArgumentException()
    case op :: afterOp =>
      op match
        case Operand.Num(n) =>
          (n, afterOp)
        case Operand.Add =>
          val (l, afterL) = polishEval(afterOp, new_indent)
          val (r, afterR) = polishEval(afterL, new_indent)
          (l + r, afterR)
        case Operand.Mul =>
          val (l, afterL) = polishEval(afterOp, new_indent)
          val (r, afterR) = polishEval(afterL, new_indent)
          (l * r, afterR)
}.andThenPrintResult(indent)

McCarthy ⭐️

What does the following function do? Use tracing annotations to figure it out!

def mc(n: Int): Int =
  if n > 100 then n - 10
  else mc(mc(n + 11))

Takeuchi 🔥

What do the following functions do? Use tracing annotations to figure it out!

def t(x: Int, y: Int, z: Int): Int =
  if x <= y then y
  else
    t(
      t(x - 1, y, z),
      t(y - 1, z, x),
      t(z - 1, x, y)
    )

Tree folds

Two functions pairs and foldt are defined below. Use examples, pictures, the substitution method, refactoring, or tracing to figure out what foldt does.

extension [T](l: List[T])
  def pairs(op: (T, T) => T): List[T] = l match
    case a :: b :: tl => op(a, b) :: tl.pairs(op)
    case _            => l
  def foldt(z: T)(op: (T, T) => T): T = l match
    case Nil       => z
    case List(t)   => t
    case _ :: tail => l.pairs(op).foldt(z)(op)

Armed with that knowledge, can you figure out what algorithm the function ms below implements? Is it efficient? How does it differ from another version of the same algorithm that you saw previously?

extension (l: List[Int])
  def ms: List[Int] =
    l.map(List(_)).foldt(Nil)(merge)

(merge is the usual function that takes two sorted lists and merges them in sorted order)

def merge(xs: List[Int], ys: List[Int]): List[Int] =
  (xs, ys) match
    case (Nil, _) => ys
    case (_, Nil) => xs
    case (x :: xs1, y :: ys1) =>
      if x < y then x :: merge(xs1, ys)
      else y :: merge(xs, ys1)

Tracing performance issues

Sometimes, tracing can even help find performance issues: the longer a calculation takes, and the slower tracing statements will appear on screen. Can you use this insight to demonstrate that something is wrong with each of the following functions?

1. Reverse

def badReverse[T](l: List[T], acc: List[T] = Nil): List[T] =
  l match
    case Nil    => acc.reverse
    case h :: t => badReverse(t, acc ++ List(h))

2. Map

def badMap[T1, T2](l: List[T1], f: T1 => T2): List[T2] =
  if l.length == 0 then Nil
  else f(l.head) :: badMap(l.tail, f)

Tracing comprehensions

Performance issues

The following function has surprisingly poor performance. Why?

def badZip[T1, T2](l1: List[T1], l2: List[T2]): Seq[(T1, T2)] =
  for i <- (0 to math.min(l1.length, l2.length) - 1)
  yield (l1(i), l2(i))

A subtlety in desugaring and tracing comprehensions 🔥

A keystone of the CS214 debugging guide is to “understand the system”. Sometimes observing the system’s final output is enough, but other times adding instrumentation helps. It pays to be careful, however: any time you change the system that you are debugging, you risk changing its behavior, too. Let’s see an example.

As we’ve seen previously, tracing can help not just with recursion, but also with comprehensions: to insert a tracing instruction into a comprehension, we use _ = println(…).

1. Here is an instrumented comprehension. What does the tracing code print, and in which order?

   def traceIfTrue(b: Boolean, label: String) =
     if b then println(label)
     b
   
   def filter_tracedIfTrue(l: Seq[Int]): Seq[Int] =
     for
       n <- l
       if traceIfTrue(n % 5 == 0, f"$n is a multiple of 5!")
       if traceIfTrue(n % 3 == 0, f"  $n is also a multiple of 3!")
       if traceIfTrue(n >= 10, f"    $n is also greater than 10!")
     yield n
   

   comprehensions/src/main/scala/comprehensions/Tracing.scala

   Confirm your guess by running this code in a worksheet.

2. Here is a different, arguably more readable way to trace the same comprehension. What will it print?

   def filter_traced(l: Seq[Int]): Seq[Int] =
     for
       n <- l
       if n % 5 == 0
       _ = println(f"$n is a multiple of 5!")
       if n % 3 == 0
       _ = println(f"  $n is also a multiple of 3!")
       if n >= 10
       _ = println(f"    $n is also greater than 10!")
     yield n
   

   comprehensions/src/main/scala/comprehensions/Tracing.scala

   As before, confirm your guess by running this code in a worksheet.

3. What can you conclude?

Non-structural recursion: numbers

Factorial ⭐️

Define a recursive function that returns the factorial of the input integer.

def factorial(n: Int): Int =
  ???

def factorial(n: Int): Int =
  require(n >= 0)
  if n == 0 then 1
  else n * factorial(n - 1)

Fast exponentiation

Fast exponentiation is a technique to optimize the exponentiation of numbers:

b²ⁿ = (b²)ⁿ = (bⁿ)²
b²ⁿ⁺¹ = b * b²ⁿ

Define a function that implements this fast exponentiation.

def fastExp(base: Int, exp: Int): Int =
  ???

def fastExp(base: Int, exp: Int): Int =
  require(exp >= 0)
  if exp == 0 then 1
  else if (exp % 2) != 0 then base * fastExp(base, exp - 1)
  else fastExp(base * base, exp / 2)

Base-N encoding ⭐️

In this exercise, your task is to implement a function that encodes a given integer into its representation in a given base. The result should be a list of integers. If the number input is 0, decimalToBaseN should return an empty List.

For instance:

1. Encode the number 9 to base-2: decimalToBaseN(9, 2) should return List(1, 0, 0, 1).
2. Encode the number 20 to base-16: decimalToBaseN(20, 16) should return List(1, 4).

Your task is to implement the decimalToBaseN function.

def decimalToBaseN(number: Int, base: Int, acc: List[Int] = Nil): List[Int] =
    ???

def decimalToBaseN(number: Int, base: Int, acc: List[Int] = Nil): List[Int] =
  if number == 0 then acc
  else decimalToBaseN(number / base, base, (number % base) :: acc)

Non-structural recursion: collections

Coin Change ⭐️

You are given a list of coin denominations coins: List[Int], which are the different values a coin can have, and a target amount. You need to determine the number of distinct ways to make up the target amount using any combination of the provided coin denominations. You can use each coin denomination an unlimited number of times.

def coinChange(coins: List[Int], amount: Int): Int =
    ???

Let’s illustrate the coin change problem with an example.

Suppose you have the following coin denominations: List(1, 2, 5), and you want to make change for the amount 5. How many different ways are there to make change for 5 using these coins?

Here are the different ways to make change for 5:

5 = 5 (use one 5-coin)
5 = 2 + 2 + 1 (use two 2-coins and one 1-coin)
5 = 2 + 1 + 1 + 1 (use one 2-coin and three 1-coins)
5 = 1 + 1 + 1 + 1 + 1 (use five 1-coins)

So, there are a total of 4 different ways to make change for 5 using the denominations List(1, 2, 5).

def coinChange(coins: List[Int], amount: Int): Int =
  if amount == 0 then 1
  else if amount < 0 || coins.isEmpty then 0
  else
    coinChange(coins.tail, amount) + coinChange(coins, amount - coins.head)

Merge sort ⭐️

Merge sort is a popular and efficient comparison-based sorting algorithm that follows the divide-and-conquer paradigm. It works by recursively dividing a list into smaller sublists, sorting them, and then merging them back together into a single sorted list.

Roughly, merge sort proceeds in the following way:

• Split the list into two sublists.
• Recursively sort each sublist.
• Merge the two sorted sublists back into one sorted list.

Split

Define a function that splits a list into two halves, whose length difference is less than or equal to 1.

There are multiple ways to implement such a function from the Scala standard library. You may use a library function.

For example, if the list has n elements, the first list has the first $\lfloor n / 2 \rfloor$ elements and the second has the rest.

Or, when counting elements from 1, the first list has all items that were at odd positions, and the second one has all items that were at even positions. For example, the list a b c d e f g will be split into a c e g and b d f.

def split[A](l: List[A]): (List[A], List[A]) =
  ???

def split[A](l: List[A]): (List[A], List[A]) =
  l match
    case Nil         => (Nil, Nil)
    case head :: Nil => (List(head), Nil)
    case even :: odd :: rest =>
      val (evenList, oddList) = split(rest)
      (even :: evenList, odd :: oddList)

Merge

Write a merge function that takes two sorted lists and returns a sorted list containing all elements of both lists.

def merge(xs: List[Int], ys: List[Int]): List[Int] =
  ???

def merge(xs: List[Int], ys: List[Int]): List[Int] =
  (xs, ys) match
    case (Nil, _) => ys
    case (_, Nil) => xs
    case (x :: xs1, y :: ys1) =>
      if x < y then x :: merge(xs1, ys)
      else y :: merge(xs, ys1)

Sort

Implement the mergeSort function.

If the list has one or zero elements, what should the function do?

def mergeSort(xs: List[Int]): List[Int] =
    ???

def mergeSort(xs: List[Int]): List[Int] =
  xs match
    case Nil         => Nil
    case head :: Nil => List(head)
    case _ =>
      val (left, right) = split(xs)
      merge(mergeSort(left), mergeSort(right))

Exercises from the slides

N-Queens

Write a function isSafe which tests if a queen placed in an indicated column col is secure amongst the other placed queens. It is assumed that the new queen is placed in the next available row after the other placed queens (in other words: in row queens.length).

def isSafe(col: Int, queens: List[Int]): Boolean =
  ???

def isSafe(col: Int, queens: List[Int]): Boolean =
  val row = queens.length
  queens.zipWithIndex.forall((qc, qr) =>
    // Check if there's no conflict in the same column or diagonals
    qc != col && math.abs(qc - col) != math.abs(qr - row)
  )

Variance

The following exercises are intended to help you hone your understanding of covariance and contravariance.

Subtyping of variant types ⭐️

Recall that:

• Lists are covariant in their only type parameter.
• Functions are contravariant in the argument, and covariant in the result.

Consider the following hierarchies:

abstract class Fruit
class Banana extends Fruit
class Apple extends Fruit
abstract class Liquid
class Juice extends Liquid

Consider also the following typing relationships for A, B, C, D: A <: B and C <: D.

Fill in the subtyping relation between the types below. Bear in mind that it might be that neither type is a subtype of the other.

Testing subtyping relationships

Scala’s compiler automatically checks variance rules. Can we make it show us what it inferred? Write a function assertSubtype so that assertSubtype[Int, String] causes a compilation error, but assertSubtype[String, Object] compiles.

def assertSubtype[A, B >: A]: Unit = {}
def assertSupertype[A, B <: A]: Unit = {}

Understanding variance ⭐️

Variance rules are designed to keep type casts safe: any time the compiler rejects code for variance reasons, it does so to avoid runtime errors that could happen if these protections were not in place.

Here are some examples. For each, think of what might go wrong if the compiler didn’t disallow this pattern.

Contravariant field

Scala rejects the following definition. Why?

case class C[-A](a: A)

case class C[-A](a: A) // Error
                 // ^ contravariant type A occurs in covariant position in type A of value a

class C[-A](a: A)

val strAny: Any = "hello"
val cAny: C[Any] = C(strAny)
val cInt: C[Int] = cAny // Would be OK because Int <: Any
cInt.a - 1 // 😱

trait C[-A]:
  val a: A

class C[-A](a: A)

Double negation

Scala rejects the following definition. Why?

  trait C[-A]:
    def app(f: A => Int): Int

  trait C[-A]:
    def app(f: A => Int): Int // Error
            // ^ contravariant type A occurs in covariant position in type A => Int of parameter f

case class CIntOption(s: Option[Int]) extends C[Option[Int]]:
  override def app(f: Option[Int] => Int): Int =
    f(s)

val cOption: C[Option[Int]] = CIntOption(None)
val cSome: C[Some[Int]] = cOption // OK since Some <: Option
val boom = cSome.app((some: Some[Int]) => some.value) // 😱

Free and bound functions

Scala rejects the following definition:

  trait F[+A]:
    def f(a: A): A

… yet it accepts the following:

def f[A](a: A): A = a

Why?

  trait F[+A]:
    def f(a: A): A // Error
          // ^ covariant type A occurs in contravariant position in type A of parameter a

class FInt extends F[Int]:
  override def f(i: Int): Int = i + 1

val fInt = FInt()
val fAny: F[Any] = fInt // Ok since Any >: Int
fAny.f("Boom") // 😱

case class CSome() extends F[Some[Int]]:
  override def f(a: Some[Int]): Some[Int] =
    Some(a.value + 1)

val cSome: F[Some[Int]] = CSome()
val cOption: F[Option[Int]] = cSome // Ok since Option >: Some
cOption.f(None) // 😱

    def f[A](a: A) = a
    val fInt: Int => Int = f[Int]
    val fAny: Any => Any = fInt // Error
                        // ^^^^ Found:    (fInt : Int => Int)
                        //      Required: Any => Any

Extension methods

Scala rejects the following definition:

  trait Foldable1[+A]:
    def fold(a: A)(f: (A, A) => A): A

… yet it accepts the following:

trait Foldable2[+A]
extension [A](t: Foldable2[A])
  def fold(a: A)(f: (A, A) => A): A = ???

Why?

  trait Foldable1[+A]:
    def fold(a: A)(f: (A, A) => A): A // Error
             // ^               ^ covariant type A occurs in contravariant position in type (A, A) => A of parameter f
             // ^ covariant type A occurs in contravariant position in type A of parameter a

class FoldableInt extends Foldable1[Int]:
  override def fold(a: Int)(f: (Int, Int) => Int): Int =
    a + f(a - 1, a + 1)

var fInt = FoldableInt()
var fAny: Foldable1[Any] = fInt // OK since Int <: Any
fAny.fold("Foo")((x, y) => y) // 😱

Implementing classes with variance

Here is a simple trait for stacks:

trait Stack[T]:
  /** Peek at the top of this stack */
  def peek(): Option[T]

  /** Create a new stack with one more entry, at the top */
  def push(t: T): Stack[T]
  /** Separate the top entry from the rest of the stack */
  def pop(): (Option[T], Stack[T])

1. Write an implementation of this trait.

2. Write a function that takes a list of stacks and collects the top of each stack into a new stack.

   def joinStacks[T](l: List[Stack[T]]): Stack[T] =
     ???
   

   variance/src/main/scala/variance/Variance.scala

3. What happens if you try to call join with a mix of stacks with different element types (different Ts)? Can you even put two such stacks together in a list? Why or why not?

   def mkStackInt(): Stack[Int] =
     ???
   
   def mkStackString(): Stack[String] =
     ???
   
   // Does this work?
   // val tops = joinStacks(List(mkStackInt(), mkStackString()))
   

   variance/src/main/scala/variance/Variance.scala

4. Assume that we want to change Stack[T] to allow for multiple stacks with different T types to be placed together in a list. Is there a variance annotation for T that will allow this? Which one makes more sense?

   Try to perform the change by adding an annotation on T in Stack[T]. What problem do you run into? Why is this error reasonable? (What would go wrong otherwise?) Change the signature of push to make it work.

5. Is it always possible to turn an invariant trait into a covariant one? Consider the following example:

   trait Drawer[T]:
     def get(): T
     def put(t: T): Drawer[T]
   
   case class IncrementingDrawer(i: Int) extends Drawer[Int]:
     def get() = i - 1
     def put(j: Int) = IncrementingDrawer(j + 1)
   

   variance/src/main/scala/variance/Variance.scala

   Can you make Drawer covariant in T without breaking IncrementingDrawer?

6. From question 5, it is clear that covariance puts restrictions on what classes that implement a covariant trait can do (the same is true of contravariance). Based on this, can you think of a good reason not to make a container class (like a List or a Stack) covariant?

7. Here is another trait, similar to stacks, but storing at most one element. First give T an adequate variance annotation as in the Stack case (this will require other changes, of course), then implement the trait.

   trait Box[T]:
     /** Peek at the value inside the box */
     def unbox(): Option[T]
   
     /** Create a new box with the contents */
     def replace(t: T): Box[T]
     /** Create a new box by applying `f` to the contents of this one */
     def map[T2](f: T => T2): Box[T2]
   

   variance/src/main/scala/variance/Variance.scala

8. Both of these traits have a way to inspect one element of the container. Change both of them to extend the following HasTop trait, which captures this property.

   trait HasTop[+T]:
     /** Peek at one value inside this container */
     def top: Option[T]
   

   variance/src/main/scala/variance/Variance.scala

9. Drawer[T] is required to be invariant to be compatible with IncrementingDrawer, but HasTop[+T] is covariant in T. Can Drawer[T] implement HasTop[T] without breaking IncrementingDrawer?

10. Rewrite the join operation to work on lists of HasTop instances, rather than stacks. Does this join still work if you remove the covariance annotation on T in Box and Stack? Why?

    def joinTops[T](l: List[HasTop[T]]): List[T] =
      ???
    

    variance/src/main/scala/variance/Variance.scala

A variance puzzle 🔥

Assume the following two classes or traits…

C[-A, +B]
F[ A, +B] extends C[A, B]

… and the following subtyping relationships…

A <: B
X <: Y

… what are the relations between the following pairs?

• C[A, Y] and F[B, X];
• F[A, X] and C[A, Y]?

class C[-A, +B]
class F[ A, +B] extends C[A, B]

def assertSubtype[A, B >: A]: Unit = {}
def assertSupertype[A, B <: A]: Unit = {}

def test[B, A <: B, Y, X <: Y]: Unit =
  assertSubtype[C[A, Y], F[B, X]] // Error
  assertSupertype[C[A, Y], F[B, X]] // Ok
  assertSubtype[F[A, X], C[A, Y]] // OK
  assertSupertype[F[A, X], C[A, Y]] // Error

Exercises from the slides

Array Typing Problem

Arrays in Java are covariant, but covariant array typing causes problems. Do you know why?

To see why, let’s explore with an example:

Consider a class IntSet that defines binary trees storing sets of integers. A set of integers is either an empty set represented by an empty tree, or a non-empty set stored in a tree that consists of one integer and two subtrees. In Java, IntSet can be implemented as follows:

sealed interface IntSet permits Empty, NonEmpty {}
final class Empty implements IntSet {}
final class NonEmpty implements IntSet {
  private final int elem;
  private final IntSet left, right;
  public NonEmpty (int elem, IntSet left, IntSet right) {
    this.elem = elem;
    this.left = left;
    this.right = right;
  }
}

In Scala, IntSet would be written as follows:

sealed trait IntSet
case class Empty() extends IntSet
case class NonEmpty(elem: Int, left: IntSet, right: IntSet) extends IntSet

Now consider the Java code below:

NonEmpty[] a = new NonEmpty[]{
  new NonEmpty(1, new Empty (), new Empty())};
IntSet[] b = a ;
b[0] = new Empty();
NonEmpty s = a[0];

It looks like in the last line, we assigned an Empty value to a variable of type NonEmpty! What went wrong?

The problematic array example would be written as follows in Scala:

val a: Array[NonEmpty] = Array(NonEmpty(1, Empty(), Empty()))
val b: Array[IntSet] = a
b(0) = Empty()
val s: NonEmpty = a(0)

When you try out this example, what do you observe?

1. A type error in line 1
2. A type error in line 2
3. A type error in line 3
4. A type error in line 4
5. A program that compiles and throws an exception at run-time
6. A program that compiles and runs without exception

Liskov Substitution Principle

The Liskov Substitution Principle (LSP) tells us when a type can be a subtype of another:

If A <: B, then everything one can do with a value of type B one should also be able to do with a value of type A.

Assume the following type hierarchy and two function types:

trait Fruit
class Apple extends Fruit
class Orange extends Fruit
type A = Fruit => Orange
type B = Apple => Fruit

According to the LSP, which of the following should be true?

1. A <: B
2. B <: A
3. A and B are unrelated.

Prepend

Consider adding a prepend method to List which prepends a given element, yielding a new list.

1. A first implementation of prepend could look like this:

   trait List[+T]: 
      def prepend(elem: T): List[T] = Node(elem, this)
   

   But that does not type-check. Why?

   1. prepend turns List into a mutable class.
   2. prepend fails variance checking.
   3. prepend’s right-hand side contains a type error.

2. Given the second implementation of prepend:

   trait List[+T]: 
     def prepend [U >: T] (elem: U): List[U] = Node(elem, this)
   

   What is the result type of this function (Apple <: Fruit, Orange <: Fruit):

   def f(xs: List[Apple], x: Orange) = xs.prepend(x)
   

   Possible answers:

   1. does not type check
   2. List[Apple]
   3. List[Orange]
   4. List[Fruit]
   5. List[Any]

Specifications

Reasoning about your code requires specifying what it is supposed to do??

In Scala, it’s common to use require and ensuring to specify pre- and post-conditions for functions, respectively. The require method checks a given condition (usually an input validation) and throws an IllegalArgumentException if the condition is not met. On the other hand, ensuring is used to validate the result of a function. It takes a predicate that the result must satisfy, and if not, an assertion error is thrown.

For example:

val eps = 0.00001f

def sqrt(x: Double): Double = {
  require(x >= 0)
  Math.sqrt(x)
} ensuring (res =>
    (x - res * res) <= eps && (x - res * res) >= -eps
)

The following exercises will make writing such specs second nature!

Debugging with tests and specs

Bad combinatorics ⭐️

Consider the following incorrect function:

/** Construct all subsets of `s` of size `k` (INCORRECT!) */
def badCombinations[T](set: Set[T], k: Int): Set[Set[T]] = {
  if k == 0 then Set(Set())
  if set.isEmpty then Set()
  else
    for
      item <- set
      rest = set - item
      subset <- Iterable.concat(
        for s <- badCombinations(rest, k - 1) yield rest + item,
        for s <- badCombinations(rest, k) yield rest
      )
    yield subset
}

1. Read this function carefully.

2. Which inputs are meaningful for this function? Write a require clause to rule out meaningless arguments. Check that your require clause works by calling this function with invalid arguments in a worksheet and confirming that it raises an exception.

3. Unit tests are a great way to ensure that corner cases are correctly handled. Create a new test suite class in src/test/scala/specs/SpecsSuite.scala (you can consult a previous-week exercise set or lab for inspiration, or the munit documentation), then write a unit test that asserts that this function computes the right result when called with an empty set as input (use assertEquals and Set()).

4. Make sure that your test runs and reports a failure (it should, since this function is incorrect). You can use sbt testOnly -- *your-test-name* to run your test.

5. Find the bug that leads to an empty set being returned, and confirm that the unit test now passes.

6. What does the documentation of this function promise? Write an ensuring clause to capture this formally. Is this a complete specification? (A specification is complete if any function that respects it is a correct implementation of the original requirements — here, the documentation string).

7. Find an input for which this function violates the postcondition that you just wrote. Confirm your conjecture by calling this function in a worksheet and confirming that the ensuring clause throws an exception.

8. Correct the remaining bugs in this function. You may find it useful to add tracing instructions to observe its behavior.

9. Bonus question: Is your corrected function efficient? Look carefully at the work it does on a simple example. Do you spot any redundant work?

Bad transactions

The following code defines a class BankAccount and associated operations deposit, withdraw and transfer:

protected class BankAccount(private var _balance: Double):
  import AccOpResult.*

  def balance = _balance

  private def updateBalance(amount: Double): AccOpResult =
    val oldBalance = balance
    _balance = amount
    Ok(oldBalance)

  /** Deposits the specified amount into the bank account.
    *
    * @param amount
    *   The amount to be deposited. Must be non-negative.
    */
  def deposit(amount: Double): AccOpResult = {
    updateBalance(balance + amount)
  }

  /** Withdraws the specified amount from the bank account.
    *
    * @param amount
    *   The amount to be withdrawn. Must be non-negative.
    */
  def withdraw(amount: Double): AccOpResult = {
    if balance >= amount then
      updateBalance(balance - amount)
    else
      InsufficientFund(balance)
  }

  /** Transfers the specified amount from this bank account to `that` bank
    * account.
    *
    * @param amount
    *   The amount to be transferred. Must be non-negative.
    */
  def transfer(that: BankAccount, amount: Double): (AccOpResult, AccOpResult) = {
    if this.balance >= amount then
      (this.withdraw(amount), that.deposit(amount))
    else
      (InsufficientFund(this.balance), Ok(that.balance))
  }

Type AccOpResult is used to memorize a “screenshot” of the balance before the operation and whether the operation is successful:

enum AccOpResult:
  case Ok(oldBalance: Double)
  case InsufficientFund(oldBalance: Double)

1. Write the preconditions and postconditions for the functions deposit, withdraw and transfer using require and ensuring.
2. Can you identify the bugs in the code that violate these conditions?

Translating specs from English

Ambiguous specs

The following statements are ambiguous. For each of them, explain the ambiguity (either in words, or by giving at least two different, unambiguous expressions in Scala code that are compatible with the original sentence):

1. “Access to the system is restricted to senior engineers and developers.”
2. “The argument to this function must be a supertype of a serializable type that implements IsFinite”
3. “Only finite Double lists are supported.”
4. “Any sibling of a node that makes a request must be ready to process answers.”
5. “Objects passed to this method must be unlockable.”

Translating simple specs ⭐️

Translate the following English statements to mathematical statements or to Scala code. Aim to be as succinct and clear as possible; do not optimize for performance. For some statements, it may not be possible to write Scala code (which ones?).

1. The list of integers l is sorted in ascending order
2. All values in map m1 are keys in map m2.
3. Even numbers are always immediately followed by odd numbers in list l.
4. There are no negative numbers in the output of function f.
5. Functions f and g compute the same output when given a positive number.
6. List l1 is a permutation of list l2.
7. Number p is prime.

Paths and cycles

Translate the following English statements to Scala code:

A path is a nonempty sequence of edges (pairs of points) such that the endpoint of each edge is the starting point of the next edge.

A cycle is a path whose starting point equals its endpoint.

case class Edge[+Point](src: Point, dst: Point)

def isPathMap[Point](edges: Seq[Edge[Point]]): Boolean =
  !edges.isEmpty && edges.map(_.dst).dropRight(1) == edges.drop(1).map(_.src)

def isPathSliding[Point](edges: Seq[Edge[Point]]): Boolean =
  // “A *path* is a nonempty sequence of edges”
  !edges.isEmpty &&
    edges.sliding(2).forall {
      case Seq(e0, e1) =>
        // such that the endpoint of each edge
        e0.dst
        // is the starting point of the next edge.
          == e1.src
    }

def isPathFold[Point](edges: Seq[Edge[Point]]): Boolean =
  !edges.isEmpty &&
    !edges.tail.foldLeft[Option[Edge[Point]]](Some(edges.head)) {
      case (Some(e0), e1) => if e0.dst == e1.src then Some(e1) else None
      case _              => None
    }.isEmpty

def isPathRec[Point](edges: Seq[Edge[Point]]): Boolean =
  def consistent(first: Edge[Point], rest: Seq[Edge[Point]]): Boolean =
    rest.isEmpty ||
      (first.dst == rest.head.src &&
        consistent(rest.head, rest.tail))
  !edges.isEmpty && consistent(edges.head, edges.tail)

def isPathRecMatch[Point](edges: Seq[Edge[Point]]): Boolean =
  def consistent(edges: Seq[Edge[Point]]): Boolean =
    edges match
      case e0 :: e1 :: tl => e0.dst == e1.src && consistent(e1 :: tl)
      case _              => true
  !edges.isEmpty && consistent(edges)

def isCycleEq[Point](edges: Seq[Edge[Point]]): Boolean =
  isPathMap(edges) && edges.head.src == edges.last.dst

def isCycleCons[Point](edges: Seq[Edge[Point]]): Boolean =
  isPathMap(edges.last +: edges)

Course policies

This course has a reasonably complex grading policy: one lab is dropped, we accept medical reasons for skipping a lab, callbacks combine with labs, we have a midterm and a final, etc.

Translate the grading policy of this course (found in Overall Grade) into a Scala function, OverallGrade. First, start with the easy version:

def OverallGrade(labScore: Double, midtermScore: Double, finalScore: Double): Double =
  ???

🔥 Then, try the full grading policy.

def OverallGrade(labScore: Double, midtermScore: Double, finalScore: Double): Double =
  val overallScore = labScore * 0.3 + midtermScore * 0.3 + finalScore * 0.4
  (((5.25 * overallScore + 0.875) * 4).round * 0.25).min(6.0)

Finding incompleteness in specs ⭐️

The following ensuring specifications are incomplete: they do not detect all incorrect behaviors.

For each one, replace the existing function body with an incorrect implementation that still obeys the ensuring clause, then find an input that proves that your modified function is incorrect and confirm that the ensuring clause is incomplete by checking that it does not raise an assertion.

1. def filterWithIncompleteSpec[T](l: List[T], p: T => Boolean) = {
     l.filter(p)
   } ensuring (res => res.forall(p))
   

   specs/src/main/scala/specs/Specs.scala

2. def mapWithIncompleteSpec[T, Q](ts: List[T])(f: T => Q) = {
     ts.map(f)
   } ensuring (qs =>
     qs.length == ts.length &&
       qs.forall(q => ts.exists(t => f(t) == q))
   )
   

   specs/src/main/scala/specs/Specs.scala

3. def flattenWithIncompleteSpec[T](tss: List[List[T]]) = {
     tss.flatten
   } ensuring (ts =>
     ts.length == tss.map(_.length).sum &&
       tss.forall(ts.containsSlice(_))
   )
   

   specs/src/main/scala/specs/Specs.scala

© 2023–2025 EPFL. All rights reserved.