Last updated on Wednesday, January 21, 2026

Week 2: Higher-Order Functions and Debugging

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

• In the first part of this exercise set, we’ll revisit week 1’s exercises, and search for ways to leverage the power of higher-order functions to write shorter, simpler code. This first part is important for this week’s lab, and it will work much better if you work in groups.

• In the second part of this exercise set, we’ll make ourselves familiar with the notion of “functions as values”. We’ll store functions in vals, combine them, make functions that make functions that make functions, etc. We also encourage you to work in groups on this part.

• Finally, in the third part of this exercise set, we’ll train your debugging skills based on the SE lectures.

As before, ⭐️ indicates the most important exercises and questions and 🔥 indicates the most challenging ones. 🔜 indicates exercises that are useful to prepare for future lectures.

You do not need to complete all exercises to succeed in this class, and you do not need to do all exercises in the order they are written.

Higher-Order Functions

This week, we’re trying something a bit different. At the front of the class you should find a stack of printed index cards (also available here), containing the solutions to all of the list function problems of week 1. Here is the protocol:

1. Form a small group (2 to 4 people).
2. Come to the front of the class to pick up a sheet of index cards (two pages).
3. Cut the sheets into individual cards.
4. Start working on exercises. The cards will be useful in “Part 1: Observation” and “Part 2: Conjecture”.

Higher-order functions on lists and trees ⭐️

You may have noted that we asked to write very similar code many, many times in last week’s exercises. Let’s explore this observation in more detail.

Part 1: Observation ⭐️

Let’s look at five categories of functions, each illustrated by a pair of recursive functions from last week’s exercises. In your stack of index cards, find the cards for the following functions:

• sum and product (we’ll call this pair “associative”)
• increment and capAtZero (we’ll call this pair “map”)
• collectEven and removeZeroes (we’ll call this pair “filter”)
• countEven and multiplyOdd (we’ll call this pair “foldRight”)
• min and last (we’ll call this pair “reduceRight”)

Read the implementation of these functions carefully. For each pair, ask yourself: what do these two functions have in common? Which parts differ? Use underlines, colors, or boxes to highlight the differences (you can write on the cards).

Once you’re done, put each of these pairs down, leaving some space around each pair to add more cards.

Part 2: Conjecture ⭐️

Let’s see how well the patterns that you have found generalize.

1. You should have about 20 cards left. Try to classify each card into one of the five categories above, based on how well it fits the pattern that you identified earlier. If you feel that you need more categories, that’s OK. Oh, and beware: two of the cards don’t fit!

   Hint

   In particular, you may decide that allEven/allPositiveOrZero and anyOdd/anyNegative should be their own categories. That’s fine!

   Hint

   reverseAppend and init are the ugly ducklings. reverseAppend is an instance of a different pattern (a “left fold”) that we will study later.

2. Find another group of students, and compare your results with them. Do you agree on everything? Did you create the same additional categories? If you disagree, is it because one category is a special case of another one?

   Hint

   If you look very carefully, you will see that all categories are special cases of “fold” and “reduce”.

Part 3: Experiment ⭐️

Time for higher-order functions! Take the categories above one by one, and for each of them, write one single function that is more general than all the examples belonging to that category. To help with this, consider starting with the following warm-up exercise:

Warm-up

Higher-order functions can be used to “abstract away” part of a function.

1. Consider the following two functions, which check whether the head of a list has a certain property, and return false if the list is empty:

   def headIsEven(l: IntList): Boolean =
     !l.isEmpty && l.head % 2 == 0
   def headIsPositive(l: IntList): Boolean =
     !l.isEmpty && l.head > 0
   

   higher-order-functions/src/main/scala/hofs/fun.scala

   The bodies of these functions are very similar, so we can abstract away the common parts into a separate higher-order function (a function that takes a function):

   def headHasProperty(p: Int => Boolean, l: IntList): Boolean =
     !l.isEmpty && p(l.head)
   

   higher-order-functions/src/main/scala/hofs/fun.scala

   Now, use headHasProperty to refactor (i.e. rewrite in a more succinct way) the functions headIsEven and headIsPositive:

   Solution

   def headIsEven1(l: IntList): Boolean =
     headHasProperty(i => i % 2 == 0, l)
   def headIsPositive1(l: IntList): Boolean =
     headHasProperty(i => i > 0, l)
   

   higher-order-functions/src/main/scala/hofs/fun.scala

2. Now take a look at these three functions:

   def DoubleTriple(x: Int) =
     IntCons(x * 2, IntCons(x * 3, IntNil()))
   
   def DivideTrivide(x: Int) =
     IntCons(x / 2, IntCons(x / 3, IntNil()))
   
   def IncrementDeuxcrement(x: Int) =
     IntCons(x + 1, IntCons(x + 2, IntNil()))
   

   higher-order-functions/src/main/scala/hofs/fun.scala

   What parts do they have in common? What parts are different?

   Write a single function ConstructTwo that abstracts away the common parts of the three functions above, and rewrite all three functions to use it:

   def ConstructTwo(f: Int => Int, g: Int => Int): Int => IntList =
     ???
   
   val DoubleTriple2 = TODO
   val DivideTrivide2 = TODO
   val IncrementDeuxcrement2 = TODO
   

   higher-order-functions/src/main/scala/hofs/fun.scala

def ConstructTwo(f: Int => Int, g: Int => Int): Int => IntList =
  x => IntCons(f(x), IntCons(g(x), IntNil()))

val DoubleTriple2 = ConstructTwo(x => x * 2, x => x * 3)
val DivideTrivide2 = ConstructTwo(x => x / 2, x => x / 3)
val IncrementDeuxcrement2 = ConstructTwo(x => x + 1, x => x + 2)

Refactoring recursive functions

Your task is now to generalize this process of abstraction to the groups of functions that you have identified.

The general functions that you come up with will need additional parameters, just like in the refactoring exercise. They should be such that you can rewrite all the functions that fit into the categories as special cases of the general functions, by passing a few parameters.

Once you’re done with this exercise on paper, use the REPL, last week’s tests, or last week’s worksheet to confirm that your rewritten (“refactored”) functions work.

You can get the scaffold code by pulling from our course exercises repository with the following command:

cd ~/Documents/cs214/exercises # Replace with the exercises where you cloned the exercises
git pull

Note that it covers only the first part of the set (this part). For the second part (below), we have only provided you with a simple worksheet, with no tests, so that you can learn to test your functions directly yourself (either directly in the worksheet, or in the REPL).

def map(f: Int => Int)(l: IntList): IntList =
  if l.isEmpty then IntNil()
  else IntCons(f(l.head), map(f)(l.tail))

def filter(p: Int => Boolean)(l: IntList): IntList =
  if l.isEmpty then IntNil()
  else
    val keep = p(l.head)
    val tl = filter(p)(l.tail)
    if keep then IntCons(l.head, tl) else tl

def foldRight(f: (Int, Int) => Int, base: Int)(l: IntList): Int =
  if l.isEmpty then base
  else f(l.head, foldRight(f, base)(l.tail))

def foldRightList(f: (Int, IntList) => IntList, base: IntList)(l: IntList): IntList =
  if l.isEmpty then base
  else f(l.head, foldRightList(f, base)(l.tail))

def reduceRight(f: (Int, Int) => Int)(l: IntList): Int =
  if l.isEmpty then throw new IllegalArgumentException("Empty list!")
  else if l.tail.isEmpty then l.head
  else f(l.head, reduceRight(f)(l.tail))

def forall(p: Int => Boolean)(l: IntList): Boolean =
  if l.isEmpty then true
  else p(l.head) && forall(p)(l.tail)

def exists(p: Int => Boolean)(l: IntList): Boolean =
  if l.isEmpty then false
  else p(l.head) || exists(p)(l.tail)

val length = foldRight((_, acc) => 1 + acc, 0)

val allPositiveOrZero = forall(hd => hd >= 0)

val countPositive = foldRight(
  (hd, acc) => (if hd > 0 then 1 else 0) + acc,
  0
)

val sum = foldRight((hd, acc) => hd + acc, 0)

val product = foldRight((hd, acc) => hd * acc, 1)

val anyOdd = exists(hd => hd % 2 != 0)

val decrement = map(hd => hd - 1)

val collectEven = filter(hd => hd % 2 == 0)

val min = reduceRight(scala.math.min)

val increment = map(hd => hd + 1)

val subtract = reduceRight((hd, acc) => hd - acc)

val removeOdd = filter(hd => hd % 2 == 0)

val countEven = foldRight(
  (hd, acc) => (if hd % 2 == 0 then 1 else 0) + acc,
  0
)

val multiplyBy2 = map(hd => 2 * hd)

val anyNegative = exists(hd => hd < 0)

val allEven = forall(hd => hd % 2 == 0)

val multiplyOdd = foldRight(
  (hd, acc) => (if hd % 2 != 0 then hd else 1) * acc,
  1
)

def horner(x: Int, l: IntList) =
  foldRight((hd, acc) => hd + x * acc, 0)(l)

val capAtZero = map(hd => if hd > 0 then 0 else hd)

val removeZeroes = filter(hd => hd != 0)

def reverseAppend(l1: IntList, l2: IntList): IntList =
  if l1.isEmpty then l2
  else reverseAppend(l1.tail, IntCons(l1.head, l2))

val takeWhilePositive =
  foldRightList((hd, acc) => if hd > 0 then IntCons(hd, acc) else IntNil(), IntNil())

def append(l1: IntList, l2: IntList): IntList =
  foldRightList(IntCons.apply, l2)(l1)

def collectMultiples(d: Int, l: IntList): IntList =
  filter(hd => hd % d == 0)(l)

val last = reduceRight((hd, acc) => acc)

def init(l: IntList): IntList =
  if l.isEmpty then
    throw IllegalArgumentException("Empty list!")
  else if l.tail.isEmpty then IntNil()
  else IntCons(l.head, init(l.tail))

def contains(l: IntList, n: Int): Boolean =
  exists(hd => hd == n)(l)

def isSubset(l: IntList, L: IntList): Boolean =
  forall(hd => contains(L, hd))(l)

def intersection(l: IntList, L: IntList): IntList =
  filter(hd => contains(L, hd))(l)

def difference(l: IntList, L: IntList): IntList =
  filter(hd => !contains(L, hd))(l)

Part 4: Conclusion

The higher-order functions that we have discovered today are useful beyond Scala, and have names common across programming languages:

• “associative” (sum/product), once suitably generalized, is almost identical to “foldRight”, so it typically doesn’t have its own name.
• “map” (increment/multiply) and “filter” (collectEven/removeOdd) are special cases of foldRight. They are so useful that they are typically defined (and optimized) separately from foldRight, with their own name. They are present in the vast majority of modern programming languages (including JavaScript, Python, and Java).
• “foldRight” (countEven/multiplyOdd) and “reduceRight” (minMax/last) are similar to each other, but reduceRight uses the last element of the list as its starting point, and does not work for empty lists.

Variants of these functions are found in many fields: in data science with MapReduce; in databases with SELECT/WHERE (filter); in graphics with GPUs and SIMD programs; and in many other computational sciences, where they help process large data sets. There are other such higher-order functions that capture common patterns, which we will explore throughout the course.

The supporting code for this week’s lab includes definitions of all of these functions, should you want to use them. We found them useful in our own solution.

1. 🔜 map and filter are special cases of foldRight. Can you rewrite them using foldRight instead of direct recursion?

   def mapAsFoldRight(f: Int => Int): IntList => IntList =
     ???
   
   def filterAsFoldRight(p: Int => Boolean): IntList => IntList =
     ???
   

   higher-order-functions/src/main/scala/hofs/fun.scala

2. ⭐️ allEven and anyNegative can be implemented using foldRight, but is the result as efficient as the original function? Why or why not?

   Hint

   Try evaluating each implementation with the substitution model and counting evaluation steps.

3. Another way to implement allEven and anyNegative would be to define two functions:

   • one function, forall, to check whether a predicate (a function from Int to Boolean) holds (i.e., evaluates to true) for all values in a list, and
   • one function, exists, to check whether a predicate holds for any value in a list:

   def forall(p: Int => Boolean)(l: IntList): Boolean =
     if l.isEmpty then true
     else p(l.head) && forall(p)(l.tail)
   
   def exists(p: Int => Boolean)(l: IntList): Boolean =
     if l.isEmpty then false
     else p(l.head) || exists(p)(l.tail)
   

   higher-order-functions/src/main/scala/hofs/listOps.scala

   1. Rewrite allEven and anyNegative using forall/exists.

      def allEven(l: IntList): Boolean =
        if l.isEmpty then true
        else (l.head % 2 == 0) && allEven(l.tail)
      

      higher-order-functions/src/main/scala/hofs/listOps.scala

      def anyNegative(l: IntList): Boolean =
        if l.isEmpty then false
        else l.head < 0 || anyNegative(l.tail)
      

      higher-order-functions/src/main/scala/hofs/listOps.scala

   2. The two implementations provided above use if with a constant branch (if … then true else … and if … then false else …). Can you simplify them to eliminate the ifs?

      def forallNoIf(p: Int => Boolean)(l: IntList): Boolean =
        ???
      
      def existsNoIf(p: Int => Boolean)(l: IntList): Boolean =
        ???
      

      higher-order-functions/src/main/scala/hofs/fun.scala

def mapAsFoldRight(f: Int => Int): IntList => IntList =
  foldRightList((hd, tl) => IntCons(f(hd), tl), IntNil())

def filterAsFoldRight(p: Int => Boolean): IntList => IntList =
  foldRightList(
    (hd, tl) =>
      if p(hd) then IntCons(hd, tl) else tl,
    IntNil()
  )

val allEven = forall(hd => hd % 2 == 0)

val anyNegative = exists(hd => hd < 0)

def forallNoIf(p: Int => Boolean)(l: IntList): Boolean =
  l.isEmpty || (p(l.head) && forallNoIf(p)(l.tail))

def existsNoIf(p: Int => Boolean)(l: IntList): Boolean =
  !l.isEmpty && (p(l.head) || existsNoIf(p)(l.tail))

Part 5: Going further

The functions that we have seen today are applicable beyond lists; we will look at this in more depth next week, but you may be interested to get started right away:

• 🔜 Look over the tree functions of week 1. Do you see patterns and categories similar to the ones we saw for lists? Could you operate the same generalization by defining map, filter, and reduce on trees?

• 🔜 Look over the string functions of week 1. Are they different from the list functions? Is there anything preventing you to use your list functions on strings?

Functions as values

Operations on functions ⭐️

1. Think about the types that you already know in Scala: Boolean, Int, String, … (what else?): each of them has operations that you can use to combine them: * on Ints, || on Booleans, + on Strings, == on most types… (what else?)

   Which ones of these operations make sense for functions? Do they make sense of all functions, or just for some functions? What could it mean to “or” or “add” two functions together?

   Hint

   Consider concrete examples: if I have two functions isOdd and isGreaterThan5, how can I combine them? What operators can I apply to their results?

   How about two functions $f: x ↦ x + 1$ and $g: x ↦ x^2$? The answer should be a bit different from the Boolean case. Why? Consider the argument and return types.

   Hint

   Take time to think about what == may mean for functions. If we define equality as f(x) ≣ g(x) for all x, then could you write a program that checks whether two functions are equal? How long would that program run for?

2. Can you think of operations that make sense for functions, but not for the other types you know?

   Hint

   Think again about $f: x ↦ x + 1$ and $g: x ↦ x^2$. I can add or multiply their results, of course, but what else can I do with them?

   Then think about logical negation (not), isEven, and isOdd. Can I define one in terms of the other two?

Function combinations

Composition ⭐️

1. ⭐️ Write a function that takes two functions f and g, and returns a new function that applies them in sequence (f, then g). This is called composition and is usually written g ∘ f in mathematics. In Scala, it is typically written g `compose` f or f `andThen` g (both are built-in):

   def andThen(f: Int => Double, g: Double => String): Int => String =
     ???
   

   higher-order-functions/src/main/scala/hofs/fun.scala

2. Can you write variants of compose for other types of functions? Bool => Bool, or String => String, for example. Does the implementation look different?

3. More generally, assume that f has type A => B and g has type C => D. Under what conditions can you compose f and g to form g ∘ f? What about f ∘ g?

def andThen(f: Int => Double, g: Double => String): Int => String =
  (x: Int) => g(f(x))

Identity

0 is the neutral element for +: $0 + x = x + 0 = x$ for all $x$. 1 is the neutral element for *.

What is the neutral element for compose? That is, which function id is such that id ∘ f ≡ f ∘ id ≡ f for all f? (we use f ≡ g here to mean that f(x) == g(x) for all x.

val id: Int => Int =
  TODO

val id: Int => Int =
  x => x

Flip

1. Define a function flip. It takes a function and returns the same function, but with the arguments flipped.

   def flip(f: (Int, Int) => Int): (Int, Int) => Int =
     ???
   

   higher-order-functions/src/main/scala/hofs/fun.scala

2. What happens if you compose flip with itself (in other words, what does flip ∘ flip do?)

def flip(f: (Int, Int) => Int): (Int, Int) => Int =
  (x, y) => f(y, x)

Modularizing with compositions ⭐

Higher-order functions are often very useful to capture repeated patterns. For example, here are some closely related functions:

val squareMinusOne     = (x: Int) => (x - 1) * (x - 1)
val squarePlusOne      = (x: Int) => (x + 1) * (x + 1)
val squareSquare       = (x: Int) => (x * x) * (x * x)
val squareMinusTwo     = (x: Int) => (x - 2) * (x - 2)
val squareSquareSquare = (x: Int) =>
  ((x * x) * (x * x)) * ((x * x) * (x * x))

Can you define these functions in terms of the following ones?

val square = (x: Int) => x * x
val plusOne = (x: Int) => x + 1
val minusOne = (x: Int) => x - 1
def composeInt(f: Int => Int, g: Int => Int): Int => Int =
  x => f(g(x))

val squareMinusOne = composeInt(square, minusOne)
val squarePlusOne = composeInt(square, plusOne)
val squareSquare = composeInt(square, square)
val squareMinusTwo = composeInt(square, composeInt(minusOne, minusOne))
val squareSquareSquare = composeInt(square, composeInt(square, square))

Lifting

1. Write a function that takes two functions Int => Int and returns a new function Int => Int whose results are the sum of the results of the first two functions.

   def adder(f: Int => Double, g: Int => Double): Int => Double =
     ???
   

   higher-order-functions/src/main/scala/hofs/fun.scala

   Hint

   The result should be such that adder(f, g)(x) == f(x) + g(x).

   This is called a lifted version of +. In mathematics, this is the usual definition of + on functions.

2. Can you do the same for *, -, /, other operators? Do you notice any similarities?

   def multiplier(f: Int => Double, g: Int => Double): Int => Double =
     ???
   

   higher-order-functions/src/main/scala/hofs/fun.scala

3. We saw previously that 0 is the neutral element of +. What is the neutral element of adder? In other words, what function is such adder(f, g) ≡ f?

def adder(f: Int => Double, g: Int => Double): Int => Double =
  x => f(x) + g(x)

def multiplier(f: Int => Double, g: Int => Double): Int => Double =
  x => f(x) * g(x)

Heavy lifting

Let’s extract the common code between the functions in the previous exercise.

1. Write a function that takes a single function op (a binary operator such as +) and returns a lifted version of that operation (like adder above).

   def lifter(op: (Double, Double) => Double): (Int => Double, Int => Double) => (Int => Double) =
     ???
   

   higher-order-functions/src/main/scala/hofs/fun.scala

   lifter((x, y) => x + y) should be the same as adder. Look for the common parts in the implementation, and extract the ones that vary between them.

2. Rewrite adder and other related functions in terms of this one.

   val adder2 = TODO
   val multiplier2 = TODO
   

   higher-order-functions/src/main/scala/hofs/fun.scala

def lifter(op: (Double, Double) => Double): (Int => Double, Int => Double) => (Int => Double) =
  (f, g) => (x => op(f(x), g(x)))

val adder2 = lifter((x, y) => x + y)
val multiplier2 = lifter((x, y) => x * y)

Multi-lifting

1. Write a lifted version of the boolean && (and) operator.

   def meet(f: Int => Boolean, g: Int => Boolean): (Int => Boolean) =
     ???
   

   higher-order-functions/src/main/scala/hofs/fun.scala

   Hint

   This function should be such that meet(f, g)(x) == f(x) && g(x).

   Functions that return booleans are often called “predicates” (in other words, f: Int => Boolean is a predicate, and meet above combines two predicates into one).

2. 🔜 Generalize meet to accept more than one predicate. That is, write a function Meet which, given a list of predicates, returns a single predicate that lifts && across all of the predicates.

   def Meet(l: IntPredicateList): (Int => Boolean) =
     ???
   

   higher-order-functions/src/main/scala/hofs/fun.scala

def meet(f: Int => Boolean, g: Int => Boolean): (Int => Boolean) =
  x => f(x) && g(x)

def Meet(l: IntPredicateList): (Int => Boolean) =
  if l.isEmpty then x => true
  else meet(l.head, Meet(l.tail))

Values as functions: defs, vals and currying

The idea of currying is to change (slightly) the way a function is invoked (called) to make it easier to use. Let us explore this on two examples:

Translating between defs and vals (named and anonymous functions) ⭐️

Using the template below, rewrite (and show how to call) each of the following functions:

def isGreaterThanBasic(x: Int, y: Int): Boolean =
  x > y
val isGreaterThanAnon: (Int, Int) => Boolean =
  (x, y) => x > y
val isGreaterThanCurried: Int => Int => Boolean =
  x => y => x > y // Same as `x => (y => x > y)`
def isGreaterThanCurriedDef(x: Int)(y: Int): Boolean =
  x > y

// How to call:
//   For all x, y:
//     isGreaterThan(x, y)
//       == isGreaterThanAnon(x, y)
//       == isGreaterThanCurried(x)(y)
//       == isGreaterThanCurriedDef(x)(y)

1. incrHeadByX

   def incrHeadByXBasic(x: Int, l: IntList): IntList =
     if l.isEmpty then l
     else IntCons(l.head + x, l.tail)
   
   val incrHeadByXAnon: (Int, IntList) => IntList =
     TODO
   
   val incrHeadByXCurried: Int => IntList => IntList =
     TODO
   
   def incrHeadByXCurriedDef(x: Int)(l: IntList): IntList =
     ???
   

   higher-order-functions/src/main/scala/hofs/fun.scala

2. addToFront

   def addToFrontBasic(x: Int, y: Int, l: IntList): IntList =
     IntCons(x, IntCons(y, l))
   
   val addToFrontAnon: (Int, Int, IntList) => IntList =
     TODO
   
   val addToFrontPartlyCurried: (Int, Int) => IntList => IntList =
     TODO
   
   val addToFrontCurried: Int => Int => IntList => IntList =
     TODO
   
   def addToFrontCurriedDef(x: Int)(y: Int)(l: IntList): IntList =
     ???
   

   higher-order-functions/src/main/scala/hofs/fun.scala

3. contains

   def containsBasic(l: IntList, n: Int): Boolean =
     !l.isEmpty && (n == l.head || contains(l.tail, n))
   
   def containsAnon: (IntList, Int) => Boolean =
     TODO
   
   def containsCurried: IntList => Int => Boolean =
     TODO
   
   def containsCurriedDef(l: IntList)(n: Int): Boolean =
     ???
   

   higher-order-functions/src/main/scala/hofs/fun.scala

   It is debatable whether containsAnon is really anonymous, since it must use its own name (the one being defined in the def) for the recursive call. This recursion issue is also why we use def instead of val here.

4. headHasProperty (from “Part 3”, above)

   def headHasPropertyBasic(p: Int => Boolean, l: IntList): Boolean =
     !l.isEmpty && p(l.head)
   
   val headHasPropertyAnon: ((Int => Boolean), IntList) => Boolean =
     TODO
   
   val headHasPropertyCurried: (Int => Boolean) => IntList => Boolean =
     TODO
   
   def headHasPropertyCurriedDef(p: Int => Boolean)(l: IntList): Boolean =
     ???
   

   higher-order-functions/src/main/scala/hofs/fun.scala

Finally, using this new headHasPropertyCurried, rewrite headIsEven and headIsPositive. Which version is shorter?

def headIsEven(l: IntList): Boolean =
  !l.isEmpty && l.head % 2 == 0
def headIsPositive(l: IntList): Boolean =
  !l.isEmpty && l.head > 0

val headIsEven2 =
  TODO
val headIsPositive2 =
  TODO

def incrHeadByXBasic(x: Int, l: IntList): IntList =
  if l.isEmpty then l
  else IntCons(l.head + x, l.tail)

val incrHeadByXAnon: (Int, IntList) => IntList =
  (x, l) =>
    if l.isEmpty then l
    else IntCons(l.head + x, l.tail)

val incrHeadByXCurried: Int => IntList => IntList =
  x =>
    l =>
      if l.isEmpty then l
      else IntCons(l.head + x, l.tail)

def incrHeadByXCurriedDef(x: Int)(l: IntList): IntList =
  if l.isEmpty then l
  else IntCons(l.head + x, l.tail)

def addToFrontBasic(x: Int, y: Int, l: IntList): IntList =
  IntCons(x, IntCons(y, l))

val addToFrontAnon: (Int, Int, IntList) => IntList =
  (x, y, l) => IntCons(x, IntCons(y, l))

val addToFrontPartlyCurried: (Int, Int) => IntList => IntList =
  (x, y) => l => IntCons(x, IntCons(y, l))

val addToFrontCurried: Int => Int => IntList => IntList =
  x => y => l => IntCons(x, IntCons(y, l))

def addToFrontCurriedDef(x: Int)(y: Int)(l: IntList): IntList =
  IntCons(x, IntCons(y, l))

def containsBasic(l: IntList, n: Int): Boolean =
  !l.isEmpty && (n == l.head || contains(l.tail, n))

def containsAnon: (IntList, Int) => Boolean =
  (l, n) =>
    !l.isEmpty && (n == l.head || containsAnon(l.tail, n))

def containsCurried: IntList => Int => Boolean =
  l =>
    n =>
      !l.isEmpty && (n == l.head || containsCurried(l.tail)(n))

def containsCurriedDef(l: IntList)(n: Int): Boolean =
  !l.isEmpty && (n == l.head || containsCurried(l.tail)(n))

def headHasPropertyBasic(p: Int => Boolean, l: IntList): Boolean =
  !l.isEmpty && p(l.head)

val headHasPropertyAnon: ((Int => Boolean), IntList) => Boolean =
  (p, l) => !l.isEmpty && p(l.head)

val headHasPropertyCurried: (Int => Boolean) => IntList => Boolean =
  p => l => !l.isEmpty && p(l.head)

def headHasPropertyCurriedDef(p: Int => Boolean)(l: IntList): Boolean =
  !l.isEmpty && p(l.head)

val headIsEven2 =
  headHasPropertyCurried(i => i % 2 == 0)
val headIsPositive2 =
  headHasPropertyCurried(i => i > 0)

val headHasPropertyCurried0: (Int => Boolean) => IntList => Boolean =
  (p: Int => Boolean) => (l: IntList) => !l.isEmpty && p(l.head)

def headHasPropertyCurried1(p: Int => Boolean): IntList => Boolean =
  (l: IntList) => !l.isEmpty && p(l.head)

def headHasPropertyCurried2(p: Int => Boolean)(l: IntList): Boolean =
  !l.isEmpty && p(l.head)

Currying container functions ⭐️

Now let’s see how these different styles can help:

Let’s assume we have a list of EPFL Sciper numbers registered for this course (students and staff), and a separate list of EPFL Scipers for just the staff. Thus, registered students are those who occur in the first list but not the second one:

val cs214All =
  IntCons(123456, IntCons(654321, IntCons(111222, IntCons(333444, IntCons(555666, IntCons(787878, IntNil()))))))

val cs214Staff =
  IntCons(654321, IntCons(333444, IntNil()))

1. Write a function isRegisteredForCS214 that checks whether a given Sciper appears in the cs214All list. Write two versions: one using containsBasic, as a def; and one using containsCurried, as a val. For the val, do not create an anonymous function: the definition should have no mention of a sciper variable.

   def isRegisteredForCS214Def(sciper: Int): Boolean =
     ???
   
   val isRegisteredForCS214Val =
     TODO
   

   higher-order-functions/src/main/scala/hofs/fun.scala

2. Write a function isCS214Student that checks whether a Sciper corresponds to a registered student (i.e. not a staff member). Write two versions: one using containsBasic, as a def; and one using containsCurried, notLifter, and andLifter, as a val. For the val, as before, do not create an anonymous function: the definition should have no mention of a sciper variable.

   def isCS214StudentDef(sciper: Int): Boolean =
     ???
   

   higher-order-functions/src/main/scala/hofs/fun.scala

   def andLifter(f: Int => Boolean, g: Int => Boolean): Int => Boolean =
     n => f(n) && g(n)
   
   def notLifter(f: Int => Boolean): Int => Boolean =
     n => !f(n)
   
   val isCS214StudentVal =
     TODO
   

   higher-order-functions/src/main/scala/hofs/fun.scala

   The val style is often called “point-free style”, which means using only function combinators like andLifter and notLifter instead of explicit parameter names.

3. Notice that the two versions of the function above will always scan both lists. Using the difference function on lists, write a more general, curried function that takes two lists, computes the difference, and then returns a function that takes a sciper and validates it against the resulting list. Make sure that the list difference is computed once. Can you do it in point-free style, with no anonymous functions?

   def isCourseStudentDefPartlyCurried(all: IntList, staff: IntList): Int => Boolean =
     ???
   

   higher-order-functions/src/main/scala/hofs/fun.scala

def isRegisteredForCS214Def(sciper: Int): Boolean =
  containsBasic(cs214All, sciper)

val isRegisteredForCS214Val =
  containsCurried(cs214All)

def isCS214StudentDef(sciper: Int): Boolean =
  containsBasic(cs214All, sciper)
    && !containsBasic(cs214Staff, sciper)

def andLifter(f: Int => Boolean, g: Int => Boolean): Int => Boolean =
  n => f(n) && g(n)

def notLifter(f: Int => Boolean): Int => Boolean =
  n => !f(n)

val isCS214StudentVal =
  andLifter(
    containsCurried(cs214All),
    notLifter(containsCurried(cs214Staff))
  )

def isCourseStudentDefPartlyCurried(all: IntList, staff: IntList): Int => Boolean =
  val students = difference(all, staff)
  containsCurried(students)

Equality 🔥

Mathematicians generally say that two functions are “equal” when they have the same outputs for all inputs.

1. By this definition, which of the following functions are equal?

   val f0 = (x: Long) => x
   val f1 = (x: Long) => if x > 0 then x else -x
   val f2 = (x: Long) => x + 1 - 1
   val f3 = (x: Long) =>
     Math.sqrt(x.toDouble * x.toDouble).round
   val f4: Long => Long = x =>
     if x < 0 then f4(x + 1) - 1
     else if x > 0 then f4(x - 1) + 1
     else 0
   

   higher-order-functions/src/main/scala/hofs/fun.scala

2. Can you define a function that checks whether two functions of type Boolean => Boolean are equal?

   def eqBoolBool(
       f: Boolean => Boolean,
       g: Boolean => Boolean
   ) =
     ???
   

   higher-order-functions/src/main/scala/hofs/fun.scala

   What about functions of the following types?

   • Int => Boolean
   • Boolean => Int
   • IntList => Boolean
   • Boolean => IntList
   • Int => Boolean => IntList

3. Can you come up with a general result? For which types A and B can one write a function eqAB that checks whether two functions of type A => B return the same outputs for all inputs?

4. What do you think of this definition of equality? Is f4 really “the same” as f0, or do they differ in any way?

Fixed points

1. A value x is a fixed point of f if f(x) == x. Do the following functions have fixed points? If so, which one(s)?

   val a = (x: Int) => x
   val b = (x: Int) => -x
   val c = (x: Int) => x + 1
   val d = (x: Int) => (x / 2) + 5
   val e = (x: Int) => if x % 10 == 0 then x else (x + 1)
   val f = (x: Int) => -(x * x)
   val g = (x: Int) => /* 🔥 */ /* assuming x > 0 */
     if x == 1 then 1
     else if x % 2 == 0 then x / 2
     else 3 * x + 1
   

   higher-order-functions/src/main/scala/hofs/fun.scala

2. Write a function fixedPoint that takes a function f and an integer x, checks whether x is already a fixpoint of f, and then looks for a fixed point by repeatedly calling f, until it converges.

   def fixedPoint(f: Int => Int, start: Int): Int =
     ???
   

   higher-order-functions/src/main/scala/hofs/fun.scala

   For example, fixedPoint(((x: Int) => x / 2 + 5), 20) will call itself recursively with x = 15 (20 / 2 + 5), then x = 12 (15 / 2 + 5), then x = 11 (12 / 2 + 5), then x = 10 (11 / 2 + 5).

3. For each of the following expressions, indicate whether it terminates, and if so, what value is returned:

   1. fixedPoint(((x: Int) => x / 2), 4)
   2. fixedPoint(((x: Int) => -x), 3)
   3. fixedPoint(((x: Int) => x), 123456)
   4. fixedPoint(((x: Int) => x + 1), 0)
   5. fixedPoint(((x: Int) => if (x % 10 == 0) then x else x + 1), 35)
   6. fixedPoint(((x: Int) => x / 2 + 5), 20)

   What happens when there is no fixed point? Does fixedPoint work for all functions above that have a fixed point? Does it depend on the starting value of x?

4. 🔥 Finally, a question that is not directly relevant to the class but interesting to think about. For which functions and which inputs does fixedPoint work?

@tailrec
def fixedPoint(f: Int => Int, start: Int): Int =
  val next = f(start)
  if next == start then start else fixedPoint(f, next)

Debugging

The best way to improve your debugging skills is to apply the debugging guide to your own code in the labs. For more focused training, however, we provide a few exercises below. Happy hacking!

Time for some recursion debugging

The following program is intended to compute and output $x^n$ by using the square-and-multiply method, but a bug has sneaked in. Can you find it, explain what went wrong, and fix it?

def squareAndMultiply(x: Double, n: Int): Double =
  if n < 0 then
    squareAndMultiply(1 / x, -n)
  else if x == 1 then
    1
  else if n == 0 then
    0
  else if n % 2 == 0 then
    squareAndMultiply(x * x, n / 2)
  else
    x * squareAndMultiply(x, n - 1)

// 1. Start evaluating the expression
squareAndMultiply(2,0)
// 2. Take the right if-branch, where n == 0
0
// We're done

def squareAndMultiply(x: Double, n: Int): Double =
  if n < 0 then
    squareAndMultiply(1 / x, -n)
  else if x == 1 then
    1
  else if n == 0 then
    1
  else if n % 2 == 0 then
    squareAndMultiply(x * x, n / 2)
  else
    x * squareAndMultiply(x, n - 1)

Encoding issues ⭐️

Prof. Pit-Claudel recently received a spam email with the following title:

Re: Design Query for √âcole polytechnique f√(c)d√(c)rale de ...

Explain what happened.

Re: Design Query for École polytechnique fédérale de Lausanne

import java.nio.charset.Charset
import scala.jdk.CollectionConverters.*

def findPairs(src: String, dst: String): Iterable[(Charset, Charset)] =
  Charset.availableCharsets()
    .values().asScala
    .filter(enc => enc.canEncode())
    .flatMap(enc =>
      Charset.availableCharsets()
        .values().asScala
        .filter(dec => dec.decode(enc.encode(src)).toString() == dst)
        .map(dec => (enc, dec))
    )

findPairs("É", "√â").foreach(println)
// (CESU-8,x-MacCroatian)
// (CESU-8,x-MacIceland)
// (CESU-8,x-MacRoman)
// (CESU-8,x-MacRomania)
// (CESU-8,x-MacTurkish)
// (UTF-8,x-MacCroatian)
// (UTF-8,x-MacIceland)
// (UTF-8,x-MacRoman)
// (UTF-8,x-MacRomania)
// (UTF-8,x-MacTurkish)

findPairs("É", "√â").foreach((enc, dec) =>
  println(f"$enc, $dec: é → ${dec.decode(enc.encode("é"))}")
)
// CESU-8, x-MacCroatian: é → √Š
// CESU-8, x-MacIceland: é → √©
// CESU-8, x-MacRoman: é → √©
// CESU-8, x-MacRomania: é → √©
// CESU-8, x-MacTurkish: é → √©
// UTF-8, x-MacCroatian: é → √Š
// UTF-8, x-MacIceland: é → √©
// UTF-8, x-MacRoman: é → √©
// UTF-8, x-MacRomania: é → √©
// UTF-8, x-MacTurkish: é → √©

def findPairsSuccint(src: String, dst: String): Iterable[(Charset, Charset)] =
  for
    enc <- Charset.availableCharsets().values.asScala
    if enc.canEncode()
    dec <- Charset.availableCharsets().values.asScala
    if dec.decode(enc.encode(src)).toString() == dst
  yield (enc, dec)

Debugging warnings

When Prof. Pit-Claudel demoed sbt new in class, the following appeared on screen:

SLF4J: Failed to load class "org.slf4j.impl.StaticLoggerBinder".
SLF4J: Defaulting to no-operation (NOP) logger implementation
SLF4J: See http://www.slf4j.org/codes.html#StaticLoggerBinder for further details.

What happened?

Debugging with the substitution model ⭐️

Lists

removeDuplicates

1. removeDuplicates takes a list and produces a new list with all duplicated elements removed, keeping only the first one. For simplicity, we use 1 :: 2 :: 3 :: IntNil to denote IntCons(1, IntCons(2, IntCons(3, IntNil))). For example, for a list 1 :: 2 :: 4 :: 2 :: 3 :: 3 :: IntNil, the second 2 and 3 are duplicated elements, so the returned list should be 1 :: 2 :: 4 :: 3 :: IntNil.

   The following is an (incorrect) implementation of removeDuplicates, using a function contains(l, x) that checks whether list l contains value x:

   def removeDuplicates(l: IntList): IntList =
     l match
       case IntNil() => IntNil()
       case IntCons(hd, tl) =>
         if contains(tl, hd) then removeDuplicates(tl)
         else IntCons(hd, removeDuplicates(tl))
   

   debugging/src/main/scala/debugging/ListOps.scala

   1. What is the expected return value of this program for the input 1 :: 2 :: 1 :: IntNil?

   2. Write down, step by step, the evaluation of removeDuplicates(IntCons(1, IntCons(2, IntCons(1, IntNil())))), using the substitution model. You may assume that contains correctly computes its result and substitute calls to it in a single step.

      (Consider using an erasable surface, such as a whiteboard, tablet, or writing slate, to reduce repetition).

      Where does the computation diverge from the expected result?

   3. Fix the implementation.

Binary search trees

isBST

A Binary Search Tree (BST) is a binary tree such that the value carried by each node is greater than all values in the left subtree and smaller than all values in the right subtree. For example, the following is a binary search tree:

       8
      / \
     3   10
    / \   \
   1   6   14

1. Can a binary search tree contain duplicate values?

2. Is the following tree a BST?

   val t0 =
     IntBranch(5,
       IntBranch(2, IntEmptyTree(), IntEmptyTree()),
       IntBranch(10,
         IntBranch(4, IntEmptyTree(), IntEmptyTree()),
         IntEmptyTree())))
   

3. The function isBST takes a binary tree and returns true if the tree is a binary search tree, false otherwise. Here is one candidate implementation of it:

   def isBST(t: IntTree): Boolean =
     t match
       case IntEmptyTree() => true
       case IntBranch(v, l, r) =>
            (l == IntEmptyTree() || v > l.value)
         && (r == IntEmptyTree() || v < r.value)
         && isBST(l)
         && isBST(r)
   

   debugging/src/main/scala/debugging/TreeOps.scala

   1. There is something wrong with this implementation. But what? Using the substitution method, show what isBST(t0) evaluates to (t0 refers to the tree above):

      For succinctness, we recommend writing IntEmptyTree as ε, IntBranch(v, l, r) as [v, l, r], and IntBranch(v, IntEmptyTree, IntEmptyTree) as [v], so that this input is written as follows:

      isBST([5 [2] [10 [4] ε]])
      

4. Fix the implementation.

insert

Binary search trees are convenient to represent sets of values. To use them in this way, we need a contains function and an insert function.

Let’s focus on the insert function. insert takes a binary search tree representing a set of values $V$ and a new value $v_1$, and returns a new binary search tree representing the set $V \cup {v_1}$.

The following is an attempt at implementing insert:

def insert(t: IntTree, v1: Int): IntTree =
  t match
    case IntEmptyTree() => IntBranch(v1, IntEmptyTree(), IntEmptyTree())
    case IntBranch(v0, l, r) =>
      if v1 < v0 then IntBranch(v0, insert(l, v1), r)
      else IntBranch(v0, l, insert(r, v1))

1. Find a counterexample: a binary search tree t and an input v1 such that insert(t, v1) produces an incorrect result.

2. Fix the implementation.

def insert(t: IntTree, v1: Int): IntTree =
  t match
    case IntEmptyTree() => IntBranch(v1, IntEmptyTree(), IntEmptyTree())
    case IntBranch(v0, l, r) =>
      if v0 > v1 then IntBranch(v0, insert(l, v1), r)
      else if v0 < v1 then IntBranch(v0, l, insert(r, v1))
      else t

© 2023–2025 EPFL. All rights reserved.