In this section, I'll give an extended example of the use of higher-order functions to express patterns common to many functions, and allow those patterns to be customized by passing procedure arguments. Consider the following function to sum the elements of a list @example @group (define (list-sum lis) (if (null? lis) 0 (+ (car lis) (list-sum (cdr lis))))) @end group @end example Given this definition, @example (list-sum '(10 15 20 25)) @end example is equivalent to @example (+ 10 (+ 15 (+ 20 (+ 25 0)))). @end example Now consider a very similar function to multiply the elements of a list, where we've adopted the convention that the product of a null list is 1. (1 is probably the right value to use, because if you multiply something by 1 you get back the same thing---just as if you add something to 0 you get back the same thing.) @example @group (define (list-prod lis) (if (null? lis) 1 (+ (car lis) (list-prod (cdr lis))))) @end group @end example Given this definition, @example (list-prod '(2 3 4 5)) @end example is equivalent to @example (* 2 (* 3 (* 4 (* 5 1)))) @end example [ the following is now somewhat redundant with earlier material: ] Given these definitions, you can probably imagine a very similar function to subtract the elements of a list, or to divide the elements of a list. For subtraction, the base value for an empty list should probably be zero, because subtracting zero doesn't change anything. For division it should probably be one. We can write a higher-order procedure @code{reduce} that implements this pattern in a general way, taking three arguments: any procedure you want successively applied to the elements of a list, an appropriate base value to use as a result for empty lists, and the list to do it to. @example @group (define (reduce fn base-value lis) (if (null? lis) base-value (fn (car lis) (reduce fn base-value (cdr lis))))) @end group @end example This is a very general procedure, that can be used for lots of things besides numerical operations on lists of numbers: it can be used for any computation over successive items in a list. What does @code{(reduce cons '() '(a b c d))} do? It's equivalent to @code{(cons 'a (cons 'b (cons 'c (cons 'd '())))}. That is, @code{(reduce cons '() }@emph{list}@code{)} copies a list. We could define @code{list-copy} that way: @example (define (list-copy lis) (reduce cons '() lis)) @end example We could also define @code{append} that way. Here's a two-argument version of @code{append}: @example (define (append list1 list2) (reduce cons list2 list1)) @end example The reduction of a list using (lambda (x rest) (cons (* x 2) rest)) constructs a new list whose elements are twice the values of the corresponding elements in the original list. @example @group Scheme>(reduce (lambda (x rest) (cons (* x 2) rest)) '() '(1 2 3 4)) (2 4 6 8) @end group @end example The @code{reduce} procedure above is handy, because you can use it for many different kinds of computations over different kinds of lists values, as long as you can process the elements (and construct the result) front-to-back. It's a little awkward, though, in that each time you use it, you have to remember the appropriate base value for the operation you're applying to a list. Sometimes it would be preferable to come up with a single specialized procedure like @code{list-sum}, which implicitly remembers which function it should apply to the list elements (e.g., +) and what base value to return for an empty list (e.g., 0). We can write a procedure @code{make-reducer} that will automatically construct a reducer procedure, given a function and a base value. Here's an example usage: @example @group Scheme> (define list-sum (make-reducer + 0)) list-sum Scheme> (define list-product (make-reducer * 1)) list-copy Scheme> (list-sum '(1 2 3 4)) 10 Scheme> (list-product '(1 2 3 4)) 24 @end group @end example Make sure you understand the expressions above. The define forms are @code{not} using procedure definition syntax---they're using plain variable definition syntax, but the initial value expressions return procedures constructed by make-reducer. If we hadn't wanted to define procedures named list-sum and list-product, and hang on to them, we could have just taken the procedures returned by make-reducer and called them immediately: @example @group Scheme> ((make-reducer + 0) '(1 2 3 4)) 10 Scheme> ((make-reducer * 1) '(1 2 3 4)) 24 @end group @end example This is very much like calling our original @code{reduce} procedure, except that each time we're constructing a specialized procedure that's like @code{reduce} customized for particular values of its first two arguments; then we call that new, specialized procedure to do the work on a particular list. Here's a simple definition of @code{make-reducer} in terms of @code{reduce}: @example @group (define (make-reducer fn base-value) (lambda (lis) (reduce fn base-value lis))) @end group @end example Notice that we @emph{are} using procedure definition syntax here, so the @code{lambda} in the body will create and return a closure. But suppose we don't already have a reduce procedure, and we don't want to leave one lying around. A cleaner solution is to define the general @code{reduce} procedure as a local procedure, and create closures of it in different environments to customize it for different functions and base values. @example @group (define (make-reducer fn base-value) (letrec ((reduce (lambda (lis) (if (null? lis) base-value (fn (car lis) (reduce (cdr lis))))))) reduce)) ; return new closure of local procedure @end group @end example This procedure uses closure creation to create a customized version of @code{reduce} When @code{make-reducer} is entered, its arguments are bound and initialized to the argument values---i.e., the function and base value we want the custom reducer to use. In this environment, we create a closure of the standard reducer procedure using lambda. We wrap the lambda in a letrec so that the reducer can see its own name. Notice that since reduce is a local procedure, it can see the arguments to make-reducer, and we don't have to pass it those arguments explicitly. By using local procedure definition syntax---which not all Schemes support---we can write this as: @example @group (define (make-reducer fn base-value) (define (reduce lis) (if (null? lis) base-value (fn (car lis) (reduce (cdr lis))))) reduce)) ;return new closure of local procedure @end group @end example Make sure that you understand that these are equivalent---the local @code{define} is equivalent to a letrec and a lambda, and in either case the closure created (by the @code{lambda} or the @code{define) will capture the environment where the arguments to make-reducer are bound.