Based on the code snippets developed in class, summaries and explanations in this document were drafted with the assistance of generative AI. The author verified all facts, revised the text for coherence, and takes full responsibility for the final content.

Week 8 Overview

Week 8 covers dynamic dispatch and inheritance, parametric polymorphism, and subtyping. These snippets develop parametric polymorphism with type classes: separating data from ordering, passing orderings implicitly with using and given, and lifting operations to lists.

Parametric Polymorphism with Type Classes

This walkthrough starts with an inheritance-based design for ordering and then refactors it into a type-class style design. The progression illustrates a core separation-of-concerns idea: data types should not need to inherit behavior just to participate in generic algorithms.

1) Mixing concerns: data inherits ordering

In this first version, values implement ordering themselves by inheriting from OrdI[T].

trait OrdI[T]:
  def compare(other: OrdI[T]) : Int
end OrdI

case class MyInt(v: Int) extends OrdI[MyInt]:
  def compare(other: OrdI[MyInt]): Int =
    v - other.asInstanceOf[MyInt].v
end MyInt

def maxI[T](x: OrdI[T], y: OrdI[T]) : OrdI[T] =
  if x.compare(y) > 0 then x else y
end maxI

maxI(new MyInt(3), new MyInt(4))

This works, but ordering logic is tightly coupled to the data representation (MyInt). Next we separate data from behavior.

2) Separate concerns with an explicit order object

We define Ord[T] as a standalone abstraction and pass an instance explicitly.

trait Ord[T]:
  def compare(x: T, y: T) : Int
end Ord

def maxExplicit[T](x: T, y: T)(ord: Ord[T]) : T =
  if ord.compare(x, y) > 0 then x else y
end maxExplicit

val intOrder = new Ord[Int] {
  def compare(x: Int, y: Int) : Int = x - y
}

maxExplicit(4, 5)(intOrder)

Now maxExplicit is fully generic, but call sites can become verbose. Scala 3 context parameters remove that boilerplate.

3) Use using parameters for contextual orderings

The algorithm still depends on Ord[T], but callers can provide it contextually.

def max[T](x: T, y: T)(using ord: Ord[T]) : T =
  if ord.compare(x, y) > 0 then x else y
end max

max(4, 5)(using intOrder)

To make most calls fully implicit, we provide default given instances.

4) Install default instances with given

These instances are discovered automatically when a method requires Ord[T].

given Ord[Int]:
  def compare(x: Int, y: Int) : Int = x - y

given Ord[String]:
  def compare(x: String, y: String) : Int =
    x.compareTo(y)

max(4, 5)
max("A", "B")

With this setup, generic collection operations become concise.

5) Lift max to lists: maximum

The following versions show equivalent ways to propagate contextual evidence.

def maximum1[T](xs: List[T])(using ord: Ord[T]) : T =
  xs.reduceLeft(max(_, _)(using ord))

def maximum2[T](xs: List[T])(using ord: Ord[T]) : T =
  xs.reduceLeft(max)

def maximum[T : Ord](xs: List[T]) : T =
  xs.reduceLeft(max)

The context-bound form T : Ord is the most compact and idiomatic here. Next we reuse this infrastructure to derive new behavior.

6) Derive inverse order and implement minimum

Instead of writing a second aggregation algorithm, we define inverse ordering once and reuse maximum.

def inverseOrd[T](using ord: Ord[T]) = new Ord[T]:
  def compare(x: T, y: T) : Int = ord.compare(y, x)

def minimum[T : Ord](xs: List[T]) : T =
  maximum(xs)(using inverseOrd)

maximum(List(1, 2, 3, 4, 5))
minimum(List(1, 2, 3, 4, 5))

This final step highlights the main design payoff: we can extend ordering behavior compositionally without changing data types or duplicating algorithms.