hof

# Higher-order functions and polymorphism

## Higher-order functions

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.

## Polymorphism

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>```

## Currying and uncurrying

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>

val add : int -> int -> int = <fun>

- : 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>

- : int = 8```

## Bounded iterators

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```

## Unbounded iterators

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>```

## Exercises 