Last updated on Monday, September 29, 2025

Week 3 debrief: pattern matching, calculator lab, and computational complexity

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

Administrivia

Please resubmit find-hof. The fastest among you caught our autograder by surprise on Wednesday night. If you submitted your find-hof callback on Wednesday and experienced didn’t receive a grade, please resubmit your patch (you can use the “Add a new attempt based on previous submission” button).

We have extra help sessions on Mondays. To get help working on the lab, come to the Monday help sessions! This is especially useful if you have an exam-lab that week, since you won’t have time on Wednesday to ask questions. This Monday’s help session will be held in INM 200, ELA 1, and MED 0 1418.

Callbacks and labs are graded. Labs and callbacks are both graded. More details about grading, including how scores are distributed between labs and callbacks, are in our course policies.

Please use the debugging guide. The debugging lecture contains a guide on how to ask questions on Ed, and on how to debug. A dedicated Ed thread guides you on how to share code online. Please follow these guides when asking questions on Ed: learning to debug is an objective of this class, and asking good questions shows respect for the time and efforts of our student assistants. Thanks!

Interesting questions on Ed

• toInt(n) calls itself recursively with n; why doesn’t that cause an infinite loop?
• Can I reuse min when implementing minMax?

A tip for calculator: debugging failing tests

The calc lab is designed to exercise your debugging abilities. If you run into an issue (for example an incomplete simplification), use the debugging guide! The key aspect here is to simplify and minimize: do not spend time attempting to understand a very large and complex random test.

Instead:

1. Simplify the test by repeatedly removing parts of it, until you converge to a minimal test.

2. Confirm that you understand what the code is supposed to do:

   a. Start by computing by hand what should happen (not by following your code; by following the problem statement).

   b. Then, confirm that this is the expected test result: if not, you misunderstood the problem statement.

3. Debug your code:

   a. Confirm that you understand what it does by running it by hand, comparing the result to what it produces in a worksheet. If the two do not match, you misunderstood how Scala works.

   b. Compare the execution of your code with the notes you made in step 2. Where do things diverge?

4. Fix the issue: step 3 should tell you precisely where things go wrong.

If you need help, ask on Ed or in person, but make sure to show us what you attempted.

Deep dives

If your recursive functions run too slowly…

Consider the following function:

/** Returns the maximum value of the list. */
def max(l: IntList): Int = l match
  case IntNil                                  => 0
  case IntCons(head, tail) if head > max(tail) => head
  case IntCons(head, tail)                     => max(tail)

We write some code that uses it:

object IntList:
  def repeat(num: Int, times: Int): IntList =
    if times == 0 then IntNil else IntCons(num, repeat(num, times - 1))

val list = IntList.repeat(5, 50)
val maxOfList = max(list) // runs forever

And max runs seemingly forever, even for a small list of 50 elements! Can you find out why it does? (Hint: Use substitution method to find out how many recursive calls to max do we make)

We can compute the same result while recursing fewer times by computing max(tail) only once and remembering the result in a val. This means max will be called only once per element in the list.

/** Returns the maximum value of the list. */
def maxLinear(l: IntList): Int = l match
  case IntNil => 0
  case IntCons(head, tail) =>
    val tailMax = maxLinear(tail)
    if head > tailMax then head else tailMax

We will see similar analyses in week 6.

Useful pattern matching syntax 🚀

Wildcard patterns

You can use _ to discard a part of the pattern. E.g.

case Cons(_, Cons(_, tail)) =>
  // `_` doesn't capture any value

Given a following function matchHead:

def matchHead(list: IntList, target: Int) =
  list match
    case IntCons(head, tail) =>
      if head == target then print(s"Head matches: $target :)")
      else print(s"Head doesn't match :(")
    case IntNil => print(s"Head doesn't match :(")

Can you rewrite it so it uses wildcard patterns?

def matchHead(list: IntList, target: Int) =
  list match
    case IntCons(head, _) =>
      if head == target then print(s"Head matches: $target :)")
      else print(s"Head doesn't match :(")
    case _ => print(s"Head doesn't match :(")

If guards

Scala lets you add extra conditions in case branches by using a “pattern guard”, written case pattern if guard. Both the pattern and the guard need to be satisfied to enter the branch. For example:

case IntCons(head, _) if head >= 0 =>
  ??? // only lists starting with non-negative number fall here
case _ =>
  ??? // all else falls hare

Can you rewrite matchHead above so it takes advantage of if guards?

def matchHead(list: IntList, target: Int) =
  list match
    case IntCons(head, _) if head == target =>
      print(s"Head matches: $target :)")
    case _ => print(s"Head doesn't match :(")

Checking for equality

You can also check for equality using pattern matching directly. To do so, either include the target of the comparison in backticks, or use a name that starts with a capital letter.

val apple = "I have an apple"
val Bananas = "I have some bananas"

x match // x has type String here
  case `apple` => // matches if x == "I have an apple"
  case Bananas => // matches if x == "I have some bananas"
  case apple =>
    // matches any x
    // this will also define a new variable target with value equal to x that will shadow val apple = "I have an apple"

Can you rewrite matchHead above so it takes advantage of equality checks?

def matchHead(list: IntList, target: Int) =
  list match
    case IntCons(`target`, _) => print(s"Head matches: $target :)")
    case _ => print(s"Head doesn't match :(")

def matchHead(list: IntList, Target: Int) =
  list match
    case IntCons(Target, _) => print(s"Head matches: $Target :)")
    case _ => print(s"Head doesn't match :(")

Two classic debugging stories

Here is an interesting debugging story from OpenOffice:

• Open Office doesn’t print on Tuesdays

And here is another amusing debugging story:

• We can’t send mail more than 500 miles

(The lecture slides have additional links to good resources on debugging.)

© 2023–2025 EPFL. All rights reserved.