Lecture 8: Functions as Values

Functions Without Names

If functions are to be regarded as computational values, then we need a notation for them. The fun notation expresses a non-recursive function value without giving the function a name.

\tt fun\;x\;\rightarrow E is the function f such that f(x)=E. The function fun n -> n*2 is a doubling function.

# fun n -> n * 2;;
  - : int -> int = <fun>

The main purpose of fun-notation is to package up small expressions that are to be applied repeatedly using some other function. The expression fun n -> n*2 has the same value as the identifier double, declared as follows:

# let double n = n * 2;;
  val double : int -> int = <fun>

The fun notation can also do pattern matching, and the function keyword adds an anonymous variable name to pattern match against. The following functions are all equivalent, with the latter definitions bound to the is_zero value and the earlier ones anonymous:

# fun x -> match x with 0 -> true | _ -> false;;
  - : int -> bool = <fun>

Curried Functions

A curried function returns another function as its result. We use the string concetenation operator (^) to illustrate how this works.

# (^);;
  - : string -> string -> string = <fun>

A short form for the definition of prefix is simply to pass multiple arguments to the function definition. The following two definitions are equivalent in OCaml:

# let prefix = fun a -> fun b -> a ^ b;;
  val prefix : string -> string -> string = <fun>

Currying is the technique of expressing a function taking multiple arguments as nested functions, each taking a single argument. The fun-notation lets us package n*2 as the function fun n -> n * 2, but what if there are several variables, as in fun n -> n * 2 + k? A function of two arguments could be coded using pattern-matching on pairs, writing fun (n, k) -> n * 2 + k.

Currying is an alternative, where we nest the fun-notation:

# fun k -> fun n -> n * 2 + k;;
  - : int -> int -> int = <fun>

Applying this curried function to the argument 1 yields another function, in which k has been replaced by 1:

# let fn = fun k -> fun n -> n * 2 + k;;
  val fn : int -> int -> int = <fun>

And this function, when applied to 3, yields the result 7. The two arguments are supplied one after another.

The example on the slide is similar but refers to the expression a^b, where ^ is the infix operator for string concatenation. Function promote binds the first argument of prefix to "Professor"; the resulting function prefixes that title to any string to which it is applied.

Shorthand for Curried Functions

A function-returning function is just a function of two arguments.

This curried function syntax is nicer than nested fun binders:

# let prefix a b = a ^ b;;
  val prefix : string -> string -> string = <fun>

Curried functions allows partial application (to the first argument).

In OCaml, an n-argument curried function f can be declared using the syntax:

\tt let \; f \; x_1 \: \ldots \: x_{n} \: = \: E

and applied using the syntax:

\tt \; E_1 \; \ldots \; E_n 

If f is not recursive, then it is equivalent to the function expressed via nesting as follows:

\tt fun \; x_1 \; \rightarrow \cdots \rightarrow fun \; x_{n} \rightarrow E 

We now have two ways of expressing functions of multiple arguments: either by passing a pair of arguments or by currying. Currying allows partial application which is useful when fixing the first argument yields a function that is interesting in its own right. An example from mathematics is the function x^y, where fixing y=2 yields a function in x alone, namely squaring. Similarly, y=3 yields cubing, while y=1 yields the identity function.

Though the function hd (which returns the head of a list) is not curried, it may be used with the curried application syntax in some expressions:

# List.hd [dub; promote] "Hamilton";;
  Line 1, characters 9-12:
  Error: Unbound value dub

Here List.hd is applied to a list of functions, and the resulting function dub is then applied to the string "Hamilton". The idea of executing code stored in data structures reaches its full development in object-oriented programming, like in Java.

Partial Application: A Curried Insertion Sort

# let insort lessequal =
    let rec ins x = function
      | [] -> [x]
      | y::ys -> if lessequal x y then x :: y :: ys
                 else y :: ins x ys
    in
    let rec sort = function
      | [] -> []
      | x::xs -> ins x (sort xs)
    in
    sort;;
  val insort : ('a -> 'a -> bool) -> 'a list -> 'a list = <fun>

The sorting functions we discussed in earlier lectures are coded to sort floating-point numbers. They can be generalised to an arbitrary ordered type by passing the ordering predicate lessequal as an argument.

Functions ins and sort are declared locally, referring to lessequal. Though it may not be obvious, insort is a curried function. Given its first argument, a predicate for comparing some particular type of items, it returns the function sort for sorting lists of that type of items.

Some examples of its use:

# insort (<=) [5; 3; 9; 8];;
  - : int list = [3; 5; 8; 9]

An obscure point: the syntax (<=) denotes the comparison operator as a function, which is then given to insort. Passing the relation \geq for lessequal gives a decreasing sort. This is no coding trick; it is justified in mathematics, since if \leq is a partial ordering then so is \geq.

map: the “Apply to All” Function

# let rec map f = function
    | [] -> []
    | x::xs -> (f x) :: map f xs;;
  val map : ('a -> 'b) -> 'a list -> 'b list = <fun>

The functional map applies a function to every element of a list, returning a list of the function’s results. “Apply to all” is a fundamental operation and we shall see several applications of it below. We again see the advantages of fun-notation, currying and map. If we did not have them, the first use of map in the above code block would require a preliminary function declaration:

# let rec sillylist = function
    | [] -> []
    | s::ss -> (s ^ "ppy") :: sillylist ss;;
  val sillylist : string list -> string list = <fun>

An expression containing several applications of functionals---such as our second example---can abbreviate a long series of declarations. Sometimes this coding style is cryptic, but it can be clear as crystal. Treating functions as values lets us capture common program structures once and for all.

In the second example, double is the obvious integer doubling function we defined earlier. Note that \texttt{map} is a built-in OCaml function in the form of List.map. OCaml’s standard library includes, among much else, many list functions.

Example: Matrix Transpose

\begin{pmatrix}
           a   & b & c \\
           d   & e & f
   \end{pmatrix}^T =
   \begin{pmatrix}
        a & d     \\
        b & e     \\
        c & f
\end{pmatrix}

# let rec transp = function
    | []::_ -> []
    | rows -> (map List.hd rows) ::
              (transp (map List.tl rows));;
  val transp : 'a list list -> 'a list list = <fun>

A matrix can be viewed as a list of rows, each row a list of matrix elements. This representation is not especially efficient compared with the conventional one (using arrays). Lists of lists turn up often, though, and we can see how to deal with them by taking familiar matrix operations as examples. ML for the Working Programmer goes as far as Gaussian elimination, which presents surprisingly few difficulties.

The transpose of the matrix

\left(\begin{smallmatrix} a & b & c \\
                           d & e & f\end{smallmatrix}\right)

is

\left(\begin{smallmatrix}
        a & d     \\
        b & e     \\
        c & f
   \end{smallmatrix}\right)

which in OCaml corresponds to the following transformation on lists of lists:

\begin{aligned}
\text{[[a; b; c]; [d; e; f]]} \Rightarrow& \text{ [[a; d]; [b; e]; [c; f]]}
\end{aligned}

The workings of function transp are simple. If rows is the matrix to be transposed, then map hd extracts its first column and map tl extracts its second column:

\begin{aligned}
\text{map hd rows} \Rightarrow & \text{ [a; d]}\\
\text{map tl rows} \Rightarrow & \text{ [[b; c]; [e; f]]}
\end{aligned}

A recursive call transposes the latter matrix, which is then given the column [a; d] as its first row. The two functions expressed using map would otherwise have to be declared separately.

Review of Matrix Multiplication

\begin{pmatrix} A_1 & \cdots & A_k \end{pmatrix}  \cdot
   \begin{pmatrix}
        B_1 \\ \vdots \\ B_k
   \end{pmatrix}   =
   \begin{pmatrix}
        A_1 B_1 + \cdots + A_k B_k
   \end{pmatrix}

The right side is the vector dot product \vec\{A\}\cdot \vec\{B\}. Repeat for each row of A and column of B.

The dot product of two vectors is

(a_1,\ldots,a_k) \cdot (b_1,\ldots,b_k) = a_1b_1 + \cdots + a_kb_k 

A simple case of matrix multiplication is when A consists of a single row and B consists of a single column. Provided A and B contain the same number k of elements, multiplying them yields a 1\times1 matrix whose single element is the dot product shown above.

If A is an m\times k matrix and B is a k\times n matrix then A\times B is an m\times n matrix. For each i and j, the (i,j) element of A\times B is the dot product of row i of A with column j of B.

\begin{pmatrix}
        2 & 0 \\
        3 &-1 \\
        0 & 1 \\
        1 & 1
   \end{pmatrix}
   \begin{pmatrix}
        1 & 0 & 2 \\
        4 &-1 & 0
   \end{pmatrix}   =
   \begin{pmatrix}
        2 & 0 & 4 \\
       -1 & 1 & 6 \\
        4 &-1 & 0 \\
        5 &-1 & 2
\end{pmatrix}

The (1, 1) element above is computed by

(2,0)\cdot(1,4) = 2\times1 + 0\times4 = 2. 

Coding matrix multiplication in a conventional programming language usually involves three nested loops. It is hard to avoid mistakes in the subscripting, which often runs slowly due to redundant internal calculations.

Matrix Multiplication in OCaml

Dot product of two vectors---a curried function

# let rec dotprod xs ys =
    match xs, ys with
    | [], [] -> 0.0
    | x::xs, y::ys ->  (x *. y) +. (dotprod xs ys);;
  Lines 2-4, characters 4-50:
  Warning 8 [partial-match]: this pattern-matching is not exhaustive.
  Here is an example of a case that is not matched:
  ([], _::_)
  val dotprod : float list -> float list -> float = <fun>

Matrix product

# let rec matprod arows brows =
    let cols = transp brows in
    map (fun row -> map (dotprod row) cols) arows;;
  val matprod : float list list -> float list list -> float list list = <fun>

The transp brows converts B into a list of columns, yielding a list whose elements are the columns of B. Each row of A\times B is obtained by multiplying a row of A by the columns of B.

Because dotprod is curried, it can be applied to a row of A. The resulting function is applied to all the columns of B. We have another example of currying and partial application.

The outer map applies dotprod to each row of A. The inner map, using fun-notation, applies dotprod row to each column of B. Compare with the version in ML for the Working Programmer (page 89) which does not use map and requires two additional function declarations.

In the dot product function, the two vectors must have the same length. Otherwise, exception Match_failure is raised.

List Functionals for Predicates

# let rec exists p = function
  | [] -> false
  | x::xs -> (p x) || (exists p xs);;
  val exists : ('a -> bool) -> 'a list -> bool = <fun>

A predicate is a boolean-valued function.

The functional exists transforms a predicate into a predicate over lists. Given a list, exists p tests whether or not some list element satisfies p (making it return true). If it finds one, it stops searching immediately, thanks to the behaviour of the lazy || operator.

Dually, we have a functional to test whether all list elements satisfy the predicate. If it finds a counterexample then it, too, stops searching.

# let rec all p = function
  | [] -> true
  | x::xs -> (p x) && all p xs;;
  val all : ('a -> bool) -> 'a list -> bool = <fun>

The filter functional, like map, transforms lists. It applies a predicate to all the list elements, but instead of returning the resulting values (which could only be true or false), it returns the list of elements satisfying the predicate.

Applications of the Predicate Functionals

# let member y xs =
    exists (fun x -> x=y) xs;;
  val member : 'a -> 'a list -> bool = <fun>

Testing whether two lists have no common elements

# let disjoint xs ys =
    all (fun x -> all (fun y -> x<>y) ys) xs;;
  val disjoint : 'a list -> 'a list -> bool = <fun>

The Lists lecture presented the function member, which tests whether a specified value can be found as a list element, and inter, which returns the “intersection” of two lists: the list of elements they have in common.

But remember: the purpose of list functionals is not to replace the declarations of popular functions, which probably are available already. It is to eliminate the need for separate declarations of ad-hoc functions. When they are nested, like the calls to \texttt{all} in \texttt{disjoint} above, the inner functions are almost certainly one-offs, not worth declaring separately.

Our primitives themselves can be seen as a programming language. Part of the task of programming is to extend our programming language with notation for solving the problem at hand. The levels of notation that we define should correspond to natural levels of abstraction in the problem domain.

Historical Note: Alonzo Church’s \lambda-calculus gave a simple syntax, \lambda-notation, for expressing functions. It is the direct precursor of OCaml’s fun-notation. It was soon shown that his system was equivalent in computational power to Turing machines, and Church’s thesis states that this defines precisely the set of functions that can be computed effectively.

The \lambda-calculus had a tremendous influence on the design of functional programming languages. McCarthy’s Lisp was something of a false start; it interpreted variable binding incorrectly, an error that stood for some 20 years. But in 1966, Peter Landin (of Queen Mary College, University of London) sketched out the main features of functional languages.

# let sw f x y = f y x;;
  val sw : ('a -> 'b -> 'c) -> 'b -> 'a -> 'c = <fun>

(x',y')<(x,y)\iff x'<x \vee (x'=x \wedge y'<y).

# type 'a option = None | Some of 'a;;
  type 'a option = None | Some of 'a

# let rec change till amt =
    match till, amt with
    | _       , 0   -> [ [] ]
    | []      , _   -> []
    | c::till , amt -> if amt < c then change till amt
                      else let rec allc = function
                             | [] -> []
                             | cs :: css -> (c::cs) :: allc css
                           in
                             allc (change (c::till) (amt - c)) @
                                   change till amt;;
  val change : int list -> int -> int list list = <fun>