Last updated on Monday, September 29, 2025

Week 2 debrief: Higher-order functions, equational reasoning

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

Administrivia

• Monday is a holiday! Take this opportunity to learn a bit of Git, wrap up the boids lab, and have some higher-order fun!

• If you have an exam-lab scheduled, make sure that you’re familiar with the course policies and exam-lab logistics, and… don’t forget to submit your code before the end of the exam! A few students among Wednesday’s exam-lab takers forgot… and were not able to retrieve their code later: they had to start over. Just like in the final, you can’t count on unsubmitted code being available or graded.

• Similarly, don’t forget to submit each lab by the deadline! If you leave one as draft, if won’t be graded. It’s easy to confirm whether you lab has been counted: just wait a few minutes and check whether a grade has appeared on Moodle.

• Our training VMs are available at most times, and so are the exam VMs during every exam-lab slot (to everyone, not just test takers). Take these opportunities to get familiar with the VDI environment ahead of the final!

Interesting links and Ed questions

• Recursion

  • Why should product(Nil) be 1?

• Higher order functions

  • What is the difference between higher-order and first-class functions?

• Logistics

  • How do I access the Boids simulation UI from my Windows browser while running the server in WSL2?
  • I submitted my code and got a grade, but Moodle says “Not submitted”; am I OK?
  • Is it OK to use var?

• Interesting discussions

  • Do the data abstraction slides assume that denominators are positive?
  • A nice example of using Git history to answer a language question (fr)

What should product and allEven return for empty lists?

Here are two ways to think of these:

Simplicity

You could make these functions throw an exception for empty lists. Here is what this would look like for product:

def product(l: IntList):
  if l.isEmpty then throw new InvalidArgumentException("Empty!")
  else if l.tail.isEmpty then l.head
  else l.head * product(l.tail)

But! Perhaps we could make this nicer if we allowed ourselves to return a different value for empty lists. What should this value be?

def product(l: IntList):
  if l.isEmpty then ???
  else l.head * product(l.tail)

Let’s see by substitution:

product(IntCons(3, IntNil))
3 * product(IntNil)
3 * ???

So ??? should be such that 3 * ??? = 3. Hence, product(IntNil) should be 1!

Desirable properties

Another way to think of this issue is to think of what properties we want our functions to have:

• allEven(L) should be the same as not(anyOdd(L)). Are there any odd numbers in the empty list? No, so anyOdd(L) is false, and hence allEven(L) must be true!

• Using A ++ B to denote the concatenation of two lists A and B, what should be the value of product(A ++ B)? Intuitively, we would like it to be product(A) * product(B).

  Now take B == IntNil. Then A ++ B is simply A, and hence product(A) = product(A ++ B) = product(A ++ IntNil) == product(A) * product(IntNil), which means that product(IntNil) must be 1!

How to return a function?

Let’s start with a small exercises:

def f(x: Int, y: Double)(z: Boolean): String = ""

What are the types of the following expressions?

• f
• f(1, 2.3)
• f(1, 2.3)(true)
• f(1, 2.3, true)

Now, knowing this, let’s write a curried version of the add function. Normally, add has type (Int, Int) => Int. Given two numbers x and y, add(x, y) returns x + y. But! We want a version of add that can easily be partially applied. So we want to create an add with type Int => Int => Int. This can be written in any of the following ways:

val add: Int => Int => Int

def add(x: Int): Int => Int

def add(x: Int)(y: Int): Int

For the sake of the example, we let’s start with the second one. We take one int x: Int, and we must return a function Int => Int, so we create a function addX of that type and return it:

def add(x: Int): Int => Int =
  def addX(y: Int): Int =
    ???
  addX

Now, implementing addX is trivial.

def add(x: Int): Int => Int =
  def addX(y: Int): Int =
    x + y
  addX

This solution does what we want, but we can still do some refactoring to make it nicer. Let’s start by rewriting addX from def to a val, thus changing our implementation to use an anonymous function.

def add(x: Int): Int => Int =
  val addX = (y: Int) =>
    x + y
  addX

Now we can just inline addX to get:

def add(x: Int): Int => Int =
  (y: Int) => x + y

From there, we can easily change to the second form of add, above:

def add(x: Int)(y: Int): Int = x + y

Alternatively, can easily switch to the first form, with a val:

val add = (x: Int) => (y: Int) => x + y

That’s three ways to express the same functionality. Which one should we use in general? Read on to find out!

To curry or not to curry? The many ways to define a function

With higher-order-functions, we have seen lots of different ways to define functions. You now have two dimensions of choice:

• Currying VS not currying
• Named VS anonymous

There is also the option of defining your function as a val or a def.

Named VS Anonymous

Whether you name your function or not is a matter of succinctness.

Naming a function is advantageous when

• It will be called from many different places, or
• The functionality is complex enough to require a name

Often, we have very simple functionality that doesn’t require a name. The two following blocks of code show the same function written in an anonymous and named way respectively. Would you prefer reading this:

studentResults.filter(_.grade > 5)

Or this?

def hasGradeGreatedThan5(s: StudentResult) =
  s.grade > 5
studentResults.filter(hasGradeGreaterThan5)

The second one is much longer and hence much more distracting to read.

In principle, you should use anonymous functions for small functions that are meant for a very specific and simple task that you are using in a single place. It makes the code smoother to read.

Currying or not currying, that is the question

Currying a function means transforming a function that takes multiple arguments to multiple functions that each take part of the arguments. For example, the following function:

def add(x: Int, y: Int): Int = x + y

can be curried this way:

def addCurried(x: Int)(y: Int): Int = x + y

This is useful when you want to create partially applied functions.

For example, we can use addCurried to create a function that always add 5 to its parameter:

val add5 = addCurried(5) // 'add5' is a function of type (Int) => Int
println(add5(3)) // prints 8

Suppose you want to implement logging in your program. To do this, you implement this method:

def log(component: String, message: String): Unit =
  println(s"[$component] $message")

Each part of your program uses a different value for component, so that you know exactly from where each log message comes from.

But you end up with a lot of duplicated code. Within one part of your code, the component value is the same for all log calls. Isn’t there a way to simplify this? Yes, currying!

You redefine your function as:

def logCurried(component: String)(message: String): Unit =
  println(s"[$component] $message")

Then, in each part of your code, you create a logger that only gets used there. For example, if you have a server component:

val logger = logCurried("SERVER")

// Later in the server code
logger("Received request")

This is what we mean when we say partially applied functions, and this is where currying shines.

We’ll see more examples of this throughout the course.

val or def

Functions can be defined using either val or def, so which one should you use? For example, when defining a curried version of addition, is it better to write this def?

def add(x: Int)(y: Int): Int = x + y

… or this val?

val add = (x: Int) => (y: Int) => x + y

In practice, def is the most commonly used: use it by default. When the function is needed repeatedly as a value, use val. def can also be used, but will take a small amount of time to translate to a value every time it is used as one, thus val can provide slightly better performance in such cases. Thus, a good rule of thumb is to use def when defining functions that will mostly be called directly, and val for functions that will mostly be passed to other functions.

val numbers = List(1, 2, 3, 4, 5)

def add1(x: Int, y: Int): Int = x + y

object Math:
  def add2(x: Int, y: Int): Int = x + y

@main def run() =
  def internalAdd(x: Int, y: Int): Int = x + y

  val add3: (Int, Int) => Int = (x: Int, y: Int)=> x + y

  // All of these can be used in the same way
  println(numbers.foldLeft(0)(add1))
  println(numbers.foldLeft(0)(Math.add2))
  println(numbers.foldLeft(0)(internalAdd))
  println(numbers.foldLeft(0)(add3))

  // val has slightly better performance if used repeatedly as a value
  val numbers2 = List(6, 7, 8, 9, 10)
  val numbers3 = List(11, 12, 13, 14, 15)
  println(numbers.foldLeft(0)(add3))
  println(numbers2.foldLeft(0)(add3))
  println(numbers3.foldLeft(0)(add3))

There is one case in which def versus val makes a major difference, however: when the definition itself has side effects. val is evaluated immediately; def is delayed until it is called.

For example, here are four code fragments. Can you say what each of them prints?

val add1v =
  println("Oh! A val!");
  (x: Int) => x + 1

def add1d =
  println("Oh, a `def`!");
  (x: Int) => x + 1

add1v(2)

add1d(2)

val add1v =
  println("Oh! A val!");
  (x: Int) => x + 1
// Prints "Oh! A val!"

def add1d =
  println("Oh, a `def`!");
  (x: Int) => x + 1
// Does not print anything

add1v(2)
// Returns 3, does not print anything

add1d(2)
// Prints "Oh, a `def`!", then returns 3

© 2023–2025 EPFL. All rights reserved.