Last updated on Saturday, October 10, 2026

Week 5: Collections, subtyping and (more) proofs

Congrats on completing your fifth week of CS-214! Here is a round-up of interesting questions, tips for exercises and labs, and general notes about the course.

Administrivia

• Callback: the unguided callback starts this week. Please read the instructions carefully, and submit your team and proposal on Moodle by Friday 16 October 6pm.
• Feedback: please fill out this semester’s indicative feedback for this course through ISA. Your feedback is valuable as it helps us continuously improve CS-214.
• Exam training: starting upcoming Wednesday, we will organise optional additional training with exam labs. We will assign everyone an additional exam lab session, so that you get another chance to practice, if you wish.

Tips and interesting Ed questions

• How to improve performance using tail-recursion? And beyond tail-recursion?.
• FoldLeft versus FoldRight?

The type puzzle

Programming can be seen as a puzzle where we need to find an implementation that satifes our constraints. For typed programming languages, such as Scala, the type of the function that we wish to implement is one of such constraints that we need to satisfy. Finding a term of this type is the goal. The actions that we can take in this puzzle are selecting terms (functions, values) and composing them with one another (function application, pattern matching, etc). The tactic, or strategy, is how we decide which actions to explore.

When unsure how to proceed with the implementation of a function, you can try to start by focussing first on these type constraints. For certain programs, in particular polymorphic ones, there is often only a handful of implementations that satisfy these type constraints, and they can be found methodically.

Let’s walk through a simple example. In particular, we’ll try to find the implementation of listOfDuplicates using a structured approach. The solution might seem obvious, but it helps illustrate the process.

The goal of our puzzle is to implement a function listOfDuplicates of the type A -> Nat -> List[A], for some type A.

Step 0

Our journey starts with a blank slate:

def listOfDuplicates[A](x: A)(length: Nat): List[A] = ?

Goal: List[A]

Terms:

• x : A
• length : Nat
• Nil : List[A]
• _::_ : A -> List[A] -> List[A]
• listOfDuplicates : A -> Nat -> List[A]

Action: pattern match on length

Step 1

We now find ourselves here:

def listOfDuplicates[A](x: A)(length: Nat): List[A] =
    if length == 0 then
        ?
    else 
        ?

Goal: List[A] (first ?) and List[A] (second ?)

Terms: as before

Action: use Nil to satisfy the first goal

Step 2

Let’s update our state:

def listOfDuplicates[A](x: A)(length: Nat): List[A] =
    if length == 0 then
        Nil
    else 
        ?

Goal: List[A]

Terms: as before

Action: use x ::_

Step 3

The current state:

def listOfDuplicates[A](x: A)(length: Nat): List[A] =
    if length == 0 then
        Nil
    else
        x :: ?

Action: use listOfDuplicates x (length - 1)

Step 4

This gives us a solution, and one that seems rather sane as well. Hurray!

def listOfDuplicates[A](x: A)(length: Nat): List[A] =
    if length == 0 then
        Nil
    else
        x :: listOfDuplicates(x, length - 1)

Hopefully this particular example helped illustrate a methodical approach to finding the right implementation. As you saw, it is not decisive. Sometimes you need to use your judgement to rule out “suspicious” certain steps – it is part science, part art. Nevertheless, it can help structure your way towards a solution.

Debugging tests

It can be overwhelming when SBT prints out a long list of failing tests back to you. In general, we recommend the following process:

1. Start by testing each of your functions on small inputs, in a worksheet. (If you have trouble configuring worksheets, ask us in help sessions!)
2. Once you’re confident that your code is correct, locate the corresponding tests:
   1. Open the test suite files under src/test/scala/.
   2. Identify the ones that use your function, and try to get a sense of what they do.
3. Run only the relevant tests, using testOnly.
4. If a test fails, clear your terminal, then rerun just that one, using testOnly.
5. If it’s not clear what’s happening, copy the test to your worksheet, and experiment there.

Enum value scope

In the following code snippet, it may seem strange that we can’t simply refer to Empty and Cons in the FullEvaluator block. Instead, we need to import the enum value names using import Ctx.*

object FullEvaluator:
  enum Ctx:
    case Empty
    case Cons(name: String, v: Double, tail: Ctx)

  import Ctx.* // why??

The reason is to remove ambiguity. The names of the enum values are scoped to the enum itself; that is, only within the enum object can you use that directly. Outside the enum block, you need to prefix them with Ctx. The following example shows why this is needed:

object FullEvaluator:
  enum KeyValueCtx:
    case Empty
    case Cons(key: String, value: Double, tail: KeyValueCtx)

  enum CounterCtx:
    case Empty
    case Cons(counter: Int, tail: CounterCtx)

  // to which enum would `Empty` belong, if referenced here?

When the recursive tail can’t be optimised

In pursuit of tail-recursion optimisation, one might write class A’s count with an accumulator, and assume the compiler applies the optimisation.

class A {
  def count(n: Int, acc: Int): Int =
    if (n == 0) acc else count(n - 1, acc + 1)
}

class B extends A {
  override def count(n: Int, acc: Int): Int = {
    println(s"$n")
    super.count(n, acc)
  }
}

new B().count(3, 0) // prints 3, 2, 1, 0

However, if we annotate the count method in class A with @tailrec, we’ll receive the following compiler error: TailRec optimisation not applicable, method count is neither private nor final so can be overridden.

Without TCO, calling B.count will invoke A.count, which in turn will invoke B.count on the recursion due to dynamic dispatch. If the compiler were to apply TCO on A.count it would not invoke B.count anymore. As such the optimisation wouldn’t be behaviour preserving, and therefore the compiler does not apply it.

This example shows why annotating with functions with @tailrec can be useful if you expect them to be tail-recursive.

Code-quality improvements

Here are a few common code smells and code style improvements, based on your lab submissions:

Use the curried argument lists

Instead of writing a lambda that just passes the arguments to another function, it is often possible to just use the function.

Before:

def curriedAdd(a: Int)(b: Int): Int = a + b
xs.map(x => curriedAdd(1)(x))

or

def curriedAdd(a: Int)(b: Int): Int = a + b
xs.map(curriedAdd(1)(_))

After:

def curriedAdd(a: Int)(b: Int): Int = a + b
xs.map(curriedAdd(1))

Let the collection combinator handle the edge case

When writing code using collection combinators, it is often unnecessary to explicitly handle edge cases. Opt for a simpler implementation if the result stays the same.

Before:

if xs.isEmpty then Nil
else xs.takeWhile(_ > 0)

After:

// Nil.takeWhile(_ > 0) == Nil
xs.takeWhile(_ > 0)

More functions != better code

If your inner (recursive) function has the same signature as the outer one, and the outer function doesn’t do anything more, maybe you don’t need the inner function.

Before:

def outer(xs: List[Int]): Int =
  def inner(xs: List[Int]): Int =
    xs match
      case Nil => 0
      case x :: rest => x + inner(rest)
  inner(xs)

After:

def outer(xs: List[Int]): Int =
  xs match
    case Nil => 0
    case x :: rest => x + outer(rest)

© 2023–2026 EPFL. CC BY 4.0.