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:
# let sumc x y = x+y;; val sumc : int -> int -> int = <fun>
The type operator →
associates to the right.
So, the correct parenthesization of the type int → int → int
is int → (int → int)
.
Therefore, 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 f
)
and two integers (the parameters a
and b
),
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 y
to f(y) + y
.
We can do this in several ways. First, the “official” definition:
# let h = fun f -> fun y -> (f y) + y ;; val h : (int -> int) -> int -> int = <fun>
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:
# let h' f = fun y -> (f y) + y ;; val h'' : (int -> int) -> int -> int = <fun>
Using the syntactic sugar twice, we obtain:
# let h'' f y = (f y) + y;; val h'' : (int -> int) -> int -> int = <fun>
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!
The type '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 a
.
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.
The function 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 |f|
:
# let abs f = fun x -> if f x < 0 then -(f x) else f x;; val abs : ('a -> int) -> 'a -> int = <fun>
The type of abs
says that, for all types a
, abs
takes as input a function from a
to int
, and it returns a function from
a
to int
.
Let us apply abs
to the function that maps each x to x.
# let f' = abs (fun x -> x);; val f' : int -> int = <fun> # f' (-3);; - : int = 3
The function comp
takes as input two functions and returns their composition.
To compose f
with g
, the codomain of g
must coincide with the domain of f
.
This is what the type of comp
says:
the type of g
is 'c → 'a
, while the type of f
is '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 abs
.
# let abs = comp (fun x -> if x<0 then -x else x);; val abs : ('a -> int) -> 'a -> int = <fun>
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).
The functions 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
The function 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>
# let addpair = uncurry (+);; val addpair : int * int -> int = <fun> # addpair (3,5);; - : int = 8
Now a more complex (and insightful) example.
We want to define a function iter
that iterates any function f
for n times.
For instance:
(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 x
explicit.
For instance:
iter 0 f = id
(where id
is 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:
indeed, iter n
performs exactly n
iterarions.
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 p
:
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
that 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 iter
.
To show that, we shall now define iter n
in terms of loop
.
The exit predicate becomes true when the number of iterations made by the loop equals to n
.
To do that, we massage the iterated function f
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>