Higher-order functions
Here is a first-order function that
counts the number
of even numbers in a list.
fun countEvens nil = 0
|countEvens (first::rest) = if first mod 2 = 0 then 1 + countEvens rest
else countEvens rest;
Here is another first-order function
that counts the number of odd
numbers in a list.
fun countOdds nil = 0
|countOdds (first::rest) = if first mod 2 = 1 then 1 + countOdds rest
else countOdds rest;
Notice
that both functions perform essentially the same task, using a
different test to decide which elements to include in the count. This
suggests that we can parameterize the
test (i.e. turn it into a parameter), and replace the two first-order
functions with a single, second-order
function that accepts a test function as a parameter, as shown
below.
fun count (f, nil) = 0
|count (f, first::rest) = if f(first) then 1+count(f, rest) else count (f, rest);
If we defined the following functions:
fun isEven x = x mod 2 = 0;
fun isOdd x = x mod 2 = 1;
we can use the function count and pass these functions as parameters,
as shown below.
count(isEven,
[1,2,3,4,5,6,7,8,9]);
OR
count(isOdd,
[1,2,3,4,5,6,7,8,9]);
If the functions isEven and isOdd are not used for any other
purpose, they can be conveniently replaced by anonymous functions. Anonymous
functions allow us to specify a function as a part of the call
to count, without explicitly
defining it first, as shown below.
count( fn
x => x mod 5 = 0, [1,2,3,4,5,6,7,8,9]);
OR
count(fn x => x mod 7 = 0 andalso x
> 17, [1,2,3,4,7,6,49,8,9]));
Currying
It would be useful if we could define
new functions in terms of the function count, paired with a test function. For example,
val countEvens = count (fn x => x
mod 2 = 0);
val countOdds = count (fn x => x mod 2 = 1);
This would not work as things stand, because count, as defined above, expects a tuple - a
function and
a list - as a parameter.
Rewriting count as a curried function
solves this problem.
fun count f nil = 0
|count f (first::rest) = if f(first) then 1 + count f rest else count f
rest;
Note how this declaration is different from the earlier declaration of count. This declaration of count
does not require both a
function and a list. count
can also be called by passing it just
a function. That call returns
a (anonymous) function that can be bound to a name, by assignment
to a val, as shown below.
Having redefined count as a
curried function, we can now define new functions in terms of count and an appropriate test function.
val countEvens = count (fn x => x
mod 2 = 0);
val countOdds = count (fn x => x mod 2 = 1);
Note that in the example above, countEvens and countOdds are just names (vals) bound to count specialized by an anonymous function. Alternatively, you can define new functions in terms of count, as shown below.
fun countEvens alist = count (fn x => x
mod 2 = 0) alist;
fun countOdds alist = count (fn x => x mod 2 = 1) alist;