Functional Programming in SML - Higher Order Programming
Patterns in Functions
Consider the following two functions. The first one computes the sum of integers from
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 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
identity function simply returns its argument as result, performing no transformation at all.
This leads to the following compact definition of
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
'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.
While using higher-order functions, it seems inconvenient to have to define simple function like
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 are declared with the syntax:
fn P => E
P is the function’s parameter and
E is its body.
Here is how we would define and use a throw-away
- (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 *)
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 + 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
fun reduce (a, b, id, opr, transform) = if a > b then id else opr ((transform a), reduce (a + 1, b, id, opr, transform))
sum in terms of
reduce we should pass
0 as the value of the identity-element (
+ as the value of the operation (
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
We shall also define a similar function for multiplying a sequence. For this,
* is the binary
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
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