Last updated on Thursday, September 18, 2025

Week 1: Structural Recursion and Version Control

Welcome to the first exercise session of CS-214, Software Construction!

This exercise set will help you practice writing Scala code, get used to some functional programming style, use recursion, and get familiar with version control concepts and with Git.

Exercise sessions are meant to be done together in groups, on whiteboards, on blackboards, or on paper. Read more in the course policies. The second part of this exercise set is one of the few exceptions to the rule, as Git exercises are better done in a terminal… but you are still encouraged to do them in groups!

Exercises marked with ⭐️ are the most important ones. Exercises marked with 🔥 are the most challenging ones. Exercises or questions marked 🧪 are intended to build up to concepts used in this week’s lab.

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.

Structural Recursion

For each exercise below, we provide the signature of the functions you need to write. The body is replaced with ???: that’s the part you need to come up with! We strongly recommend that you solve these exercises on paper first.

Recursion on lists

In this exercise, you will write recursive functions that operate on lists. These lists are represented as instances of the IntList class. An IntList can be either:

• IntNil(), which represents an empty list,
• IntCons(head, tail), which represents a non-empty list starting with head (an integer) and continuing with tail (a list of integers).

Hence, the list 1, 2 is represented by IntCons(1, IntCons(2, IntNil())).

IntList objects have three operations — .head, .tail, and .isEmpty — demonstrated in the following REPL session:

scala> import recursion.*

scala> IntCons(2, IntNil()).head
val res0: Int = 2

scala> IntCons(2, IntNil()).tail
val res1: recursion.IntList = IntNil()

scala> val oneTwo = IntCons(1, IntCons(2, IntNil()))
val oneTwo: recursion.IntCons = IntCons(1,IntCons(2,IntNil()))

scala> oneTwo.isEmpty
val res2: Boolean = false

scala> oneTwo.head
val res3: Int = 1

scala> oneTwo.tail
val res4: recursion.IntList = IntCons(2,IntNil())

scala> oneTwo.tail.isEmpty
val res5: Boolean = false

scala> oneTwo.tail.head
val res6: Int = 2

scala> oneTwo.tail.tail
val res7: recursion.IntList = IntNil()

scala> oneTwo.tail.tail.isEmpty
val res8: Boolean = true

These three operations are all that you need (in addition to recursion) to solve all of the exercises below.

length ⭐️

Implement a function that computes the length of an IntList:

def length(l: IntList): Int =
  ???

allPositiveOrZero ⭐️

Implement a function that determines if all values in an IntList are positive or zero:

def allPositiveOrZero(l: IntList): Boolean =
  ???

What should this function return for an empty list? Why?

countPositive

Implement a function that counts the number of positive values in an IntList:

def countPositive(l: IntList): Int =
  ???

sum

Implement a function that computes the sum of all elements in an IntList:

def sum(l: IntList): Int =
  ???

product

Implement a function that computes the product of all elements in an IntList:

def product(l: IntList): Int =
  ???

anyOdd

Implement a function that determines if any value in an IntList is odd:

def anyOdd(l: IntList): Boolean =
  ???

What should this function return for an empty list? Why?

decrement

Implement a function that creates a new list whose values correspond to the ones in the original list, decremented by one:

def decrement(l: IntList): IntList =
  ???

collectEven ⭐️

Write a function that collects all even values from an IntList:

def collectEven(l: IntList): IntList =
  ???

min

Write a function min that retrieves the minimum of a list. If min is called on an empty list, it should throw an IllegalArgumentException using throw IllegalArgumentException("Empty list!").

def min(l: IntList): Int =
  ???

increment ⭐️

Implement a function that creates a new list whose values correspond to the ones in the original list incremented by one:

def increment(l: IntList): IntList =
  ???

subtract

Implement a function that performs right-associative subtraction. That is, 1, 2, 3, 4, 5 should become 1 - (2 - (3 - (4 - 5))) = 3.

If subtract is called on an empty list, it should throw an IllegalArgumentException using throw IllegalArgumentException("Empty list!"):

def subtract(l: IntList): Int =
  ???

removeOdd ⭐️

Write a function that creates a new list with all odd values removed:

def removeOdd(l: IntList): IntList =
  ???

Can you find an algebraic relationship between collectEven and removeOdd?

countEven

Implement a function that counts the number of even values in an IntList:

def countEven(l: IntList): Int =
  ???

Could you write countEven using collectEven and length?

multiplyBy2

Implement a function that creates a new list whose values correspond to the ones in the original list multiplied by two:

def multiplyBy2(l: IntList): IntList =
  ???

anyNegative

Implement a function that determines if any value in an IntList is negative:

def anyNegative(l: IntList): Boolean =
  ???

allEven

Implement a function that determines if all values in an IntList are even:

def allEven(l: IntList): Boolean =
  ???

multiplyOdd

Implement a function that computes the product of all odd numbers in an IntList:

def multiplyOdd(l: IntList): Int =
  ???

horner ⭐️

Given a polynomial:

$$a_0 + a_1x + a_2x^2 + a_3x^3 + \cdots + a_nx^n$$

We represent it as a list of coefficients $[a_0, a_1, a_2, \cdots, a_n]$.

Using the Horner’s rule:

$$a_0 + x \bigg(a_1 + x \Big(a_2 + x \big(a_3 + \cdots + x(a_{n-1} + x \, a_n) \cdots \big) \Big) \bigg)$$

Write a function that evaluates a polynomial given its list of coefficients and a value for $x$:

def horner(x: Int, l: IntList): Int =
  ???

capAt0

Implement a function that creates a copy of a list with all numbers greater than 0 replaced with zeroes.

def capAtZero(l: IntList): IntList =
  ???

removeZeroes

Implement a function that creates a copy of a list with all zeroes removed.

def removeZeroes(l: IntList): IntList =
  ???

reverseAppend

Implement a function that appends the reversed version of an IntList to another. For example, calling reverseAppend with the lists 1, 2, 3 and 7, 8, 9 should produce 3, 2, 1, 7, 8, 9:

def reverseAppend(l1: IntList, l2: IntList): IntList =
  ???

reverse ⭐️

Implement a function that reverses an IntList:

def reverse(l: IntList): IntList =
  ???

takeWhilePositive

Implement a function that creates a new list containing the same elements as its input list, except that it discards every number starting from the first nonpositive number (either 0 or negative). That is, 1, 2, -3, 4 should produce just 1, 2.

def takeWhilePositive(l: IntList): IntList =
  ???

append

Implement a function that concatenates two lists:

def append(l1: IntList, l2: IntList): IntList =
  ???

Bonus: Can you write it using just reverse and reverseAppend?

collectMultiples

Write a function that collects all the multiples of an integer d in a list l:

def collectMultiples(d: Int, l: IntList): IntList =
  ???

last

Implement a function that retrieves the last element from an IntList.

If last is called on an empty list, it should throw an IllegalArgumentException using throw IllegalArgumentException("Empty list!").

def last(l: IntList): Int =
  ???

init

Implement a function that creates a copy of an IntList with the last element removed (this function is sometimes called butlast).

If init is called on an empty list, it should throw an IllegalArgumentException using throw IllegalArgumentException("Empty list!").

def init(l: IntList): IntList =
  ???

minMax ⭐️

The goal of this exercise is to write a function that retrieves the smallest and largest elements from an IntList as a pair.

Because your functions must return 2 values, you will need to return a pair. A pair containing the integers 1 and 2 is written as (1, 2). Similarly, the type of a pair containing two integers is written as (Int, Int). Here is a REPL session demonstrating how to create and use pairs:

scala> val pair = (1, 2)
val pair: (Int, Int) = (1,2)

scala> pair._1
val res9: Int = 1

scala> pair._2
val res10: Int = 2

scala> val (first, second) = pair
val first: Int = 1
val second: Int = 2

To find the smallest or largest of two integers, you can use the scala.math.min and scala.math.max functions.

If minMax is called on an empty list, it should throw an IllegalArgumentException using throw IllegalArgumentException("Empty list!").

def minMax(l: IntList): (Int, Int) =
  ???

Lists as sets

Lists are ordered collections of objects; as a result, most set operations can be defined on them too:

contains ⭐️

Write a contains(l, n) function that checks whether list l contains value n:

def contains(l: IntList, n: Int): Boolean =
  ???

isSubset

Write an isSubset(l, L) function that checks whether list l is a subset of list L (that is, all elements of l are also contained in L):

def isSubset(l: IntList, L: IntList): Boolean =
  ???

intersection

Write an intersection(l, L) function that constructs a new list whose elements are the same as those of l in the same order, but with all elements not contained in L removed:

def intersection(l: IntList, L: IntList): IntList =
  ???

difference ⭐️

Write a difference(l, L) function that constructs a new list whose elements are the same as those of l in the same order, but with all elements contained in L removed:

def difference(l: IntList, L: IntList): IntList =
  ???

Recursion on trees

Now, we’ll explore recursion on binary trees. A binary tree is a tree where each node has at most two children. An IntTree can be either:

• IntEmptyTree(), which represents an empty tree,
• IntBranch(value, left, right): which represents a node with value value (an integer) and two children left and right (trees of integers).

Hence, a tree with two non-empty nodes, a root node with value 1 with a left child with value 2, is represented by IntBranch(1, IntBranch(2, IntEmptyTree(), IntEmptyTree()), IntEmptyTree()).

IntTree objects have four operations — .value, .left, .right and .isEmpty — demonstrated in the following REPL session:

scala> import recursion.*

scala> IntBranch(2, IntEmptyTree(), IntEmptyTree()).value
val res11: Int = 2

scala> IntBranch(2, IntEmptyTree(), IntEmptyTree()).left
val res12: recursion.IntTree = IntEmptyTree()

scala> IntBranch(2, IntEmptyTree(), IntEmptyTree()).right
val res13: recursion.IntTree = IntEmptyTree()

scala> val tree = IntBranch(1, IntBranch(2, IntEmptyTree(), IntEmptyTree()), IntEmptyTree())
val tree: recursion.IntBranch = IntBranch(1,IntBranch(2,IntEmptyTree(),IntEmptyTree()),IntEmptyTree())

scala> tree.isEmpty
val res14: Boolean = false

scala> tree.value
val res15: Int = 1

scala> tree.left
val res16: recursion.IntTree = IntBranch(2,IntEmptyTree(),IntEmptyTree())

scala> tree.left.isEmpty
val res17: Boolean = false

scala> tree.left.value
val res18: Int = 2

scala> tree.left.left
val res19: recursion.IntTree = IntEmptyTree()

scala> tree.left.right
val res20: recursion.IntTree = IntEmptyTree()

scala> tree.right
val res21: recursion.IntTree = IntEmptyTree()

scala> tree.right.isEmpty
val res22: Boolean = true

treeSize

Implement a function that computes the size of an IntTree. The size of a tree is the number of nodes it contains.

def treeSize(t: IntTree): Int =
  ???

treeDepth ⭐️

Implement a function that computes the depth of an IntTree. The depth of a tree is the number of edges on the longest path between the root and a leaf. Our example tree above has a depth of 2.

To find the largest of two integers, you can use the scala.math.max function.

def treeDepth(t: IntTree): Int =
  ???

treeSum 🧪

Implement a function that computes the sum of all values in an IntTree, similarly to the sum function for IntLists:

def treeSum(t: IntTree): Int =
  ???

treeAllEven

Implement a function that determines if all values in an IntTree are even:

def treeAllEven(t: IntTree): Boolean =
  ???

treeIncrement ⭐️

Implement a function that increases each value in an IntTree by one:

def treeIncrement(t: IntTree): IntTree =
  ???

treeShow 🧪

Implement a function that creates a string containing all values in an IntTree, in pre-order. This means that the value of each node must be printed before its children, and then the values of the left subtree must be printed before the values of the right subtree.

For our example tree, the output should be:

1
2

Your function must return a String.

To concatenate two strings, you can use the + operator:

scala> "Hello " + "Ada"
val res23: String = Hello Ada

To convert an integer to a string, you can use the toString method:

scala> 3.toString
val res24: String = 3

In Scala, like in Java, line breaks in strings are represented by the \n character.

Implement treeShow:

def treeShow(t: IntTree): String =
  ???

How would you modify your function to collect the values in post-order? Try comparing the execution of the original pre-order function and the post-order variant on an example, using the substitution model.

Finally, how would you modify your function to collect the values in-order?

Recursion on Strings

In this exercise, you will write recursive functions that operate on strings. A string can be thought of as a list of characters. Like lists, we can apply the same structural recursion principles to strings. Each string has the isEmpty, head and tail methods similar to IntLists:

scala> "Hello Ada".tail
val res25: String = ello Ada

scala> "Hello Ada".tail.head
val res26: Char = e

scala> "Hello Ada".tail.isEmpty
val res27: Boolean = false

scala> " ".isEmpty
val res28: Boolean = false

scala> "".isEmpty
val res29: Boolean = true

Note the type of the head method: it returns a Char, not a String. A Char is a single character, whereas a String is a sequence of characters. A String is surrounded by double quotes, whereas a Char is surrounded by single quotes.

For the following exercises, you cannot use any other method than isEmpty, head and tail on strings.

stringLength

Implement a function that computes the length of a string:

def stringLength(s: String): Int =
  ???

capitalizeString

Implement a function that capitalizes every character in a string:

def capitalizeString(s: String): String =
  ???

You will need the methods toUpper and toString of Char:

scala> 'c'.toUpper
val res30: Char = C

scala> 'c'.toString
val res31: String = c

isBlank

Implement a function that checks if a string is blank (i.e., if it only contains whitespace characters or is empty):

def isBlank(s: String): Boolean =
  ???

You may find the .isWhitespace method of Char useful:

scala> 'c'.isWhitespace
val res29: Boolean = false

scala> ' '.isWhitespace
val res30: Boolean = true

wordCount ⭐️

In this exercise, we call “word” any sequence of non-whitespace characters. For example, " Bonjour ! " has two words. Implement a function that counts the number of words in a string:

def wordCount(s: String): Int =
  ???

Example run:

scala> wordCount("  hello ")
val res32: Int = 1

scala> wordCount("  hello   world !")
val res33: Int = 3

As before, you may use c.isWhitespace to check if a character c counts as whitespace.

def discardWord(s: String): String =
  ???

caesarCipher ⭐️

Implement a function that encrypts a string using the Caesar cipher method. The Caesar cipher is an ancient form of encryption, where each letter in a string is shifted by a fixed number of places down the alphabet.

In this exercise, we assume that the input string only contains English lowercase letters. In addition, we shift the letters in a circular way, so that z shifted by 1 becomes a, z shifted by 2 becomes b, etc.

Every English letter has a corresponding ASCII and Unicode code which is an integer value. Codes of English letters are the same in ASCII and Unicode; the English lowercase letter ‘a’ corresponds to the number 97, ‘b’ is 98, and so on up to ‘z’ which is 122.

In Scala, you can get the ASCII value of an English letter using the toInt method, and convert it back to a character using the toChar method:

scala> 'a'.toInt
val res34: Int = 97

scala> 97.toChar
val res35: Char = a

Here is a REPL session demonstrating how to encrypt a single character:

scala> val aCode = 'a'.toInt
     | val zCode = 'z'.toInt
     | val numLetters = zCode - aCode + 1
val aCode: Int = 97
val zCode: Int = 122
val numLetters: Int = 26

scala> val dCode = 'd'.toInt
val dCode: Int = 100

scala> val dPlus3 = (dCode + 3 - aCode) % numLetters + aCode
val dPlus3: Int = 103

scala> dPlus3.toChar
val res36: Char = g

scala> val dPlus25 = (dCode + 25 - aCode) % numLetters + aCode
val dPlus25: Int = 99

scala> dPlus25.toChar.toString
val res37: String = c

And here are two additional examples of how your caesarCipher function should behave:

scala> caesarCipher("abc", 2)
val res38: String = cde

scala> caesarCipher("abz", 3)
val res39: String = dec

Implement the caesarCipher function accordingly:

def caesarCipher(s: String, shift: Int): String =
  ???

reverseString ⭐️

Implement a function that reverses a string:

def reverseString(s: String): String =
  ???

Polish Notation 🔥

Polish Notation (PN) is a way to write arithmetic expressions where every operator comes before its operands. For example, instead of writing 3 + 4, you would write + 3 4.

Your task is to implement a PN evaluator for an IntList where operators are represented by negative integers: we’ll deal with just addition and multiplication for now:

val Add = -1
val Multiply = -2

For example, the expression 3 + 4 would be represented as IntCons(Add, IntCons(3, IntCons(4, IntNil()))) and the expression 3 * 4 would be represented as IntCons(Mul, IntCons(3, IntCons(4, IntNil()))).

Here is a REPL session demonstrating how the polishEval function should behave:

scala> // List:   [Add, 3, 4]
scala> // Prefix: + 3 4
scala> // Infix:  3 + 4
scala> val expr1 = IntCons(Add, IntCons(3, IntCons(4, IntNil())))
val expr1: recursion.IntCons = IntCons(-1,IntCons(3,IntCons(4,IntNil())))

scala> polishEval(expr1)
val res40: (Int, recursion.IntList) = (7,IntNil())

scala> // List:   [Multiply, Add, 5, 3, 4]
scala> // Prefix: * + 5 3 4
scala> // Infix:  (5 + 3) * 4
scala> val expr2 = IntCons(Multiply, IntCons(Add, IntCons(5, IntCons(3, IntCons(4, IntNil())))))
val expr2: recursion.IntCons = IntCons(-2,IntCons(-1,IntCons(5,IntCons(3,IntCons(4,IntNil())))))

scala> polishEval(expr2)._1
val res41: Int = 32

Before starting to write code, think about how you would evaluate a PN expression. You’ll need to look at the first element of the list to determine what to do next. If it’s an operator, you’ll need to evaluate its arguments (where are they?). If it’s a number, you’ll need to return it. If it’s not a number or a known operator, you’ll need to throw an InvalidOperatorException exception. This time, when encountering an empty list throw a EmptyListException.

Write a few examples on paper and try to figure out how you would evaluate them. Then, try to translate your steps into pseudo-code.

Only once you have a clear idea of how to solve the problem, start implementing polishEval:

def polishEval(l: IntList): (Int, IntList) =
  ???

Git I: Single-user version control

The following questions, exercises, and resources are meant to guide your exploration of version control systems.

Browsing documentation

The official Git tutorial is distributed as manual (man) pages. On macOS, GNU/Linux, and WSL, you can simply type man command to get more information about command. On Windows, you may prefer to browse the online Git documentation instead.

1. Locate the commands that we discussed during the lecture in man gittutorial, man gittutorial-2, and man giteveryday.

2. Look up concepts and commands you don’t know in man gitglossary.

Configuration ⭐️

1. To use Git, you need to configure your user name and email. Look up the corresponding git config commands online, or follow the instructions in man gittutorial. This ensures that your commits carry the right author information.

2. git commit and other interactive commands sometimes need to open a text editor. Use git config to set the core.editor variable globally to your preferred editor. (The demo given in class used Emacs. On GNU/Linux, Git typically defaults to nano, which is reasonably intuitive, while on macOS it defaults to vi, which is great but not too beginner-friendly. For this course, we recommend VSCode.)

Reproducing the first Git demo

1. ⭐️ Re-watch the 15-minutes Git demo that was given at the end of the first Git lecture and follow along on your own terminal (use “Git bash” on Windows). Which commands were necessary? Which were just for demo purposes? (If you run into any issues, try reading the corresponding manual pages.)

   (If you prefer to read, you can follow this written transcript instead.)

2. Notice the file called .gitignore. What is this file for? What would git status have shown after sbt run if sbt new hadn’t created it? (Try it! Replicate the commands, then delete .gitignore and see what git status shows.)

Browsing history

1. Clone a large repository, using the git clone command. For example:

   git clone https://github.com/microsoft/vscode.git
   

2. Read up on the git blame command. What does it do? Try it on the command line on a file in the repository you just cloned.

3. Graphical interfaces can be useful to browse complex history. Find out how to perform a git blame and a git log restricted to a set of lines in your favorite editor, as demonstrated at the end of the demo (the demo used Emacs with magit as the Git UI; you can use VSCode with the Gitlens plugin).

Tracking history and creating patches ⭐️

1. Make a new clone of the course’s exercise repository, and chose an exercise to work on.

2. ⭐️ Make a commit after completing each exercise. Use git commit -m for some of the commits, and git commit without -m for others. What happens when you leave out the -m?

3. If you forget to commit between two exercises, find a Git command or a tool in the VSCode UI that lets you stage only part of your changes (hint).

4. ⭐️ Use git format-patch to share the solution to one exercise with a classmate. Use git am to apply a patch received from a classmate.

5. 🔥 What happens if you try to apply the patch after you’ve already started solving the same exercise? Look up how to handle the resulting situation, which is known as a conflict in Git.

Alternatively, you can pick one of your classes that doesn’t use git, and initialize a new git repository to hold a copy of your exercise solutions for that class.

Exploring large codebases ⭐️

1. On your computer, locate at least one free software (“open source”) application that you use regularly, and find out how to get its source code. Is it hosted in a Git repository?

2. Many projects are hosted on Git platforms such Github or Gitlab. Does Git require you to use such a platform?

3. Clone a git repository of an application that you use and explore the history. Find Git commands to answer the following questions:

   1. What happened in the last three days?
   2. Who contributed to writing the README file?
   3. What is the most recent commit that mentions a bug fix? How did the fix work? When was the buggy code introduced (in which commit?) How long did the bug remain?

4. 🔥 Sometimes you want more information than Git alone can provide directly. Find a way to answer the following questions:

   1. How many C source files does the repository contain?
   2. Which files had the most changes over the last 2 years?
   3. Which is the most commonly edited files in commits that mention a bugfix?
   4. Which was the largest commit (in terms of changed lines) in the last 3 months?

Being a good Gitizen

1. Browse a few popular repositories on Github or Gitlab. Look in particular at the commit messages. Do they use a consistent format? If you’re not sure where to look, a good example is the Spark repository.

2. ⭐️ Some projects take Git commits and change logs very seriously. Pick a free software project and find its contributor guidelines. What do they recommend doing for commits? If you don’t find great examples, see these GNU guidelines, these PostgreSQL ones, and these from Git itself.

© 2023–2025 EPFL. All rights reserved.