hof

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>

hof.txt · Last modified: 2015/10/08 15:20 (external edit)