Last updated on Monday, October 14, 2024

Comprehensions

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

As before, exercises or questions marked ⭐️ are the most important, 🔥 are the most challenging, and 🧪 are most useful for this week’s lab.

for comprehensions

Scala does not have for loops; instead, it has for comprehensions. Comprehensions are particularly powerful when you need to combine and filter results from multiple collections. Let’s see some examples!

Warm-up ⭐️

In previous weeks we saw how to filter, map over, and flatten lists using recursive functions and List API functions. This week, we have a new way to perform these computations: comprehensions.

Just 3 (filters) 🧪

Using a for comprehension, write a function that filters a list of words (represented as Strings), keeping only words of length 3:

def onlyThreeLetterWords(words: List[String]): List[String] =
  ???

LOUDER (maps)

Using a for comprehension, write a function that converts a list of words (represented as Strings) to uppercase, using the .toUpperCase() method:

def louder(words: List[String]): List[String] =
  ???

For example List("a", "bc", "def", "ghij") should become List("A", "BC", "DEF", "GHIJ").

Echo (flatMaps)

Using a for comprehension, write a function that repeats each word in a list of words n times. Write a comprehension with two separate <- clauses, and use either Iterable.fill(n)(word) to create an iterable of n times the value word, or (1 to n) to iterate n times.

def echo(words: List[String], n: Int): List[String] =
  ???

For example List("a", "bc", "def", "ghij") should become List("a", "a", "bc", "bc", "def", "def", "ghij", "ghij") if n == 2.

All together now 🧪

Using a for comprehension, write a function that converts all words in a list to upper case, removes all words whose length is not three, and repeats all others n times:

def allTogether(words: List[String], n: Int): List[String] =
  ???

For example List("All", "together", "now") should become List("ALL", "ALL", "ALL", "NOW", "NOW", "NOW") if n is 3.

Cross product

Reimplement the cross-product function from last week using a for comprehension.

Additionally, your function should now take a Scala List as input, and return a Scala List as output.

def crossProduct[A, B](l1: List[A], l2: List[B]): List[(A, B)] =
  ???

Triangles in a directed graph

Reimplement the triangles function from last week using a for comprehension and Scala Lists.

def triangles(edges: DirectedGraph): List[(NodeId, NodeId, NodeId)] =
  ???

Glob matching (ungraded callback to find!)

The real Unix find command takes a “glob pattern” for its -name filter: it supports wildcards like ? and * to allow for partial matches. For example,

• find -name 2023-*.jpg finds all files whose name starts with 2023- and ends with .jpg, and
• find -name 20??-*.jp*g finds all files whose name starts with 20, then has two arbitrary characters, then a dash, any letter, and finally .jp followed by anything followed by g. This would allow users to find 2002-03-18T11:15.jpg or 2002-03-18 modified.jpeg, for example.

Write a function glob(pattern, input) that returns a boolean indicating whether a glob pattern matches a string (represented as a list of Chars):

def glob(pattern: List[Char], input: List[Char]): Boolean =
  ???

The rules are as follows:

• ? matches one arbitrary character
• * matches an arbitrary sequence of characters
• Other characters match themselves

The whole pattern must match the whole string: partial matches are not allowed.

Based on your implementation, can you prove that a pattern that does not contain wildcards matches only itself? That “*” matches everything? That a pattern with only ? matches all strings of the same length as the pattern? That repeated * can be replaced by single *?

Des chiffres et des lettres

“Des chiffres et des lettres” is a popular TV show in French-speaking countries.

In this show, contestants take turns guessing the longest word that can be made from a list of letters, and finding a way to arrange a list of numbers into an arithmetic computation to get as close as possible to a target number. For example:

• For the letters G N Q E U T I O L Y C E P H, an excellent contestant would immediately propose the word “POLYTECHNIQUE”.

• For the numbers 2 5 3 9 100 9 and the target number 304, an excellent contestant would suggest 3 * (9 + 9) + 5 * 100 / 2, and exclaim “le compte est bon!”.

Des lettres 🧪

Write a function longestWord which, given a wordlist (a collection of words) represented as a List[String] and a collection of letters represented as a String, finds the longest word that can be made by reordering a subset of these strings. You can write your function directly, or follow the steps below.

Des chiffres 🔥

Write a function leCompteEstBon that takes a List of integers and a target number, and returns an arithmetic expression that evaluates to the target sum, if one exists. The allowable operators are +, - (only when the result is nonnegative), *, and / (only when the division is exact), as well as parentheses. For the purpose of this exercise, assume that we are only interested in exact results, using all provided integers. The result should be an expression of type Expr:

trait Expr:
  val value: Option[Int]

case class Num(n: Int) extends Expr:
  val value = Some(n)

abstract class Binop extends Expr:
  val e1, e2: Expr // Subexpressions
  def op(n1: Int, n2: Int): Option[Int] // How to evaluate this operator

val value: Option[Int] =
  for
    n1 <- e1.value
    n2 <- e2.value
    r <- op(n1, n2)
  yield r

case class Add(e1: Expr, e2: Expr) extends Binop:
  def op(n1: Int, n2: Int) =
    Some(n1 + n2)

case class Sub(e1: Expr, e2: Expr) extends Binop:
  def op(n1: Int, n2: Int) =
    if n1 < n2 then None else Some(n1 - n2)

case class Mul(e1: Expr, e2: Expr) extends Binop:
  def op(n1: Int, n2: Int) =
    Some(n1 * n2)

case class Div(e1: Expr, e2: Expr) extends Binop:
  def op(n1: Int, n2: Int) =
    if n2 != 0 && n1 % n2 == 0 then Some(n1 / n2) else None

Tracing comprehensions

Performance issues

The following function has surprisingly poor performance. Why?

def badZip[T1, T2](l1: List[T1], l2: List[T2]): Seq[(T1, T2)] =
  for i <- (0 to math.min(l1.length, l2.length) - 1)
  yield (l1(i), l2(i))

A subtlety in desugaring and tracing comprehensions 🔥

A keystone of the CS214 debugging guide is to “understand the system”. Sometimes observing the system’s final output is enough, but other times adding instrumentation helps. It pays to be careful, however: any time you change the system that you are debugging, you risk changing its behavior, too. Let’s see an example.

As we’ve seen previously, tracing can help not just with recursion, but also with comprehensions: to insert a tracing instruction into a comprehension, we use _ = println(…).

1. Here is an instrumented comprehension. What does the tracing code print, and in which order?

   def traceIfTrue(b: Boolean, label: String) =
     if b then println(label)
     b
   
   def filter_tracedIfTrue(l: Seq[Int]): Seq[Int] =
     for
       n <- l
       if traceIfTrue(n % 5 == 0, f"$n is a multiple of 5!")
       if traceIfTrue(n % 3 == 0, f"  $n is also a multiple of 3!")
       if traceIfTrue(n >= 10, f"    $n is also greater than 10!")
     yield n
   

   src/main/scala/comprehensions/Tracing.scala

   Confirm your guess by running this code in a worksheet.

2. Here is a different, arguably more readable way to trace the same comprehension. What will it print?

   def filter_traced(l: Seq[Int]): Seq[Int] =
     for
       n <- l
       if n % 5 == 0
       _ = println(f"$n is a multiple of 5!")
       if n % 3 == 0
       _ = println(f"  $n is also a multiple of 3!")
       if n >= 10
       _ = println(f"    $n is also greater than 10!")
     yield n
   

   src/main/scala/comprehensions/Tracing.scala

   As before, confirm your guess by running this code in a worksheet.

3. What can you conclude?

Non-structural recursion: numbers

Factorial ⭐️

Define a recursive function which returns the factorial of the input integer.

def factorial(n: Int): Int =
  ???

Fast exponentiation

Fast exponentiation is a technique to optimize the exponentiation of numbers:

b²ⁿ = (b²)ⁿ = (bⁿ)²
b²ⁿ⁺¹ = b * b²ⁿ

Define a function that implements this fast exponentiation.

def fastExp(base: Int, exp: Int): Int =
  ???

Base-N encoding ⭐️

In this exercise, your task is to implement a function that encodes a given integer into its representation in a given base. The result should be a list of integers.

For instance:

1. Encode the number 9 to base-2: decimalToBaseN(9, 2) should return List(1, 0, 0, 1).
2. Encode the number 20 to base-16: decimalToBaseN(20, 16) should return List(1, 4).

Your task is to implement the decimalToBaseN function.

def decimalToBaseN(number: Int, base: Int, acc: List[Int] = Nil): List[Int] =
    ???

Non-structural recursion: collections

Coin Change ⭐️

You are given a list of coin denominations coins: List[Int], which are the different values a coin can have, and a target amount. You need to determine the number of distinct ways to make up the target amount using any combination of the provided coin denominations. You can use each coin denomination an unlimited number of times.

def coinChange(coins: List[Int], amount: Int): Int =
    ???

Let’s illustrate the coin change problem with an example.

Suppose you have the following coin denominations: List(1, 2, 5), and you want to make change for the amount 5. How many different ways are there to make change for 5 using these coins?

Here are the different ways to make change for 5:

5 = 5 (use one 5-coin)
5 = 2 + 2 + 1 (use two 2-coins and one 1-coin)
5 = 2 + 1 + 1 + 1 (use one 2-coin and three 1-coins)
5 = 1 + 1 + 1 + 1 + 1 (use five 1-coins)

So, there are a total of 4 different ways to make change for 5 using the denominations List(1, 2, 5).

Merge sort ⭐️

Merge sort is a popular and efficient comparison-based sorting algorithm that follows the divide-and-conquer paradigm. It works by recursively dividing a list into smaller sublists, sorting them, and then merging them back together into a single sorted list.

Roughly, merge sort proceeds in the following way:

• Split the list into two sublists.
• Recursively sort each sublist.
• Merge the two sorted sublists back into one sorted list.

Split

Define a function that splits a list into two halves, whose length difference is less than or equal to 1.

There are multiple ways to implement such function. You may use a library function.

For example, if the list has n elements, the first list has the first $\lfloor n / 2 \rfloor$ elements and the second has the rest.

Or, when counting elements from 1, the first list has all items that were at odd positions, and the second one has all items that were at even positions. For example, the list a b c d e f g will be split into a c e g and b d f.

def split[A](l: List[A]): (List[A], List[A]) =
  ???

Merge

Write a merge function that takes two sorted lists and returns a sorted list containing all elements of both lists.

def merge(xs: List[Int], ys: List[Int]): List[Int] =
  ???

Sort

Implement the mergeSort function.

If the list has one or zero elements, what should the function do?

def mergeSort(xs: List[Int]): List[Int] =
    ???

Exercises from the slides

N-Queens

Write a function isSafe which tests if a queen placed in an indicated column col is secure amongst the other placed queens. It is assumed that the new queen is placed in the next available row after the other placed queens (in other words: in row queens.length).

def isSafe(col: Int, queens: List[Int]): Boolean =
  ???

© 2023, 2024 EPFL. All rights reserved.