User Tools

Site Tools


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


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

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