Skip to content
Snippets Groups Projects
progfun2-4-1.md 2.67 KiB
Newer Older
% Type-Directed Programming — Motivating Example
Martin Odersky's avatar
Martin Odersky committed
%
%

Sorting Lists of Numbers
========================

Consider a method `sort` that takes as parameter a `List[Int]` and
returns another `List[Int]` containing the same elements, but sorted:

~~~
def sort(xs: List[Int]): List[Int] = {
  ...
  ... if x < y then ...
  ...
}
~~~

At some point, this method has to compare two elements `x` and `y`
of the given list.

Making `sort` more General
==========================

Problem: How to parameterize `sort` so that it can also be
used for lists with elements other than `Int`, such as `Double`
or `String`?

A straightforward approach would be to use a polymorphic type
`A` for the type of elements:

~~~
def sort[A](xs: List[A]): List[A] = ...
~~~

But this does not work, because the comparison `<` is not defined for
all arbitrary types `A`.

Parameterization of `sort`
==========================

The most flexible design is to pass the comparison operation
as an additional parameter:

~~~
def sort[A](xs: List[A])(lessThan: (A, A) => Boolean): List[A] = {
  ...
  ... if lessThan(x, y) then ...
  ...
}
~~~

Calling Parameterized `sort`
============================

We can now call `sort` as follows:

~~~
scala> val xs = List(-5, 6, 3, 2, 7)
scala> val strings = List("apple", "pear", "orange", "pineapple")

scala> sort(xs)((x, y) => x < y)
res0: List[Int] = List(-5, 2, 3, 6, 7)

scala> sort(strings)((f1, f2) => f1.compareTo(f2) < 0)
res1: List[String] = List(apple, orange, pear, pineapple)
~~~

Parameterization with Ordering
==============================

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

~~~
scala.math.Ordering[A]
~~~

Provides ways to compare elements of type `A`. So, instead of
parameterizing with the `lessThan` function, we could parameterize
with `Ordering` instead:

~~~
def sort[A](xs: List[A])(ord: Ordering[A]): List[A] = {
  ...
  ... if ord.lt(x, y) then ...
  ...
}
~~~

Ordering Instances
==================

Calling the new `sort` can be done like this:

~~~
import scala.math.Ordering

sort(xs)(Ordering.Int)
sort(strings)(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.

~~~
object Ordering {
  val Int = new Ordering[Int] {
    def lt(x: Int, y: Int) = x - y < 0
  }
}
~~~

Reducing Boilerplate
====================

Problem: Passing around `Ordering` arguments is cumbersome.
Martin Odersky's avatar
Martin Odersky committed

~~~
sort(xs)(Ordering.Int)
sort(ys)(Ordering.Int)
sort(strings)(Ordering.String)
~~~

Sorting a `List[Int]` value always uses the same `Ordering.Int` argument,
sorting a `List[String]` value always uses the same `Ordering.String`
argument, and so on…