A higher order function (HOF) is a function that does one or both of the following:
Before we jump in, let's have a quick refresher.
You should already be very familiar with defining functions like this:
(define (f x) (plus1 x))
In this function definition, the parameter of
x, which is fed into the body as an argument to the built-in procedure
plus1. If we bring back our substitution model from Lesson 1, we can say that a call to
(f 5), would be evaluated with the following steps:
-> (f 5) -> (plus1 5) 6
5 is substituted into the body of
f and we call
5 to get
6. Alright, that was too easy. But what if, instead of using
x as an argument to the function in the body, we use it as the function?
Let's look at an example.
(define (f g) (g 2))
Do you see how
g is in front? Hmm. What happens if we call
(f 5) this time?
-> (f 5) -> (5 2) ; application: not a procedure; ; expected a procedure that can be applied to arguments ; given: 5 ; [,bt for context]
Whoops. Looks like we need to feed
f a procedure instead.
-> (f square) -> (square 2) 4
We could also feed
f a lambda function!
-> (f (lambda (x) (* x x))) -> ((lambda (x) (* x x)) 2) -> (* 2 2) -> 4
Would you look at that! We just defined a function,
f, that takes a procedure,
g, as its argument and applies
2. There it is, your first higher order function. Play around and see if you can define your own procedures that take other procedures as arguments.
Now that we've seen how functions can be passed around, let's actually explore how this can be useful.
Consider the following three functions:
(define (sum-doubles a b) (if (> a b) 0 (+ (* 2 a) (sum-doubles (+ a 1) b)))) (define (sum-squares a b) (if (> a b) 0 (+ (square a) (sum-squares (+ a 1) b)))) (define (sum-cubes a b) (if (> a b) 0 (+ (cube a) (sum-cubes (+ a 1) b))))
These three functions compute the sum of the doubles, squares, and cubes of all integers between a and b, respectively.
(sum-squares 5 8) computes 52 + 62 + 72 + 82.
Defining all three of these functions seems a bit redundant. Do you see how these three functions are nearly identical in definition, except for the underlined portions of the code? It's time to build some abstraction.
We know that for each of the three functions, we apply some operation to every element between
b. So instead of having a specific function for each operation, let's abstract it away and put it in the function parameters!
So instead of having a specialized
sum-[op] function for every possible operator, we'll just have a general function called
(define (sum fn a b) (if (> a b) 0 (+ (fn a) (sum fn (+ a 1) b))))
We've underlined the major differences in the code above. In this definition of
sum, we apply some input function
fn to each number between
b, as you can see in the recursive call.
Now, we can do this:
(sum (lambda (x) (* 2 x)) 5 8)
(sum square 5 8)
and this too:
(sum cube 5 8)
Having only written one procedure,
sum, we get the functionality of all three procedures above. What a deal!
If you like, the initial three procedures can be redefined using
sum as follows:
(define (sum-squares a b) (sum square a b)) (define (sum-cubes a b) (sum cube a b)) (define (sum-doubles a b) (sum (lambda (x) (* 2 x)) a b))
In your homework, we will take the abstraction of
sum even further with an extremely useful and well-known HOF called
accumulate. Make sure you understand how
accumulate works, as you will need it in future exercises!