by vijay | tags: [ learn-fp-in-sml functional-programming functional SML OCaml tutorial ]
Functional Programming in SML - Higher Order Programming
The last part of this series introduced a basic technique in functional programming, namely recursion. Today we shall learn another important functional technique known as higher-order programming.
Patterns in Functions
Consider the following two functions. The first one computes the sum of integers from a
through b
:
fun sumInts (a, b) =
if a > b then 0
else a + sumInts (a + 1, b)
The second one computes the sum of the squares of the integers in the given range:
fun sumSquares (a, b) =
if a > b then 0
else (a * a) + sumSquares (a + 1, b)
You may have noticed that the two functions for the most part are identical. The only difference is the
transformation applied to a
before it is added to the running sum. Basically, these functions capture the
general idea of “summation of a sequence”.
A powerful language should allow us to abstract the idea of summation itself so that all particular sums can be expressed in terms of a “universal” sum function.
Such abstractions can be easily built if the language treats functions as first-class types. A value of a first-class type can be:
- created on demand,
- passed to functions as arguments,
- returned by functions as results and
- stored in data structures.
We have already encountered many types that are first-class in SML - int, real, bool, string, char and tuple.
Functional languages assign first-class status to functions as well. This feature is at the core of building higher-order abstractions.
Higher-order Programming
Higher-order programming refers to a collection of programming idioms that becomes possible when a language has functions as first-class values.
Before we look at the details, here is the story behind the name:
A language that does not allow functions as arguments is known as a first-order language. A language that allows at least one first-order function as argument is of second-order and so on. A language that place no restrictions on functional arguments is a higher-order language. SML is a higher-order language.
We can express the “summation of a series” as a generic function by passing the “transformation” function as an extra argument:
fun sum (a, b, transform) =
if a > b then 0
else (transform a) + sum (a + 1, b, transform)
Assume that we have the square function defined below:
fun square x = x * x
Now we can define sumSquares
in terms of sum
by passing square
as the transformer:
fun sumSquares (a, b) = sum (a, b, square)
What will be the transformer for sumInts
? As the integers are not supposed to be transformed in any way, it
has to be the identity
function shown below:
fun identity x = x
The identity
function simply returns its argument as result, performing no transformation at all.
This leads to the following compact definition of sumInts
:
fun sumInts (a, b) = sum (a, b, identity)
An aside on polymorphism
If you typed identity
into the REPL, you might have noticed that its inferred type is val identity = fn : 'a -> 'a
.
The identifiers beginning with the apostrophe (‘) are type variables. They denote types and not ordinary values. In the case of
identity
, SML has decided that the argument can be of any type and hence designates its type as 'a -> 'a
. SML often uses
type variables like 'a
and 'b
to represent the type of something that can be of any type.
A function that is able to admit arguments of many types are known as polymorphic (poly = many; morph = form). There is more to say about polymorphism, but let’s save that for a later post.
Function literals
While using higher-order functions, it seems inconvenient to have to define simple function like square
.
This is especially so if its only purpose is to serve as an argument to another function.
SML allows us to define functions as literal values, by using the keyword fn
. Function values are also known as function expressions or
anonymous functions.
Anonymous functions are declared with the syntax:
fn P => E
where P
is the function’s parameter and E
is its body.
Here is how we would define and use a throw-away square
function:
- (fn x => x * x) 10;
(* val it = 100 : int *)
Anonymous functions are more useful when they are created on-demand to be used as arguments for other functions:
- fun sumSquares (a, b) = sum (a, b, fn (x) => x * x);
(* val sumSquares = fn : int * int -> int *)
- sumSquares (10, 20);
(* val it = 2585 : int *)
Generalizing Sum
We saw how to abstract the idea of “adding together the numbers in a sequence”.
More generally the sum
function we defined can be seen as a folder or a reducer
because what it does is to reduce a sequence of numbers into a single value.
This reduction is achieved by interspersing the +
operator within the sequence.
The base case of the function returns 0
, which is the identity
element for addition.
This is because, for any integer n
, n + 0 = n
.
With these concepts in mind, we can generalize sum
even further to arrive at a function that can
reduce a sequence using a binary operation like +
and its matching identity element.
Here is the definition of the reduce
abstraction:
fun reduce (a, b, id, opr, transform) =
if a > b then id
else opr ((transform a), reduce (a + 1, b, id, opr, transform))
To define sum
in terms of reduce
we should pass 0
as the value of the identity-element (id
) parameter
and +
as the value of the operation (opr
).
fun sum (a, b, transform) =
reduce (a, b, 0, op +, transform)
Note: We can use an infix operator like +
as a function by preceding it with the keyword op
.
We shall also define a similar function for multiplying a sequence. For this, *
is the binary
operator and 1
is the identity element.
fun prod (a, b, transform) =
reduce (a, b, 1, op *, transform)
- prod (1, 10, fn x => x);
(* val it = 3628800 : int *)
Note: The mathematically inclined reader may recognize the reduce
function as an expression of the
Commutative monoid.
Conclusion
This post introduced higher-order programming. We saw the precise definition of this term and learned how to write simple higher-order functions.
In the next post we shall look at two other important functional programming techniques - function composition and partial evaluation.
Note that name and e-mail are required for posting comments