Functions are the “salt” of functional languages: they can appear everywhere in expressions, they can be applied, passed as parameters, and returned back by other functions. When a function may take as input another function, or can output a function, we say it is a higher-order function.
You have already seen here some examples of higher-order functions. For instance:
The type operator
→ associates to the right.
So, the correct parenthesization of the type
int → int → int is
int → (int → int).
sumc is a function that, when applied to an integer x, evaluates to a function
that maps an integer y to the sum x+y.
Higher-order functions can also take functions as arguments.
For instance, let
countzero be a function
that computes the number of zeros (in a given range) of a function
f: int → int taken as input.
# let rec countzero f a b = if a>b then 0 else (if f a = 0 then 1 else 0) + (countzero f (a+1) b);; val countzero : (int -> int) -> int -> int -> int = <fun> # countzero (fun x -> x*x - 4) 0 5;; - : int = 1
The type of
countzero can be read as follows:
when fed with a function with type
int → int (the parameter
and two integers (the parameters
it evaluates to an integer (the number of zeros of
f in the range [a,b]).
We now write an higher-order function that
takes as input a function
f: int → int, and evaluates to a function
which maps each input
f(y) + y.
We can do this in several ways. First, the “official” definition:
As an example, let us apply
h to the successor function, and then apply the resulting function to the integer 3:
# h (fun x -> x+1) 3;; - : int = 7
With the syntactic sugar defined here, we can rewrite
h more shortly as follows:
Using the syntactic sugar twice, we obtain:
All the three versions of
h are equivalent.
None is better than the others: choose the one which you prefer.
One of the simplest functions one can write is the identity:
# let id = fun x -> x;; val id : 'a -> 'a = <fun>
Note that the type of
id looks quite strange!
'a → 'a should be read as follows:
for all types
a, the function
id returns a value of type
a when applied to a value of type
In other words, the function
id is polymorphic: it can be applied to argument of many different types
(actually, of any type).
# id 3;; - : int = 3 # id "pippo";; - : string = "pippo" # id (fun x -> x+1);; - : int -> int = <fun>
Other simple examples of polymorphic functions are the projection functions on pairs.
fst selects the first element of a pair, while
snd selects the second element.
# let fst (x,y) = x;; # let snd (x,y) = y;; val fst : 'a * 'b -> 'a = <fun> val snd : 'a * 'b -> 'b = <fun>
Polymorphism plays a key role in functional programming languages,
since it allows a quite general way of defining and composing functions.
Consider, for instance, a function
abs that takes as input a function
f and computes its absolute value
The type of
abs says that, for all types
takes as input a function from
int , and it returns a function from
Let us apply
abs to the function that maps each x to x.
comp takes as input two functions and returns their composition.
g, the codomain of
g must coincide with the domain of
This is what the type of
the type of
'c → 'a, while the type of
'a → 'b.
Then, the type of the composition f ° g is
'c → 'b.
# let comp f g = fun x -> f (g x);; val comp : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b = <fun>
As an example, we exploit
comp to give an alternative definition of
We have already discussed on curried vs. uncurried functions. We now explicitly define how to transform an uncurried function into curried form (currying), and, viceversa, how to transform a curried function into uncurried form (uncurrying).
curry below transforms a function of type
'a * 'b → 'c
into a function of type
'a → 'b → 'c.
That is, a function taking a pair of arguments (x,y) becomes an higher-order function with argument x, returning a function with argument y.
# let curry f = fun x y -> f (x,y);; val curry : ('a * 'b -> 'c) -> 'a -> 'b -> 'c = <fun>
# let addpair (x,y) = x+y;; val addpair : int * int -> int = <fun> # let add = curry addpair;; val add : int -> int -> int = <fun> # add 3 5;; - : int = 8
uncurry performs the reverse transformation.
It transforms a function of type
'a → 'b → 'c
into a function of type
'a * 'b → 'c.
# let uncurry f = fun (x,y) -> f x y;; val uncurry : ('a -> 'b -> 'c) -> 'a * 'b -> 'c = <fun>
Now a more complex (and insightful) example.
We want to define a function
iter that iterates any function
f for n times.
(iter 0 f) x = x
(iter 1 f) x = f x
(iter 2 f) x = f (f x)
# let rec iter n f = fun x -> if n=0 then x else f (iter (n-1) f x);; val iter : int -> ('a -> 'a) -> 'a -> 'a = <fun>
Here is an equivalent definition of
iter, which avoids making the parameter
iter 0 f = id(where
idis the identity function)
iter 1 f = f
iter 2 f = f ° f(where ° denotes function composition)
# let rec iter n f = if n=0 then (fun x -> x) else comp f (iter (n-1) f);; val iter : int -> ('a -> 'a) -> 'a -> 'a = <fun>
Let us exploit bounded iteration to define addition and multiplication, starting from the Peano axioms.
The idea is that x + y = succ succ … succ y, where the successor function
succ is iterated x times.
# let succ = fun x -> x+1;; val succ : int -> int = <fun> # let sum = fun x y -> (iter x succ) y;; val sum : int -> int -> int = <fun> # sum 3 5;; - : int = 8
Multiplication is similar:
to compute the product of x by y, we need to iterate
sum x times,
that is x * y = y + … + y (x times).
# let mul = fun x y -> (iter x (sum y)) 0;; val mul : int -> int -> int = <fun> # mul 3 5;; - : int = 15
In the previous section we have defined a combinator
that allows for bounded iteration:
iter n performs exactly
We now introduce a more general combinator, that allows
for performing a possibly unbounded number of iterations.
The exit condition is given by a boolean predicate
we keep iterating until
p becomes false.
# let rec loop p f x = if p x then x else loop p f (f x);; val loop : ('a -> bool) -> ('a -> 'a) -> 'a -> 'a = <fun>
Let us exploit
loop to define a function that computes
a fixed point (if it exists) of a function
f: float → float.
A fixed point of
f is a value
x such that
f x = x.
Since we are working with floating point numbers, i
t would be unwise to use equality: actually, we just require
f x and
x do not differ more than some given epsilon.
# let fixpoint f eps = loop (fun x -> f x -. eps <= x && x <= f x +. eps) f;; val fixpoint : (float -> float) -> float -> float -> float = <fun> # fixpoint (fun x -> cos x) 1e-6 (-1.);; - : float = 0.739084549575212635
As mentioned above, the
loop combinator is more general than
To show that, we shall now define
iter n in terms of
The exit predicate becomes true when the number of iterations made by the loop equals to
To do that, we massage the iterated function
in order to make it count the number of iterations.
# let iter n f x = fst (loop (fun (x,k) -> k=n) (fun (x,k) -> (f x,k+1)) (x,0));; val iter : int -> ('a -> 'a) -> 'a -> 'a = <fun>