Scala Tutorial

Remember the sorting function:

def insertionSort(xs: List[Int]): List[Int] = {
  def insert(y: Int, ys: List[Int]): List[Int] =
    ys match {
      case List() => y :: List()
      case z :: zs =>
        if (y < z) y :: z :: zs
        else z :: insert(y, zs)
    }

  xs match {
    case List() => List()
    case y :: ys => insert(y, insertionSort(ys))
  }
}

How to parameterize insertionSort so that it can also be used for lists with elements other than Int (like, for instance, Rational)?

def insertionSort[T](xs: List[T]): List[T] = ...

The above attempt does not work, because the comparison < in insert is not defined for arbitrary types T.

Idea: parameterize insert with the necessary comparison function.

Parameterization of Sort

The most flexible design is to make the function insertionSort polymorphic and to pass the comparison operation as an additional parameter:

def insertionSort[T](xs: List[T])(lessThan: (T, T) => Boolean): List[T] = {
  def insert(y: T, ys: List[T]): List[T] =
    ys match {
      …
      case z :: zs =>
        if (lessThan(y, z)) y :: z :: zs
        else …
    }

  xs match {
    …
    case y :: ys => insert(y, insertionSort(ys)(lessThan))
  }
}

Calling Parameterized Sort

We can now call insertionSort as follows:

val nums = List(-5, 6, 3, 2, 7)
val fruit = List("apple", "pear", "orange", "pineapple")

insertionSort(nums)((x: Int, y: Int) => x < y)
insertionSort(fruit)((x: String, y: String) => x.compareTo(y) < 0)

Or, since parameter types can be inferred from the call insertionSort(xs):

insertionSort(nums)((x, y) => x < y)

Parametrization with Ordered

There is already a class in the standard library that represents orderings.

scala.math.Ordering[T]

provides ways to compare elements of type T. So instead of parameterizing with the lessThan operation directly, we could parameterize with Ordering instead:

def insertionSort[T](xs: List[T])(ord: Ordering[T]): List[T] = {
  def insert(y: T, ys: List[T]): List[T] =
    … if (ord.lt(y, z)) …

  … insert(y, insertionSort(ys)(ord)) …
}

Ordered Instances:

Calling the new insertionSort can be done like this:

insertionSort(nums)(Ordering.Int)
insertionSort(fruits)(Ordering.String)

This makes use of the values Int and String defined in the scala.math.Ordering object, which produce the right orderings on integers and strings.

Implicit Parameters

Problem: Passing around lessThan or ord values is cumbersome.

We can avoid this by making ord an implicit parameter:

def insertionSort[T](xs: List[T])(implicit ord: Ordering[T]): List[T] = {
  def insert(y: T, ys: List[T]): List[T] =
    … if (ord.lt(y, z)) …

  … insert(y, insertionSort(ys)) …
}

Then calls to insertionSort can avoid the ordering parameters:

insertionSort(nums)
insertionSort(fruits)

The compiler will figure out the right implicit to pass based on the demanded type.

Rules for Implicit Parameters

Say, a function takes an implicit parameter of type T.

The compiler will search an implicit definition that

• is marked implicit
• has a type compatible with T
• is visible at the point of the function call, or is defined in a companion object associated with T.

If there is a single (most specific) definition, it will be taken as actual argument for the implicit parameter. Otherwise it's an error.

Type Classes

The combination of types parameterized and implicit parameters is also called type classes.

Exercises

Define an ordering for the Rational type:

class Rational(x: Int, y: Int) {

  private def gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
  private val g = gcd(x, y)

  lazy val numer: Int = x / g
  lazy val denom: Int = y / g
}

val compareRationals: (Rational, Rational) => Int = res0

implicit val rationalOrder: Ordering[Rational] =
  new Ordering[Rational] {
    def compare(x: Rational, y: Rational): Int = compareRationals(x, y)
  }

val half = new Rational(1, 2)
val third = new Rational(1, 3)
val fourth = new Rational(1, 4)
val rationals = List(third, half, fourth)
insertionSort(rationals) shouldBe List(fourth, third, half)