Newer
Older
% Type-Directed Programming — Motivating Example
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
%
%
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.
~~~
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…