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>

LIP assignment #3