Last updated on Sunday, November 17, 2024

Structural Recursion

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

Exercise sessions are meant to be done together in groups, on whiteboards or blackboards. Read more in the course policies.

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 think about these exercises on paper first.

Exercises marked with ⭐️ are the most important ones. Exercises marked with 🔥 are the most challenging ones.

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.

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 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 it toString method:

scala> 3.toString
val res24: String = 3

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

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.

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 exercies, 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 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 an operator, you’ll need to throw an IllegalArgumentException exception.

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 implement polishEval:

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

© 2023, 2024 EPFL. All rights reserved.