Last updated on Monday, October 14, 2024

2021 CS-210 Midterm

The exam without solutions is available as PDF: 2021-midterm-empty.pdf.

Exercise 1

trait Tree[T]:
    def height: Int = this match
        case EmptyTree(_) => 0
        case Node(left, _, right, _) => Math.max(left.height, right.height) + 1

    def isBalanced: Boolean = this match
        case EmptyTree(_) => true
        case Node(left, _, right, _) => left.isBalanced && right.isBalanced && Math.abs(left.height - right.height) <= 1

case class EmptyTree[T](leq: (T, T) => Boolean) extends Tree[T]
case class Node[T](left: Tree[T], elem: T, right: Tree[T], leq: (T, T) => Boolean)
extends Tree[T]

Tests

def intLeq(a: Int, b: Int) = a <= b

val exTree1 = Node(
    Node(
        Node(EmptyTree(intLeq), 1, EmptyTree(intLeq), intLeq),
        2,
        Node(EmptyTree(intLeq), 3, EmptyTree(intLeq), intLeq),
        intLeq
    ),
    5,
    Node(
        Node(EmptyTree(intLeq), 7, EmptyTree(intLeq), intLeq),
        9,
        Node(
            Node(EmptyTree(intLeq), 10, EmptyTree(intLeq), intLeq),
            15,
            Node(EmptyTree(intLeq), 25, EmptyTree(intLeq), intLeq),
            intLeq
        ),
        intLeq
    ),
    intLeq
)

val exTree2 = Node(
    Node(
        Node(
            Node(EmptyTree(intLeq), 25, EmptyTree(intLeq), intLeq),
            15,
            Node(EmptyTree(intLeq), 10, EmptyTree(intLeq), intLeq),
            intLeq
        ),
        9,
        Node(EmptyTree(intLeq), 7, EmptyTree(intLeq), intLeq),
        intLeq
    ),
    5,
    Node(
        Node(EmptyTree(intLeq), 3, EmptyTree(intLeq), intLeq),
        2,
        Node(EmptyTree(intLeq), 1, EmptyTree(intLeq), intLeq),
        intLeq
    ),
    intLeq
)

val tree3 = Node(
    Node(
        Node(
            Node(EmptyTree(intLeq), 25, EmptyTree(intLeq), intLeq),
            15,
            Node(EmptyTree(intLeq), 10, EmptyTree(intLeq), intLeq),
            intLeq
        ),
        9,
        Node(EmptyTree(intLeq), 7, EmptyTree(intLeq), intLeq),
        intLeq
    ),
    5,
    EmptyTree(intLeq),
    intLeq
)

assert(exTree1.height == 4)
assert(exTree2.height == 4)
assert(EmptyTree(intLeq).height == 0)
assert(exTree1.isBalanced)
assert(exTree2.isBalanced)
assert(!tree3.isBalanced)

Exercise 2

enum Expr:
  case Var(name: String)
  case Op(name: String, args: List[Expr])

import Expr._

final case class UnknownVarException(name: String) extends Exception
final case class UnknownOpException(name: String) extends Exception

There was multiple correct solutions. Here two possible solutions:

def eval1(e: Expr, context: Map[Var, Int]): Int = e match 
    case Var(name) => context.get(Var(name)) match
        case Some(n) => n
        case _ => throw UnknownVarException(name)
    case Op(name, args) =>
        val nargs = args.map(eval1(_, context))
        name match
            case "*" => nargs.foldLeft(1)(_ * _)
            case "+" => nargs.foldLeft(0)(_ + _)
            case _ => throw UnknownOpException(name)

def eval2(e: Expr, context: Map[Var, Int]): Int = e match 
    case sym: Var if context.contains(sym) => context(sym)
    case sym: Var => throw UnknownVarException(sym.name)
    case Op("*", args) => args.foldLeft(1)(_ * eval2(_, context))
    case Op("+", args) => args.foldLeft(0)(_ + eval2(_, context))
    case Op(name, _) => throw UnknownOpException(name)

Comments

A lot of you assumed that the arguments of Ops can only be Vars, but these can be Ops as well as in Op("*", List(Op("+", List(Var("x"), Var("x"))), Var("y"))), so the function needs to call itself recursively for each operation argument.
Minor: Map[Var, Int] maps Var to Ints, so the argument passed to context.get must be a Var, not a String.

Tests

for eval <- Seq(eval1, eval2) do
    assert(eval(Op("+", List()), Map()) == 0)
    assert(eval(Op("+", List(Var("x"))), Map(Var("x") -> 2)) == 2)
    assert(eval(Op("+", List(Var("x"), Var("y"))), Map(Var("x") -> 2, Var("y") -> 3)) == 5)
    assert(eval(Op("*", List()), Map()) == 1)
    assert(eval(Op("*", List(Var("x"))), Map(Var("x") -> 2)) == 2)
    assert(eval(Op("*", List(Var("x"), Var("y"))), Map(Var("x") -> 2, Var("y") -> 3)) == 6)
    assert(eval(Op("*", List(Op("+", List(Var("x"), Var("x"))), Var("y"))), Map(Var("x") -> 2, Var("y") -> 3)) == 12)

Exercise 3

Exercise 3.1

Type parameter A in map

def map[B >: A](f: B => C): Transform[A, C]

Full code

trait Transform[-A, +B]:
    def apply(x: A): B
    def map[C](f: B => C): Transform[A, C]
    def followedBy[C](t: Transform[B, C]): Transform[A, C]

Solution Explanation

If you try to compile this piece of code, you’ll get:

scala> trait Transform[-A, +B]:
     |     def apply(x: A): B
     |     def map[C](f: A => C): Transform[A, C]
     |     def followedBy[C](t: Transform[B, C]): Transform[A, C]
     | 
-- Error: ----------------------------------------------------------------------
3 |    def map[C](f: A => C): Transform[A, C]
  |               ^^^^^^^^^
  |contravariant type A occurs in covariant position in type A => C of parameter f
1 error found

Short Explanation

For map, consider the function with type (A => C) => Transform[A, C], it is contravariant in A => C and covariant in Transform[A, C].

Since the map function is contravariant in A => C, and we know that a function with type A => C is contravariant in A, the map function should be covariant in A.

However, since the map function is covariant in Transform[A, C], and we know Transform[A, C] is contravariant in A, the map function is contravariant in A. This contradiction is exactly what the error message said.

Check Yourself

If a generic class T is contravariant in type F, and the generic class with type F is contravariant in type X, what’s the relationship between T and X?

Solution

For any arbitrary type DerivedX such that DerivedX <: X.

Since F is contravariant in type X, we know F[X] <: F[DerivatedX].

Since T is contravariant in type F, we know T[F[DerivatedX]] <: T[F[X]].

Therefore, T is covariant in type X.

Longer Explanation

Here is an explanation post on Ed Discussion.

To see the problem of map, let’s consider the following types:

Apple <: Fruit
FruitBox
ApplePieces

According to the given definition, we know:

Transform[Fruit, FruitBox] <: Transform[Apple, FruitBox]

If the given definition is valid, then the following code will be allowed (assuming all ??? are properly implemented):

val fruitToFruitBox: Transform[Fruit, FruitBox] = ???
val appleToFruitBox: Transform[Apple, FruitBox] = fruitToFruitBox // valid because Transform[Fruit, FruitBox] <: Transform[Apple, FruitBox]
val cutApple: Apple => ApplePiece  = ???
appleToFruitBox.map(cutApple)

Here, fruitToFruitBox is a transform from any fruit into a fruit box. Due to the assignment in line 2, for the transformappleToFruitBox, what’s waiting to be transformed is any fruit (may not be an apple). The last line contains a problem: we’re attempting to cut any fruit into apple pieces, which is problematic.

Thanks to the compiler which throws an error in the original definition, such problems are avoided.

Another Example

There’s another example from Tour of Scala:

trait List[+A]:
  def prepend(elem: A): NonEmptyList[A] = NonEmptyList(elem, this)

case class NonEmptyList[+A](head: A, tail: List[A]) extends List[A]

object Nil extends List[Nothing]

This program implements a singly-linked list. Nil represents an empty list with no elements. class NonEmptyList is a node which contains an element of type A (head) and a reference to the rest of the list (tail). The trait List and its subtypes are covariant because we have +A.

However, this program does not compile because the parameter elem in prepend is of type A, which we declared covariant. This doesn’t work because functions are contravariant in their parameter types and covariant in their result types.

Exercise 3.2

Is the following subtype assertion true?                yes    no

List[Triangle]            <:  List[AnyRef]              [X]    [ ]
List[Shape]               <:  List[AnyVal]              [ ]    [X]
List[String]              <:  List[Shape]               [ ]    [X]
Transform[Point, Circle]  <:  Transform[Point, Any]     [X]    [ ]
Transform[Point, Shape]   <:  Transform[Shape, Point]   [ ]    [X]
Transform[Shape, Point]   <:  Transform[Point, Shape]   [X]    [ ]

Exercise 4

Axioms:

(1) Nil.reverse === Nil

(2) (x::xs).reverse === xs.reverse ++ (x::Nil)

(3) (xs++ys)++zs === xs++(ys++zs)

(4) Nil map f === Nil

(5) (x::xs) map f === f(x) :: (xs map f)

(6) Nil ++ ys === ys

(7) xs ++ Nil === xs

(8) x::xs ++ ys === x::(xs ++ ys)

(9) (l1 ++ l2).map(f) === l1.map(f) ++ l2.map(f)

Exercise 4.1

We must prove:

(10) (l1 ++ l2).reverse === l2.reverse ++ l1.reverse


By induction on l1:

- l1 is Nil:

        (Nil ++ l2).reverse ===
    (6) l2.reverse

        l2.reverse ++ Nil.reverse ===
    (1) l2.reverse ++ Nil ===
    (7) l2.reverse

- l1 is x::xs

    IH: (xs ++ l2).reverse === l2.reverse ++ xs.reverse

         (x::xs ++ l2).reverse ===
    (8)  (x::(xs ++ l2)).reverse ===
    (2)  (xs ++ l2).reverse ++ (x::Nil) ===
    (IH) l2.reverse ++ xs.reverse ++ x::Nil ===
    (3)  l2.reverse ++ (xs.reverse ++ x::Nil) ===
    (2)  l2.reverse ++ (x::xs).reverse ===
         l2.reverse ++ l1.reverse

Exercise 4.2

We must prove:

(l1 ++ l2).reverse.map(f) === l2.reverse.map(f) ++ l1.reverse.map(f)


Direct proof using axiom 10 proved in 4.1:

     (l1 ++ l2).reverse.map(f) =
(10) (l2.reverse ++ l1.reverse).map(f) =
(9)  l2.reverse.map(f) ++ l1.reverse.map(f)


Or without using axiom 10:

By induction on l1:

- l1 is Nil:

        ((l1 ++ l2).reverse).map(f) ===
    (6) l2.reverse.map(f)

        l2.reverse.map(f) ++ l1.reverse.map(f) ===
    (1) l2.reverse.map(f) ++ Nil.map(f) ===
    (4) l2.reverse.map(f) ++ Nil ===
    (7) l2.reverse.map(f)


- l1 is x::xs

    IH: ((xs ++ l2).reverse).map(f) === l2.reverse.map(f) ++ xs.reverse.map(f)

         ((x::xs) ++ l2).reverse.map(f) ===
    (8)  (x::(xs ++ l2)).reverse.map(f) ===
    (2)  ((xs ++ l2).reverse ++ (x::Nil)).map(f) ===
    (9)  ((xs ++ l2).reverse.map(f)) ++ ((x::Nil).map(f)) ===
    (IH) l2.reverse.map(f) ++ xs.reverse.map(f) ++ (x::Nil).map(f) ===
    (3)  l2.reverse.map(f) ++ (xs.reverse.map(f) ++ (x::Nil).map(f)) ===
    (9)  l2.reverse.map(f) ++ (xs.reverse ++ x::Nil).map(f)) ===
    (2)  l2.reverse.map(f) ++ ((x::xs).reverse.map(f)) ===

Exercise 5

Exercise 5.1

There was multiple correct solutions:

def takeWhileStrictlyIncreasing1(list: List[Int]): List[Int] = list match
    case Nil => Nil
    case x :: Nil => list
    case x1 :: x2 :: xs => if x1 < x2 then x1 :: takeWhileStrictlyIncreasing1(x2 :: xs) else List(x1)

def takeWhileStrictlyIncreasing2(list: List[Int]): List[Int] = {
    def fun(ls: List[Int], last: Int): List[Int] = ls match
        case x :: xs if x > last => x :: fun(xs, x)
        case _ => Nil

    list match
        case x :: xs => x :: fun(xs, x)
        case Nil => Nil
}

def takeWhileStrictlyIncreasing3(list: List[Int]): List[Int] = {
    def fun(ls: List[Int], last: Option[Int]): List[Int] = (ls, last) match
        case (x :: xs, Some(last)) if x > last => x :: fun(xs, Some(x))
        case (x :: xs, None) => x :: fun(xs, Some(x))
        case _ => Nil

    fun(list, None)
}

Comments

It was possible to write a correct implementation using foldLeft. Note that foldLeft traverses the whole list and cannot “early return” like a recursive call. This possible solution was not very clean as it required a flag or a condition to check that foldLeft should do nothing once it passed the first decreasing step. Avoid using foldLeft when you do not need to traverse the whole list every time.
When we do not ask for a tail recursive implementation, the solution can be more readable without an accumulator. You should favor a simple and readable version.
The solution takeWhileStrictlyIncreasing3 uses Option and is elaborate. We include this solution for a good example of using Option but takeWhileStrictlyIncreasing2 is simpler and more readable.

Exercise 5.2

def increasingSequences(list: List[Int]): List[List[Int]] = list match
    case Nil => Nil
    case _ =>
        val prefix = takeWhileStrictlyIncreasing(list)
        prefix :: increasingSequences(list.drop(prefix.length))

Comments

It is important to store prefix to avoid calling twice takeWhileStrictlyIncreasing.
In the empty list case, some students made the confusion of returning a list containing the empty list. In this case, we have: List[List[Int]]() == Nil != List(Nil) == List(List[Int]()).