Last updated on Monday, December 18, 2023

Pattern Matching

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

This exercise set is intended to help you practice pattern matching.

In previous exercises and labs, we used if conditionals and . field accessors to write functions on data types such as lists or trees. This week, we’ll use pattern matching to make these functions more succinct and readable. We’ll move from this:

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

to this:

def reduceMatch(f: (Int, Int) => Int)(l: IntList): Int =
  l match
    case IntNil              => throw IllegalArgumentException("Empty list!")
    case IntCons(hd, IntNil) => hd
    case IntCons(hd, tl)     => f(hd, reduceMatch(f)(tl))

Most functional programmers find the second one much more readable, because it aligns the way the data is destructed (taken apart into a head and a tail) and the way the data is constructed (assembled from a head and a tail):

def constructDestruct =
  IntCons(1, IntCons(2, IntNil)) match
    case IntCons(a, IntCons(b, IntNil)) =>
      println(f"Found $a and $b")
    case _ => throw Exception("Not possible!")

Weekdays

Days of the week are a great example of simple enumerations. So, which day is tomorrow? let’s implement a function to find out.

The enum representing weekdays is defined as follows:

enum Weekday:
  case Monday
  case Tuesday
  case Wednesday
  case Thursday
  case Friday
  case Saturday
  case Sunday

Complete the following two functions:

1. next returns the next day of the week:

     def next(d: Weekday): Weekday =
       ???
   

   src/main/scala/patmat/WeekdayOps.scala

2. prev returns the previous day of the week:

     def prev(d: Weekday): Weekday =
       ???
   

   src/main/scala/patmat/WeekdayOps.scala

Tri-booleans ⭐️

By now you’re very familiar with Booleans. But in real life, not every thing is Yes or No: sometimes we just don’t know! Tri-boolean logic helps with this by adding an indeterminate value, Maybe:

enum TriBool:
  case Yes
  case No
  case Maybe

Maybe is like a Boolean value that is not yet known.

1. Take the time to think of how Maybe combine with Yes and No.

   • If I have two objects, one which is for sure blue, and one that may be blue, then can I say that I have at least one blue item? Is that for sure or maybe? What does this entail about the “or” operator on tri-Booleans?

   • If I have the same two objects (one blue, one maybe blue), can I conclusively say that not all or my objects are blue? Can I promise that they are all blue? What does this entail about the “and” operator on tri-Booleans?

2. Implement the following operations (we expect that you’ll find pattern-matching very nice for that!)

     def neg(b: TriBool): TriBool =
       ???
   

   src/main/scala/patmat/TriBoolOps.scala

     def and(b1: TriBool, b2: TriBool): TriBool =
       ???
   

   src/main/scala/patmat/TriBoolOps.scala

     def or(b1: TriBool, b2: TriBool): TriBool =
       ???
   

   src/main/scala/patmat/TriBoolOps.scala

     def nand(b1: TriBool, b2: TriBool): TriBool =
       ???
   

   src/main/scala/patmat/TriBoolOps.scala

   Want to test your code? Run testOnly TriBoolOpsTest in sbt.

   nand is a very surprising operator. If you’re not familiar with it, inspect the test cases, or read more about it!

3. Try proving on paper the following properties of these functions:

   • For any a, neg(neg(a)) = a.
   • For any a and b, neg(and(a, b)) = or(neg(a), neg(b)).
   • For any a and b, neg(or(a, b)) = and(neg(a), neg(b)).

Contexts ⭐️

Now that you have a bit of experience with pattern matching, let’s use it to construct more complex types. In this exercise we’ll study contexts, which are essentially lists of keys and values. This exercise is particularly useful for this week’s lab.

Our contexts associate names (Strings) with values (Ints), and let us do the following:

• Create an empty context;
• Add an additional key/value pair (called a “binding”) to a context;
• Look up a key to retrieve the corresponding value;
• Remove a key and its corresponding value.

For instance, we can have a context which associates "x" with 1 and "y" with 2. We can then look up the keys: looking up "x" in the context produces 1, looking up "y" produces 2, and looking up "z" or any other name results in a not-found error. We can add more mapping in the context: after associating "z" with 3, looking "z" up in the new context will result in 3, instead of an error.

Think of what Scala types and features you may use to represent a context before proceeding.

enum Context:
  case Empty
  case Cons(name: String, value: Int, tail: Context)

Implement the following three functions:

• empty returns an empty context:

    def empty: Context =
      ???
  

  src/main/scala/patmat/EnumContext.scala

• cons forms a new context by associating a new pair of name-value in an existing context:

    def cons(name: String, value: Int, rem: Context) =
      ???
  

  src/main/scala/patmat/EnumContext.scala

• lookup looks a name up in a given context:

    def lookup(ctx: Context, name: String): LookupResult =
      ???
  

  src/main/scala/patmat/EnumContext.scala

  Notice the return type: we used another enum, called LookupResult, to capture two possible results: either finding a value, or indicating that the name could not be found.

  enum LookupResult:
    case Ok(v: Int)
    case NotFound
  

  src/main/scala/patmat/EnumContext.scala

• erase drops all bindings with the given name in the context:

    def erase(ctx: Context, name: String): Context =
      ???
  

  src/main/scala/patmat/EnumContext.scala

  (As a bonus, try writing a function that removes just the first binding for a given name!)

• Finally, filter drops all bindings that fail the test pred (i.e. for which pred evaluated to `false):

    def filter(ctx: Context, pred: (String, Int) => Boolean): Context =
      ???
  

  src/main/scala/patmat/EnumContext.scala

Tree Mapping and Tree Reducing

In week 1 we worked with trees using a clunky API of .left, .right, and .isEmpty. This time, let’s do it the right way. And, to mix things up a bit, we’ll see a tree that contains values only at the leaves, instead of in every node (revisiting the examples from week 1 is another great exercise, though!)

The IntTree enum is defined as the following:

enum IntTree:
  case Leaf(value: Int)
  case Branch(left: IntTree, right: IntTree)

Here is an example:

Tree Mapping ⭐️

Let’s start with the treeMap function:

  def treeMap(tree: IntTree, op: Int => Int): IntTree =
    ???

It takes a tree and a function, and creates a new tree by applying the function on the value of each leaf node in the tree.

For instance, let’s name the tree we just saw in the diagram as t. The following diagram dipicts the computation of treeMap(t, x => x + 1).

Tree Reducing

The second task is the treeReduce function:

  def treeReduce(tree: IntTree, op: (Int, Int) => Int): Int =
    ???

Given a tree and an operator, the function reduces the values in the tree with the operator. To see what that means, let’s illustrate the call treeReduce(t, (a, b) => a + b) in diagrams, which essentially computes the sum of all values in the leaf node of t.

Intuitively, it is a bottom-up aggregation of values in the leaves. The values flow from the bottom to the root. At each branch node, the aggregated results from the two children are merged using op, the operator supplied to treeReduce.

But many of us prefer to think of it as a “pull” operation: to compute its own value, each internal node “pulls” the values of the subtrees by making recursive call.

A bit more formally,

• For each branch node, e.g. Branch(left, right), The function should recurse on both left and right and merge the results with op.
• For the leaf node, e.g. Leaf(value), the value is returned.

Map and Reduce

The last task is the treeMapReduce function, which first maps the stores in each leaf with the mapper, then reduces these mapped values using reducer.

Start with a version that maps values to strings, then reduces the strings on the leaf to the result string:

  def treeMapReduce(tree: IntTree, mapper: Int => String, reducer: (String, String) => String): String =
    ???

Now implement a version on Doubles:

  def treeMapReduceDouble(tree: IntTree, mapper: Int => Double, reducer: (Double, Double) => Double): Double =
    ???

Are there similarities? Soon we will learn how to unify the two.

IntList

Let’s implement functions on IntList again, this time with pattern matching. Before starting this part of exercises, we suggest you implementing several IntList questions from previous weeks’ exercises using pattern matching to warm yourself up!

polishEval

First, rewrite polishEval (from week 1) with pattern-matching:

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

Throw InvalidOperationNumber exception if the operator is not defined, and InvalidExpression if the input is not a valid polish-notation expression.

Compare your version new version with the original if-based implementation. Which one is more readable?

zipWith ⭐️

map, fold, and other functions that we have previously studied operate on a single list. We have already seen that some of these generalize to trees; here, we will see how one of them (map) generalizes to multiple lists. This function is called zipWith in Scala:

  def zipWith(l1: IntList, l2: IntList, op: (Int, Int) => Int): IntList =
    ???

Here is one possible specification for zipWith, using l[n] to mean “the n-th element of list l”:

Given two lists xs and ys and an operator op, let zs be zipWith(xs, ys, op). Then, zs should have length min(length(xs), length(ys)), and the i-th element of zs should be op(xs[i], ys[i]) for all i.

Note the part about the length of zs. For instance, zipWith(IntNil, IntCons(1, Nil), (x, y) => x + y) should equal to IntNil.

Implement zipWith. Do you see a connection with map?

A modular implementation of zipWith ⭐️

zipWith does a lot of work at once, and we can make it a bit more modular. For this, let’s define an intermediate type IntIntList of lists of pairs of ints:

enum IntIntList:
  case IntIntNil
  case IntIntCons(xy: (Int, Int), xs: IntIntList)
import IntIntList.*

1. Define a function zip to construct a list of pairs from a pair of lists:

     def zip(l1: IntList, l2: IntList): IntIntList =
       ???
   

   src/main/scala/patmat/IntListOps.scala

2. Define a function unzip to construct a pair of lists from a list of pairs:

     def unzip(l: IntIntList): (IntList, IntList) =
       ???
   

   src/main/scala/patmat/IntListOps.scala

3. Define a function map2to1 on lists of pairs that produces a list of ints:

     def map2to1(op: (Int, Int) => Int)(l: IntIntList): IntList =
       ???
   

   src/main/scala/patmat/IntListOps.scala

4. Rewrite zipWith using (some of) the functions above.

     def zipThenWith(l1: IntList, l2: IntList, op: (Int, Int) => Int): IntList =
       ???
   

   src/main/scala/patmat/IntListOps.scala

5. Use zipWith to implement a function movingWindow on lists that returns sequences of consecutive pairs in its input list. For example, movingWindow applied to the list a b c d e should produce the list ab bc cd de.

     def movingWindow(l: IntList): IntIntList =
       ???
   

   src/main/scala/patmat/IntListOps.scala

6. What relation is there between zip and unzip? What properties can you prove?

extractSecond ⭐️

Enumerations and case classes are often useful to distinguish multiple kinds of results. In an imperative language this would often be done with an exception: a function returns a result, and may throw various exceptions if the result cannot be computed. In Scala (and functional programming), we tend to use case classes instead, with one case per kind of result.

For example, a function that extracts the second element of a list might return a type like the following:

enum ExtractResult:
  case SecondElem(i: Int)
  case NotLongEnough
  case EmptyList

When the input list is empty, extractSecond returns EmptyList; when the input list is not long enough to have a second element (i.e. it only has one element), extractSecond returns NotLongEnough; finally, when the input list has a second element, the function returns it.

Implement extractSecond:

  def extractSecond(l: IntList): ExtractResult =
    ???

Natural Numbers 🔥

There are lots of encodings for natural numbers (that is, integers that is greater than or equal to zero). Today we will study one of the simplest one:

enum UnaryNat:
  case Zero
  case Succ(pred: UnaryNat)

Basically, there are two cases:

• Zero represents the zero, 0;
• Succ represents n+1 given an existing natural number n.

One may think of a natural encoded in this way as a Matryoshka doll:

• Zero is a smallest, solid doll,
• Succ wraps a doll inside a larger doll.

Then, the number represented by a UnaryNat is the degree of nesting of the doll (how many nested dolls there are). For example, 2 is represented as Succ(Succ(Zero)).

Implement the following functions:

1. Conversion to/from integers:

   1. Here is an implementation of fromInt. Is anything wrong with it?

      def fromInt(n: Int): UnaryNat =
        n match
          case 0 => Zero
          case _ => Succ(fromInt(n - 1))
      

      src/main/scala/patmat/UnaryNatOps.scala

   2. Implement toInt.

        def toInt(n: UnaryNat): Int =
          ???
      

      src/main/scala/patmat/UnaryNatOps.scala

2. Addition between UnaryNats

     def add(n: UnaryNat, m: UnaryNat): UnaryNat =
       ???
   

   src/main/scala/patmat/UnaryNatOps.scala

3. Multiplication between UnaryNats; for this, we have already provided you with a erroneous implementation: help us fix it… or write your own from scratch!

     def multiply(n: UnaryNat, m: UnaryNat): UnaryNat =
       m match
         case Zero => n
         case Succ(m0) => add(n, multiply(n, m0))
   

   src/main/scala/patmat/UnaryNatOps.scala

   • Run the test (testOnly -- "*multiply*") to find a failing test case. Use it to pinpoint the problem.
   • Use println to inspect how the function is recursively invoked.

4. Subtraction between UnaryNats, saturating at zero (this means that minus(x, y) == max(0, x - y). For instance, minus(Succ(Zero), Succ(Succ(Zero))) == Zero.

     def minus(n: UnaryNat, m: UnaryNat): UnaryNat =
       ???
   

   src/main/scala/patmat/UnaryNatOps.scala

5. Parity checks:

     def isEven(n: UnaryNat): Boolean =
       ???
   

   src/main/scala/patmat/UnaryNatOps.scala

     def isOdd(n: UnaryNat): Boolean =
       ???
   

   src/main/scala/patmat/UnaryNatOps.scala

How would you implement isEven and isOdd with if?

Compare the pattern-match-based and if-based implementations: which ones look better in terms of conciseness and readability?

Binary Search Tree 🔥

We have seen contexts which associates names with associated values. Looking up a name in both enum-based and function-based contexts takes $\mathrm{O}(n)$, where $n$ is the number of bindings. This can be suboptimal if the context is frequently looked up. Is there a better solution?

If we know the relations between the names, we can arrange them in a smarter way. For instance, we can sort and distribute the names within a tree structure. This can significantly improve the efficiency of the lookup operation, especially when compared to searching through every element in a linked list. Binary Search Tree (BST) is a data structure that stores key-value bindings and supports efficient lookup operation. In this exercise we consider BSTs that associate integers to strings.

What are BSTs? Let’s see examples! The following trees stores the bindings 0 -> "a", 1 -> "b" and 2 -> "c". Here 0 -> "a" means a binding which associates 0 (the key) with "a" (the value).

Each box denotes a node, whose left part is the key and right part the value.

And this one stores 0 -> "a", 1 -> "b", 2 -> "c", 3 -> "d":

Do you have any clues for the principle of BSTs? Have a guess.

See the principle

Given each node in a BST whose key is k:

All keys in its left child is less than k, and all keys in its right child is greater than k.

Find a BST that stores 0 -> "a", 1 -> "b", 2 -> "c", 3 -> "d" and 4 -> "e".

The answer is not unique, any tree that conforms to the principle and stores these bindings works. Here is a reference answer.

reference tree

The following shows the Scala enum representing BSTs:

enum BST:
  case Leaf
  case Branch(k: Int, v: String, l: BST, r: BST)

It closely mirrors the structure of the trees shown above:

• A Branch is a node, with the k-v pair and the two children.
• Leaf represents the leaf, which is not drawn on the diagrams above: when a child is missing in the diagram, there is a leaf implicitly in its position.

Now you task is to complete the following operations.

Basic operations

  def find(tree: BST, key: Int): FindResult =
    ???

  def insert(tree: BST, key: Int, value: String): BST =
    ???

Rotation

We have seen that lookup is efficient in BST. But there is a pitfall: in fact, a BST can degenerate into a linked list, and in that case the lookup operation is no more efficient than looking up a context.

For instance, the following BST, which stores the same set of bindings as one we saw before, conforms perfectly to the principle of BST but has poor performance for looking up.

Therefore, one shall prefer a balanced BST over an imbalanced one. The problem then becomes: how one can balance a BST?

The rotation operation addresses this problem. How rotation works? See the following diagram:

It illustrates two rotation operations: left- and right-rotation. We color the root node in a tree in blue. Take left-rotation as an example. Given an input tree in the form of the left hand side, it transforms the tree into the right hand side. The tree root changes from k1 to k2. You can verify that, as long as the tree on LHS is a BST, the RHS conforms to the BST principle as well.

Now, implement the following functions.

  def rotateLeft(tree: BST): BST =
    ???

  def rotateRight(tree: BST): BST =
    ???

To learn more about tree rotation and the way they are used to maintain the balance of a tree, this link is for you!

Contexts as Functions 🔥

Previously, we have seen how to represent contexts as Scala enums. Now you will try another alternative: representing them with functions!

type Context =
  String => LookupResult

This exercise takes a lot of thinking, so we recommend pondering with other students, and reading the hint below.

Implement the following four functions for function-based contexts:

  def empty: Context =
    ???

  def cons(name: String, value: Int, rem: Context): Context =
    ???

  def lookup(ctx: Context, name: String): LookupResult =
    ???

  def erase(ctx: Context, name: String): Context =
    ???

The following additional questions can help further your understanding:

• Compare the efficiency of cons, lookup and erase for enum-based and function-based contexts. When would you use one, and when would you use the other?
• Are there operations that you can implement on function contexts but not enum contexts?
• Can you convert a function context into an enum context? How about the reverse?
• What happens when your println an enum-based context? (Try in the playground!)