Chapter 4
Fun with Higher-Order Functions
Computer science is the science of abstraction creating the right model for a problem and devising the appropriate mechanizable technique to solve it. A. Aho, J. Ullman
In this chapter, we cover a very powerful programming paradigm: Higher-order functions. Higher-order functions are one of the most important mechanisms in the development of modular, well-structured, and reusable programs. They allow us to write very short and compact programs, by abstracting over common functionality. This principle of abstraction is in fact a very important software engineering princi- ple. Each significant piece of functionality in a program should be implemented in just one place in the source code. Where similar functions are carried out by distinct pieces of code, it is generally beneficial to combine them into one by abstracting out the varying part. The use of higher-order functions allows you to easily abstract out varying parts.
Since abstracting over varying parts to allow code reuse is such an important prin- ciple in programming, many languages support it in various disguises. Recently, the concept of higher-order functions has received particular attention since it features prominently in Googles MapReduce framework for distributed computing and in the Hadoop project, an open-source implementation to support large-scale data process- ing which is used widely. These frameworks are used to process 20 to 30 petabytes of data a day and simplify data processing on large clusters. Although mostly written in C++, the philosophy behind MapReduce and Hadoop is functional:
Our abstraction is inspired by the map and reduce primitives present in Lisp and many other functional languages.
-Jeffrey Dean and Sanjay Ghemawat
41 c B. Pientka Fall 2020
1 2 3
1 2 3 4
1 2 3 4
All these functions look very similar, and the code is almost the same. But obvi- ously, the sum depends on what function we are summing over! It is natural to ask, if we can write a generic sum function where we only give a lower bound a, and upper bound b, and a function f which describes what needs to be done in each iteration. The answer is, YES, we can! Here is how it works:
Chapter 4: Higher-Order Functions 4.1 Passing Functions
Higher-order functions also play an important role in code generation, i.e. pro- grams which generate other programs. Later on in the course, we will discover that higher-order functions also are key to understanding lazy computation and handling infinite data. Finally, we will see that they allow us to model closures and objects as you know them in object-oriented programming.
4.1 Passing Functions as Arguments
Functions form the powerful building blocks that allow developers to break code down into simple, more easily managed steps, as well as let programmers break programs into reusable parts. As we have seen early on in the course, functions are values, just as numbers and booleans are values.
But if they are values, can we write functions which take other functions as ar-
guments? In other words, can we write a function f:int * (int -> int) -> int? Would
this be useful? The answer is YES! It is in fact extremely useful!
Xk=b k=a
Consider the following implementation of the function which computes
1 let rec sumInts (a,b) = if (a > b) then 0 else a + sumInts(a+1,b)
k.
k=b k=b k=b Similarly, we can compute the function X k2 or X k3 or X 2k
k=a k=a k=a
let rec sumSquare(a,b) = if (a > b) then 0 else square(a) + sumSquare(a+1,b) let rec sumCubes (a,b) = if (a > b) then 0 else cubes(a) + sumCubes(a+1,b) let rec sumExp (a,b) = if (a > b) then 0 else exp(2, a) + sumExp(a+1, b)
(* sum: (int -> int) -> int * int -> int *)
let rec sum f (a,b) =
if (a > b) then 0
else (f a) + sum(f,a+1,b)
We can then easily obtain the previous functions as follows:
42 c B. Pientka Fall 2020
let rec sumInts (a,b) = sum (fun x -> x)
let rec sumCubes (a,b) = sum cube
let rec sumSquare(a,b) = sum square
let rec sumExp (a,b) = sum (fun x -> exp(2,x)) (a, b)
(a, b) (a, b) (a, b)
1 2 3 4 5 6 7 8 9
10 11 12
1 2 3
1 2 3 4 5 6 7
This seems to suggest we can generalize the previous sum function and abstract over the increment function.
Chapter 4: Higher-Order Functions 4.1 Passing Functions
Note that we can create our own functions using fun x -> e, where e is the body of the function and x is the input argument, and pass them as arguments to the function sum. Or we can pass the name of a previously defined function like square to the function sum. In general, this means we can pass functions as arguments to other functions.
What about if we want to sum up all the odd numbers between a and b?
(* sumOdd: int -> int -> int *)
let rec sumOdd (a, b) = let rec sum (a,b) =
if a > b then 0
else a + sum(a+2, b) in
if (a mod 2) = 1 then (* a was odd *) sum(a,b)
else
(* a was even *)
sum(a+1, b)
let rec sum f (a, b) inc =
if (a > b) then 0
else (f a) + sum f (inc(a),b) inc
Isnt writing products instead of sums similar? The answer is also YES. Consider computing the product of a function f(k) for k between a and b.
(* product : (int -> int) -> int * int -> (int -> int) -> int *)
let rec product f (lo,hi) inc =
if (lo > hi) then 1
else (f lo) * product f (inc(lo),hi) inc
(* Using product to define factorial. *)
let rec fact n = product (fun x -> x) (1, n) (fun x -> x + 1)
The main difference is two-folded: First, we need to multiply the results, and second we need to return 1 as a result in the base case, instead of 0.
So how could we abstract over addition and multiplication and generalize the function further? We could define such a function series? Our goal is to write this function tail-recursively and we use an accumulator {acc:int} in addition to a function f:int -> int, a lower bound a:int, an upper bound b:int, increment function inc:int -> int. We also need parameterize the function series with a function comb:int
-> int -> int to combine the results. By instantiating comb with addition (i.e. (fun x y
-> x + y)) we obtain the function sum and by instantiating it with multiplication (i.e. (fun x y -> x * y)) we obtain the function prod.
43 c B. Pientka Fall 2020
Chapter 4: Higher-Order Functions
4.1 Passing Functions
(* series:
->
*)
let rec series comb f (a,b) inc acc = let rec series (a, acc) =
if (a > b) then acc
else
series (inc(a), comb acc (f a))
in
letrecsumSeries f(a,b)inc=series(funxy->x+y)f(a,b)inc0 let rec prodSeries f (a,b) inc = series (fun x y -> x * y) f (a, b) inc 1
series(lo, r)
(combiner ( f ((a,b)
( inc
( acc
( result
: int -> int -> int) -> :int->int)-> :int*int)->
: int -> int) ->
: int) : int)
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17
Ok, we will stop here. Abstraction and higher-order functions are very powerful mechanisms in writing reusable programs.
4.1.1 Example 1: Integral
Let us consider here one familiar problem, namely approximating an integral (see Fig. 4.1). The integral of a function f(x) is the area between the curve y = f(x) and the x-axis in the interval [a, b]. We can use the rectangle method to approximate the integral of f(x) in the interval[a, b], made by summing up a series of small rectangles using midpoint approximation.
dx
f(a+(dx/2)
a
b
a+(dx/2)
Figure 4.1: Integral between a and b
44 c B. Pientka Fall 2020
Chapter 4: Higher-Order Functions 4.1 Passing Functions
To approximate the area between a and b, we compute the sum of rectangles, where the width of the rectangle is dx. The height is determined by the value of the function f. For example, the area of the first rectangle is dx f(a + (dx/2)).
Then we can approximate the area between a and b by the following series, where l = a + (dx)/2 is our starting point.
Rabf(x)dx f(l)dx+f(l+dx)dx+f(l+dx+dx)dx+
= dx (f(l) + f(l + dx) + f(l + 2 dx) + f(l + 3 dx) . . .)
Assuming we have an iterative sum function iter_sum for reals, we can now com- pute the approximation of an integral as follows:
1 2
1 2
1 2 3
let rec integral f (a,b) dx =
dx *. iter_sum f (a +. (dx /. 2.0) , b) (fun x -> x +. dx)
This is very short and elegant, and directly matches our mathematical theory. Alternatively, we could directly sum up over the area without factoring out dx. In other words, we could directly implement the definition
Rabf(x)dx f(l)dx+f(l+dx)dx+f(l+dx+dx)dx+ as follows:
let rec integral f (a,b) dx =
iter_sum (fun x -> f x *. dx) (a +. dx /. 2.0, b) (fun x -> x +. dx)
4.1.2 Example 2: Half interval method
The half-interval method is a simple but powerful technique for finding roots of an equation f(x) = 0, where f is a continuous function. The idea is that, if we are given points a and b such that f(a) < 0 < f(b), then f must have at least one zero between a and b. To locate a zero, let x be the average of a and b and compute f(x). If f(x)>0,thenfmusthaveazerobetweenaandx. Iff(x)<0,thenfmusthavea zero between x and b. Continuing in this way, we can identify smaller and smaller intervals on which f must have a zero. When we reach a point where the interval is small enough, the process stops. Since the interval of uncertainty is reduced by half at each step of the process, the number of steps required grows as (log(l/t)), where l is the length of the original interval and t is the error tolerance (that is, the size of the interval we will consider small enough). Here is a procedure that implements this strategy: let rec halfint (f:float -> float) (a, b) t = letmid=(a+.b)/.2.0 in
if abs_float (f mid) < t then mid45 c B. Pientka Fall 2020Chapter 4: Higher-Order Functions 4.1 Passing Functions4 5 6 71 2 3 41 add(1, add(2, add(3, add(4, ? ) ) ) )To stop the successive application of the function we also need a base. In our case where we add all the elements, the initial element would be 0 (i.e. we replace ? with 0).We can observe that cumulatively applying a given function to all elements in a list is useful for many situations: we might want to create a string 1234 from the given list (where the initial element would be the empty string), or we might want to multiply all elements (where the initial element would be 1), etc.We also observe that we sometimes want to gather all the results in the reverse order. While the former function is often referred to as fold-right the latter one is often described as fold-left.1 add4(add3(add2(add10)))Implementing a function fold_right which folds elements from right to left is elseif (f mid) < 0.0then halfint f (mid, b) t else halfint f (a, mid) t4.1.3 Combining Higher-order Functions with Recursive Data-TypesWe can also combine higher-order functions with recursive data-types. One of the most common uses of higher-order functions is the following: We want to apply a function f to all elements of a list. (* map: (a -> b) -> a list -> b list *)
let rec map f l = match l with |[] ->[]
| h::t -> (f h)::(map f t)
This is the first part in the MapReduce framework. What is second part Reduce referring to? It is referring to another popular higher-order function, often called fold in functional programming. Essentially fold applies a function f over a list of el- ements and produces a single result by combining all elements using f. For example, lets say we have a list of integers [1;2;3;4] and we want to add all of them. Then we essentially want to use a function add which cumulatively is applied to all elements in the list and adds up all the elements resulting in
straightforward.
1 2 3 4
(*fold_right (a->b->b)->alist->b->b*) (* fold_right f [x1; x2; ; xn] init
returns
46 c B. Pientka Fall 2020
5 6 7 8 9
10 11
1 2 3 4 5 6
Finally, we revisit another popular higher-order function, called filter. This func- tion can be used to filter out all the elements in a list which fulfill a certain predicate p:a -> bool.
Chapter 4: Higher-Order Functions
4.2 Returning Functions
f x1 (f x2 (f xn init))
or init if the list is empty. *)
let rec fold_right f l b = match l with |[] ->b
| h::t -> f h (fold_right f t b)
(* filter: (a -> bool) -> a list -> a list *)
let rec filter (p : a -> bool) l = match l with |[] ->[]
| x::l ->
if p x then x::filter p l else filter p l
You will find many similar functions already defined in the OCaml basis library.
4.2 Returning Functions as Results
In this section, we focus on returning functions as results. We will first show some simple examples demonstrating how we can transform functions into other functions. This means that higher-order functions may act as function generators, because they allow functions to be returned as the result from other functions.
Functions are very powerful. In fact, using a calculus of functions, the lambda- calculus, we can cleanly define what a computable function is. The lambda calculus is universal in the sense that any computable function can be expressed and evaluated using this formalism. It is thus equivalent to the Turing machine formalism and was originally conceived by Alonzo Church (1903-1995).
The question of whether two lambda calculus expressions are equivalent cannot be solved by a general algorithm, and this was the first question, even before the halting problem, for which undecidability could be proved. The lambda calculus is also the foundation for many programming languages in particular functional pro- gramming.
4.2.1 Example 1: Currying and uncurrying
Currying has its origin in the mathematical study of functions. It was observed by Frege in 1893 that it suffices to restrict attention to functions of a single argument.
47 c B. Pientka Fall 2020
Chapter 4: Higher-Order Functions 4.2 Returning Functions
For example, for any two parameter function f(x, y), there is a one parameter func- tion f such that f0(x) is a function that can be applied to y to give (f0(x))(y) = f(x, y). This idea can be easily implemented using higher-order functions. We will show how we can translate a function f : a * b -> c which expects a tuple x:a * b into a function f : a -> b -> c to which we can pass first the argument of type a and then the second argument of type b. The technique was named by Christopher Strachey (1916 1975) after logician Haskell Curry (1900-1982), and in fact any function can
be curried or uncurried (the reverse process).
In general, we call currying the transformation of a function which takes multiple
arguments in form of a tuple in such a way that it can be called as a chain of functions each with a single argument
1 2 3 4 5
(* curry : ((a * b) -> c) -> (a -> b -> c) *)
let curry f = (fun x y -> f (x,y))
(* uncurry: (a -> b -> c) -> ((a * b) -> c) *)
let uncurry f = (fun (y,x) -> f y x)
We say that f: a -> b -> c is the curried form of f: a * b -> c. To create func- tions we use the nameless function definition fun x -> e where x is the input and e denotes the body of the function.
A word about parenthesis and associativity of function types Given a func- tion type a -> b -> c, this is equivalent to a -> (b -> c); function types are right- associative. This in fact corresponds to how we use a function f of type a -> b -> c. Writing f arg1 arg2 is equivalent to writing (f arg1) arg2; function application is left- associative.
Lets look at why this duality between the function type and function application makes sense; f has type a -> b -> c and arg1 has type a. Therefore f arg1 must have type b -> c. Moreover, applying arg2 to the function f arg1, will return a result of type c.
(farg1)arg2:0 c | {z }
b -> c
Some more examples of higher-order functions
function definitions are equivalent:
let id = fun x -> x (* OR *)
let id x = x
1 2 3 4 5
Recall that the following two
c B. Pientka Fall 2020
48
1 2
Chapter 4: Higher-Order Functions 4.2 Returning Functions
Another silly function we can write is a function which swaps its arguments.
(* swap : (a * b -> c) -> (b * a -> c) *)
let swap f = (fun (x,y) -> f (y,x))
4.2.2 Example 2: Derivative
A bit more interesting is to implement the derivative of a function f. The derivative of a function f can be computed as follows:
df =limf(x+)-f(x)
dx!0
We can approximate the result of the derivative by choosing to be some small number. Then given a function f:float -> float and a small number dx, we can com- pute a function f which describes the derivative of f.
1 letderiv(f,dx)=funx->(f(x+.dx)-.fx)/.dx
4.2.3 Example 3: Smoothing
The idea of smoothing a function is an important concept in signal processing. If f is a function and dx is some small number, then the smoothed version of f is the function whose value at a point x is the average of f(x dx), f(x), and f(x + dx). The function smooth takes as input f and a small number dx and returns a function that computes the smoothed f.
1 let smooth(f,dx) = fun x -> (f(x -. dx)+. f(x) +. f(x+dx)) /. 3.0
It is sometimes valuable to repeatedly smooth a function (that is, smooth the
smoothed function, and so on) to obtained the n-fold smoothed function.
4.2.4 Example 4: Partial evaluation and staged computation
An important application of higher-order functions and the ability to return functions lies in partial evaluation, staged computation and code generation.
Partial evaluation is best illustrated by considering an example. For example, given the following generic function,
1 2
(* funkyPlus : int -> int -> int *)
let funkyPlus x y = x * x + y
we can first pass it 3. This generates a function fun y -> 3 * 3 + y which is partially evaluated. So, we have generated a function which will increment its input by 9.
49 c B. Pientka Fall 2020
Chapter 4: Higher-Order Functions 4.2 Returning Functions
1 2
(* plus9 : int -> int *)
let plus9 = funkyPlus
We only partially evaluate the funkyPlus function by passing only one of the argu- ments to it. This yields again a function! We can see that templates, which occur in many programming languages are in fact nothing more than higher-order functions. Note that you cannot actually see what the new function plus9 looks like. Func- tions are first-class values, and the OCaml interpreter (as any other interpreter for languages supporting functions) never prints functions back to your screen. It will simply return to you the type.
Nevertheless, given our understanding of the underlying operational semantics, we can try to understand what happens when we execute funkyPlus 3.
funkyPlus 3 = (fun x -> fun y -> x * x + y) 3 =) fun y -> 3 * 3 + y
To evaluate the application (fun x -> fun y -> x * x + y) 3, we substitute 3 for x in the body of the function, i.e. fun y -> x * x + y. This results in the expression fun y ->
3 * 3 + y.
Note, the result is not fun y -> 9 + y. We never evaluate inside the function body.
This is important because in effect this will allow us to deliberately delay the evalua- tion of some expression.
How would we generate a function which fixes y, but awaits still the input x? 1 let plus3 = (fun x -> funkyPlus x 3)
The idea of partial evaluation is quite powerful to achieve code which can be configured during run-time and code which can achieve considerable efficiency gain, especially if we stage our computation properly.
Staged computation refers to explicit or implicit division of a task into stages. It is a standard technique from algorithm design that has found its way to programming languages and environments. Examples are partial evaluation which refers to the global specialization of a program based on a division of the input into static (early) and dynamic (late) data, and run-time code generation which refers to the dynamic generation of optimized code based on run-time values of inputs.
At the heart of staged computation lies the goal to force evaluation of some part of the program before continuing with another part. For example, let us reconsider the result of (funkyPlus 3) which was fun y -> 3 * 3 + y. How could we force the evaluation of 3*3 so we actually produce a function fun y -> 9 + y. We will re-write the funkyPlus function as follows:
1 letfunkyx=letr=x*xinfuny->r+y
Now the evaluation of funky 3 will proceed as follows:
50 c B. Pientka Fall 2020
Chapter 4: Higher-Order Functions 4.2 Returning Functions
funky 3 = fun x -> let r = x * x in (fun y -> r + y) 3 =) let r = 3 * 3 in fun y -> r + y
=) let r = 9 in fun y -> r + y
=) fun y -> 9 + y
By introducing a let-expression before creating the second function which is wait- ing for the second input, we have pulled out the essential part of the code and will evaluate it before returning the function fun y -> 9 + y as a result.
In this example of funkyPlus, staging did not have a great impact on the execution and run-time behavior of our function. However, there are many examples where it can be more efficient to write staged code.
Consider we have first defined a horrible computation:
(* val horriblecomputation : int -> int *)
let rec horriblecomputation x =
let rec ackermann m n = match (m , n) with
|0,n-> n+1
| m , 0 -> ackermann (m-1) 1
| m , n -> ackermann (m-1) (ackermann m (n-1)) in
let y = (abs x) mod 3 + 2 in let rec count n = match n with
| 0 -> ackermann y 4
| n -> count(n-1) + 0 * ackermann y 4 in let large = 1000 in
(ackermann y 1) * (ackermann y 2) * (ackermann y 3) * count large
1 2 3 4 5 6 7 8 9
10 11 12
1
1 2 3 4
Executing the horrible computation will take a very long time (you can try!). Next, lets say we have two columns of test values and we are supposed to write a function test which takes the value v1 from the first column and a value v2 from the second column and computes
horribleComputation(v1) + v2
This is how the two columns look like. Column 1 Column 2
10 5 22
18
22
So, we define a function test as follows:
51 c B. Pientka Fall 2020
(* val test : int * int -> int *)
let test (x:int, y:int) =
let z = horriblecomputation x in
z+y
Chapter 4: Higher-Order Functions 4.2 Returning Functions
If we execute test on a few instantiations, where the first instantiation for x does not change, then we have to execute this horrible computation each time.
1 2 3 4 5 6 7 8 9
10
1 map (fun y -> test (10, y)) [1; 2; . ; 100]
we will compute the horribleComputation 10 exactly 100 times! This will take 500h. Thats a long time.
let result11 = test(10, 5); let result12 = test(10, 2); let result13 = test(10, 18); let result14 = test(10, 22);
let result21 = test(2, 5); let result22 = test(2, 2); let result23 = test(2, 18); let result24 = test(2, 22);
What will happen? Lets put this in a concrete perspective and assume com- puting horribleComputation(10) takes 5h. Then computing the results result11, result12, result13, and result14 will take 20h! If we give it a list of 100 inputs, as follows
1 2 3 4
Would it help to write a curried version?
We can then write the following code:
(* val test : int -> int -> int *)
let test (x:int) (y:int) =
let z = horriblecomputation x in
z+y
1 map (test 10) [1; 2; 3; ; 100]
Isnt this better? Well, lets see. The function test is equivalent to the following
:
1 2
1 test 10 =)
2 fun y -> let z = horriblecomputation 10 in z + y
We have achieved nothing, since the horrible computation is hidden within a func- tion, and we never evaluate inside functions! Functions are values, hence evaluation will stop as soon as it has computed a function as a result. As a consequence we still will compute the horrible computation every time we call the function test10. But this is exactly what we wanted to avoid!
How can we generate a function which will only compute the horrible computa- tion once and capture this result so we can re-use it for different inputs of y? The
52 c B. Pientka Fall 2020
let test =
fun x -> fun y -> let z = horriblecomputation x in z + y
Computing test 10 will simply replace x with 10 in the body of the function. Ac- cording to our operational semantics, test 10 will evaluate to
Chapter 4: Higher-Order Functions 4.2 Returning Functions
idea is that we need to factor out the horrible computation. When given an input x, we compute the horrible computation yielding z, and then create a function which awaits still the input y and adds y and z.
1 2 3 4
let testCorrect (x:int) =
let z = horriblecomputation x in (fun y -> z + y)
let r = map (testCorrect 10) [1;2;3; ; 100]
Note, we now compute the horrible computation once, when executing testCorrect 10 and created a closure which stores its result. Generating testCorrectly10 will take 5h. But, when we use testCorrectly10, we will be avoiding the recomputation of the
horrible computation, and it will be able to compute the results very quickly.
To understand the impact of partial evaluation, it is key to understand how func- tions are evaluated. Try to figure out how often horribleComputation(10) gets executed
in the following examples:
1. map (curry test 10) [1; 2; ; 100]
2. map(funx->test10x)[1;2; ..;100]
This idea of staging computation is based on the observation that a partial evalu- ator can convert a two-input program into a staged program that accepts one input and produces another program that accepts the other input and calculates the final answer. The point being that the first stage may be run ahead of time (e.g. at compile time) while the second specialized stage should run faster than the original program. Many current compilers for functional programming employ partial evaluation and staged computation techniques to generate efficient code. It is worth pointing out that to understand this optimization, we really need to understand the operational semantics of how programs are executed.
4.2.5 Example 5: Code generation
Let us consider again the following simple program to compute the exponent.
(* pow k n = n^k *)
let rec pow k n = if k = 0 then 1 else n * pow (k-1) n
1 2 3
1 funn->n*pow1n
While we wrote this program in curried form, when we partially evaluate it with k = 2 we will not have generated a function square. What we get back is the following:
53 c B. Pientka Fall 2020
Chapter 4: Higher-Order Functions 4.2 Returning Functions
The recursive call of pow is shielded by the function abstraction (closure). One
interesting question is how we can write a version of this power function which will
act as a generator. When given 2 it will produce the function square, when given
3 it produce the function cube, etc. So more generally, when given an integer k it
will produce a function which computes n . . . n 1. This result should in the end | {z }
k
be completely independent of the original pow definition.
The simplest solution, is to factor out the recursive call before we build the clo-
sure.
1 2
1
This allows us to compute a power generation function. To illustrate, let us briefly consider what happens when we execute powG 2. Let us first start with powG 1
powG 1
) letc=powG0in(funn->n*cn)
) letc=(funn0->1)in(funn->n*cn)
) funn->n*(funn0->1)n
powG 2
) letc=powG1in(funn2->n2*cn2)
) letc=(funn1->n1*(funn0->1) n1) in (funn2->n2*c n2) ) (funn2->n2*(funn1->n1*(funn0->1)n1)n2)
Is this final result really the square function? Yes, it is. Intuitively, this function is equivalent to
fun n2 -> n2 * n2 * 1
Although OCaml will not evaluate any applications inside functions, conceptually, we can see that the result is equivalent to fun n2 -> n2 * n2 * 1 by looking inside the function and reducing the applications.
(funn2->n2* (funn1->n1*(funn0->1) n1) n2 ) reducesto funn2->n2*n2* (funn0->1) n2)
reducesto funn2->n2*n2*1
So yes, we will have generated a version of the square function. Note that lan-
guages supporting templates or macros work in a very similar way and higher-order functions are one way of explaining such concepts.
54 c B. Pientka Fall 2020
let rec powGen k cont = if k = 0 then cont else powGen (k-1) (fun n -> n * (cont n))
Reviews
There are no reviews yet.