Last updated on Sunday, November 17, 2024

Contextual Abstraction

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

We strongly encourage you to solve the exercises on paper first, in groups. After completing a first draft on paper, you may want to check your solutions on your computer. To do so, you can download the scaffold code (ZIP).

This exercise set covers weeks 10 and 13.

This week, intead of providing regular tests, we’ve written all tests using ScalaCheck for automated property-based testing.

Instead of tests, ScalaCheck uses properties: logical statements that should always be true. To check a property, ScalaCheck generates random inputs for your functions, and checks whether the properties hold for those inputs.

If your code falsifies one of the properties, ScalaCheck will provide a counter-example to help you debug your code. Then, you can try the counter-example in a worksheet to check what went wrong.

We will cover ScalaCheck in class in two weeks! In the meantime, feel free to either write your own tests, or read up on ScalaCheck.

Implicit Context (week 10) ⭐️

You have seen in previous lab and exercises an enum for arithmetic expressions. Let’s augment it with a Let form:

enum Expr:
  case Num(value: Int)
  case Var(name: String)
  case Let(name: String, value: Expr, body: Expr)
  case Add(e1: Expr, e2: Expr)
  case Sub(e1: Expr, e2: Expr)
  case Mul(e1: Expr, e2: Expr)

src/main/scala/contextual/Expr.scala

Write an eval function for expressions of this type. You should not use any mutable or global variables or mutable collections.

def evaluate(e: Expr): Int =
  def recur(e: Expr)(using ctx: Map[String, Int]): Int = e match
    case _ => ???

  recur(e)(using Map.empty)

src/main/scala/contextual/Expr.scala

Let(”x”, e1, e2) should be evaluated like {val x = e1; e2}. You can assume that every Var(x) occurs in the body b of an enclosing Let(x, e, b).

For example, the following expression should evaluate to 4:

val e3 = Let("x", Let("y", Num(1), Add(Var("y"), Var("y"))), Mul(Var("x"), Var("x")))
evaluate(e3)

src/main/scala/playground.worksheet.sc

Serialization with implicits (week 10) 🧪

In the webapp lab, we are using type class WireFormat[T] to represent encoding and decoding between JSON and a data type T.

In the original implementation, the type classes for different data types are defined as regular classes, which means, to use the instance of a type, we have to construct its format manually at every place.

In this exercise, your task is to use contextual abstractions to define instances of the type class WireFormat. They are defined in webapp/lib/shared/shared/src/main/scala/wires/Wires.scala.

First, you need to define the general encode and decode functions for wires at the top of the file:

def encodeWire[T](t: T)(using wt: WireFormat[T]): ujson.Value =
  ???

src/main/scala/wires/Wires.scala

def decodeWire[T](js: ujson.Value)(using wt: WireFormat[T]): Try[T] =
  ???

src/main/scala/wires/Wires.scala

With these two functions, you can call encode and decode functions without naming the using parameters.

Then, you need to modify the different instances of WireFormat. For example, the WireFormat[Boolean] was defined as:

object OldBooleanWire extends WireFormat[Boolean]:
  def encode(t: Boolean): Value = Bool(t)
  def decode(js: Value): Try[Boolean] = Try(js.bool)

src/main/scala/wires/Wires.scala

It can be transformed to:

given WireFormat[Boolean] with
  def encode(t: Boolean): Value = Bool(t)
  def decode(js: Value): Try[Boolean] = Try(js.bool)

src/main/scala/wires/Wires.scala

If you encounter any ambiguity error (this may happen when using decodeWire in a complex expression), you can specify the type argument explicitly. Try not to use summon to get the instance of a type class explicitly.

See Importing Givens for details about how to import given instances.

Ordering (week 13) ⭐️

In mathematics, a partial order on a set is an arrangement such that, for certain pairs of elements, one precedes the other. The word partial indicates that not every pair of elements needs to be comparable; that is, there may be pairs for which neither element precedes the other. For example, the set of strings is partially ordered by the substring operator. There are pairs of strings that are not comparable by substring, e.g. “abc” and “def” are not substrings of each other.

A total order or linear order is a partial order in which any two elements are comparable. For example, the set of integers is totally ordered by the <= operator.

See Partially ordered set and Total order for more details.

In Scala, the partial order is represented by scala.math.PartialOrdering, and the total order is represented by scala.math.Ordering (as a subtype of PartialOrdering).

Ordering is a type class that represents the result of comparing two values of a type. It describes both an equivalence relation and a total order on such equivalence classes:

Equivalence relation: {(a, b) | compare(a, b) == 0}
Total order: {(a, b) | compare(a, b) <= 0}

The sign of the result of compare indicates the ordering of the two values, where the exact values do not matter:

Negative: a < b
Zero: a == b
Positive: a > b

To ensure the result is total ordering, the following properties must hold for all a, b, and c on compare:

def inverse[T](x: T, y: T)(using ord: Ordering[T]): Boolean =
  sign(ord.compare(x, y)) == -sign(ord.compare(y, x))

src/main/scala/contextual/Orderings.scala

def transitive[T](x: T, y: T, z: T)(using ord: Ordering[T]): Boolean =
  !(ord.compare(x, y) > 0 && ord.compare(y, z) > 0) || ord.compare(x, z) > 0

src/main/scala/contextual/Orderings.scala

def consistent[T](x: T, y: T, z: T)(using ord: Ordering[T]): Boolean =
  ord.compare(x, y) != 0 || sign(ord.compare(x, z)) == sign(ord.compare(y, z))

src/main/scala/contextual/Orderings.scala

(where the helper function sign represents the sign of the result).

Implement the `Ordering` typeclass for pairs

Implement an instance of the Ordering type class for pairs of type (A, B), where A and B have Ordering instances defined on them.

It should be implemented as a lexicographic ordering, where the first component is ordered first, and the second component is ordered second. That is, (a, b) <= (c, d) if and only if:

a < c, or
a == c and b <= d.

// TODO: you should modify this signature according to the requirements
given pairOrdering[A, B]: Ordering[(A, B)] with
  def compare(x: (A, B), y: (A, B)): Int = ???

src/main/scala/contextual/Orderings.scala

Example use case: Consider a program for managing an address book. We would like to sort the addresses by zip codes first and then by street name. Two addresses with different zip codes are ordered according to their zip code, otherwise (when the zip codes are the same) the addresses are sorted by street name. E.g.

type Address = (Int, String) 
val addressBook: List[Address] = List(
  (1020, "Av. d'Epenex"),
  (1015, "Rte des Noyerettes"),
  (1015, "Rte Cantonale"))

val sortedAddressBook = addressBook.sorted(using Orderings.pairOrdering)

src/main/scala/playground.worksheet.sc

Mapping ordering

Suppose we have a data structure to store students’ information:

case class Student(name: String, year: Int)

src/main/scala/contextual/Orderings.scala

If we want to sort a list of students by their years of admission first and names second, we can create an ordering for Student as follows:

given studentOrdering1: Ordering[Student] with
  def compare(x: Student, y: Student): Int =
    val cmp1 = x.year.compare(y.year)
    if cmp1 != 0 then cmp1 else x.name.compare(y.name)

src/main/scala/contextual/Orderings.scala

However, we already have orderings for Int, String, and pairs, so we can use them to create an ordering for Student.

Your task is to implement a general function “mapping” a known ordering for B to a new ordering for A. It is defined as a function orderingBy, that takes a function f: A => B and an ordering for B and returns an ordering for A. The mapping function f should be constructed carefully such that the resulting ordering follows the law of total ordering as well.

def orderingBy[A, B](f: A => B)(using ord: Ordering[B]): Ordering[A] =
  ???

src/main/scala/contextual/Orderings.scala

With orderingBy, we can create an ordering for Student:

given studentOrdering2: Ordering[Student] = orderingBy((s: Student) => (s.year, s.name))

src/main/scala/contextual/Orderings.scala

Abstract Algebra with Type Classes (week 13)

Recall the SemiGroup and Monoid type classes from the lecture:

trait SemiGroup[A]:
  extension (x: A) def combine(y: A): A

src/main/scala/contextual/Algebra.scala

trait Monoid[A] extends SemiGroup[A]:
  def unit: A

src/main/scala/contextual/Algebra.scala

The laws for SemiGroup and Monoid are:

def associative[T](x: T, y: T, z: T)(using sg: SemiGroup[T]): Boolean =
  x.combine(y).combine(z) == x.combine(y.combine(z))

src/main/scala/contextual/Algebra.scala

def identity[T](x: T)(using m: Monoid[T]): Boolean =
  m.unit.combine(x) == x && x.combine(m.unit) == x

src/main/scala/contextual/Algebra.scala

(since Monoid is also a SemiGroup, the associative law is also required for Monoid)

Generalize `reduce`

We have seen a version of reduce for a list of T where T has a SemiGroup instance:

def reduceSemiGroup[T: SemiGroup](xs: List[T]): T =
  xs.reduceLeft(_.combine(_))

src/main/scala/contextual/Algebra.scala

When we try to generalize reduce to work with any list, we run into a problem: we don’t have a default or fallback value to return when the list is empty.

Your task is to generalize reduce to work on lists of T where T has a Monoid instance such that it also works for empty lists.

def reduce[T: Monoid](xs: List[T]): T =
  xs.foldLeft(???)(???)

src/main/scala/contextual/Algebra.scala

A general way to lift a `SemiGroup` to a `Monoid`

There are some types that have a SemiGroup instance but not a Monoid instance. For example, the set of integers (BigInt) forms a SemiGroup through min. However, there is no corresponding identity element to form a Monoid.

given SemiGroup[BigInt] with
  extension (x: BigInt) def combine(y: BigInt): BigInt = x.min(y)

src/main/scala/contextual/Algebra.scala

To show that BigInt does not form a Monoid through min, suppose there exists an identity element u in BigInt such that min(a, u) == a for all a: BigInt. However, we can always find a v = u + 1 such that u < v and min(v, u) == u != v. Hence, there is no such identity element u in BigInt.

By adding an extra “positve infinity” element to the set and define it as the greatest element, we can form a Monoid through min.

In Scala, we usually use Option to represent the default/fallback value. Therefore, we can use Option[BigInt] to represent the integer set with “positive infinity”:

None represents the “positive infinity” element
Some(a) represents the integer a
None.combine(Some(a)) is Some(a) for all a: BigInt, since a < +infinity.
Some(a).combine(Some(b)) is Some(min(a, b)) for all a, b: BigInt

The properties of Monoid[Option[BigInt]] correspond to the properties of Monoid[Option[A]] where A has a SemiGroup instance.

Your task is to implement a Monoid instance for Option[A] given a SemiGroup instance for A.

given [A: SemiGroup]: Monoid[Option[A]] = ??? // you can modify `=` to `with`

src/main/scala/contextual/Algebra.scala

With the Monoid instance for Option[A], we can lift a list of BigInt to a list of Option[BigInt] and then apply the general reduce function to it to find the minimum element.

val bigints = List(BigInt(-8), BigInt(2), BigInt(0), BigInt(4), BigInt(100))
reduceSemiGroup(bigints)
val posInfinity: Option[BigInt] = None
val liftedBigints = posInfinity :: bigints.map(Option(_))
// adding a positive infinity value to the list should not change the result
reduce(liftedBigints)

src/main/scala/playground.worksheet.sc

Acknowledgement

The monoid exercise is adapted from the documentation of the Cats library.