Functional Programming in SML - Higher order Functions
Welcome to the fifth part of the Learn Functional Programming in SML series!
The previous post demonstrated some powerful abstractions that can be built by passing functions as arguments to other functions. The expressive power of the language is further increased by creating functions whose returned values are themselves functions.
The first two sections of this post will explain the basics of writing functions returning functions. After that we will look at two important function building techniques - composition and partial application.
Function Returning Functions
makeAdder function given below:
fun makeAdder x = fn (y) => x + y
This function takes an integer
x and returns a function which, when called adds
x to its argument.
Now we can make as many “adders” as we want:
- val add5 = makeAdder 5; (* val add5 = fn : int -> int *) - val add2 = makeAdder 2; (* val add2 = fn : int -> int *) - add5 10; (* val it = 15 : int *) - add2 10; (* val it = 12 : int *)
add2 are new functions dynamically created by
Both of them have their own copies of
x. In other words, they are objects with their own local state.
How does SML create functions with local state? To answer this question, we need to understand the concepts of free variables and lexical scope.
Free variables and Lexical scope
Let’s look at the body of
makeAdder once again:
fn (y) => x + y
You can see two variables in this expression - the bound variable
y and the free variable
A symbol is bound in an expression if it has been established as a variable, either by appearing as a parameter,
or by variable-binding expressions like
let. Symbols which are not bound are said to be free.
What should be the value of a free variable? To find this out, we need to consider the scope rules used by the language.
In a dynamically scoped language, the value of a free variable is looked up in the context where the expression is evaluated
during runtime. If the adding function was bound to a symbol
f, if could be evaluated as follows in a dynamically scoped language:
- let val x = 5 in (f 10) end; (* 15 *)
In a lexically scoped language, instead of the runtime context, the value for a free variable is looked up in the context where
the expression is defined. SML is a lexically scoped language. So it captured the binding for
x from the parameter of the
As the function returned by
makeAdder can be called from a place where
x is not visible, SML must save copies of the
local bindings and package them with the returned function. The data structure that keeps track of variable bindings is
known as the environment. The combination of a function and the environment that captures the variables bindings in its
defining context is known as a closure.
In a language like SML, all functions have a reference to its defining environment. So the terms functions and closures can be used interchangeably.
When a closure is called, its environment is extended with the arguments in the call. Thus the environment becomes the “local state” that is preserved across multiple applications of the closure.
To put things more graphically, this is the closure returned by the call
[[x: 5], fn (y) x + y]
This is how the environment in the closure changes, for the calls
add5 10 and
[[x: 5, y: 10] fn (y) x + y] [[x: 5, y: 2] fn (y) x + y]
The body of the function
x + y evaluated in these two closures will yield the results
A practical application of functions as return values is in creating transformers.
A transformer is a function that take another function
f as argument and return a new
function that in some way transforms the result of
A simple but useful transformer is the complement function which takes a predicate
and returns a function that will always return the opposite value of calling
fun complement (p) = fn (x) => not(p x)
The following program demonstrates the usage of
fun isEven(x) = (x mod 2) = 0 val isOdd = complement isEven isOdd 5 (* true *) isEven 5 (* false *) isEven 4 (* true *) isOdd 4 (* false *)
This program shows that despite its simplicity,
complement is an important building-block.
It can enable a library writer to eliminate half of his predicates, because library users can define
the other half simply as complements!
Functional composition allows us to combine multiple functions into a new function. The composition of the functions
c(x) = g(f(x)).
We can define a higher-order function that takes two functions
g and produce a function
c that is the composition of
fun comp (f, g) = fn (x) => g(f(x)) (* val comp = fn : ('a -> 'b) * ('b -> 'c) -> 'a -> 'c *)
A description of the type of
- The argument is a tuple of two functions -
('a -> 'b) * ('b -> 'c)
- The first function takes an argument of type
'aand returns a value of type
- The second function takes a value of type
'band returns a value of type
- As a consequence of (1) and (2),
compreturns a function that takes a value of type
'aand returns a value of type
Basically, the function returned by
comp will send a value of type
'a through the composed
g to produce a value of type
'c. As we noted in an earlier post, type variables
'c can stand for any type as long as calls to
comp satisfy the constraints established
by the type signature above.
The following program uses the
comp operator to compose the
add2 functions into an
val add5 = makeAdder 5 val add2 = makeAdder 2 val add7 = comp(add5, add2) add7 10 (* val it = 17 : int *)
Composition is so important in functional programming that SML provides the the infix
o (lower-case ‘O’) operator
to make it easy to compose functions:
val add14 = add5 o add2 o add7 add14 10 (* val it = 24 : int *)
All the functions we have written so far have a single parameter, sometimes expressed as a tuple written with parenthesis and commas. The tuple data structure is good enough to write functions that look and behave like multi-parameter functions in C or Python.
SML also allows to write functions in a different form where the function name is followed by two or more parameters, without
parenthesis or commas. Let us now try to understand the difference between this kind of functions with functions with a tuple parameter.
Consider the following two definitions of the
fun exponent1 (x, y) = if y = 0 then 1.0 else x * exponent1 (x, y-1) (* val exponent1 = fn : real * int -> real *) fun exponent2 x y = if y = 0 then 1.0 else x * exponent2 x (y-1); (* val exponent2 = fn : real -> int -> real *)
Both functions capture the same computation:
- exponent1 (2.0, 3); (* val it = 8.0 : real *) - exponent2 2.0 3; (* val it = 8.0 : real *)
But their types are different. The function
exponent1 has the type
fn : real * int -> real, meaning it takes
a tuple of a
int as argument and returns a
The second function has the type
fn : real -> int -> real. This means
exponent2 takes a
real as argument and returns
a function that takes an
int which in-turn produces a
real. As a consequence,
exponent2 can be partially instantiated -
by calling it with only the first argument. This will return a function that can be called later with an
so as to finish the computation.
This partial application technique is demonstrated by the following program:
- val f = exponent2 2.0; (* val f = fn : int -> real *) - f 3; (* val it = 8.0 : real *) - f 10; (* val it = 1024.0 : real *)
Partial functions like
exponent2 allows us to create new functions by applying the function to some, but not all, of its parameters.
Partial functions are also known as curried functions, named after the
mathematician Haskell Curry, who helped develop this technique.
This post demonstrated some techniques for writing functions that create new functions. At the core of these techniques is the concept of a closure, a function that keeps track of local state.
With this post we have covered all the basic idioms of programming with first-class functions. Now we need to learn to use these techniques for solving large, real-world problems.
But before we can start tackling large problems, we need some more tools to structure and manipulate data more complex than numbers, strings, and tuples. The next few posts will introduce you to these tools.
Note that name and e-mail are required for posting comments