Scheme Programming Exercises, Part II 1. Consider the following function to sum the elements of a list (define (list-sum lis) (if (null? lis) 0 (+ (car lis) (list-sum (cdr lis))))) Given this definition, (list-sum '(10 15 20 25)) is equivalent to (+ 10 (+ 15 (+ 20 (+ 25 0)))). 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.) (define (list-prod lis) (if (null? lis) 1 (+ (car lis) (list-prod (cdr lis))))) Given this definition, (list-prod '(2 3 4 5)) is equivalent to (* 2 (* 3 (* 4 (* 5 1)))) 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. Write a procedure 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. 2. Consider the REDUCE procedure you wrote for #1. It 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 (reduce cons '() '(a b c d)) do? Consider that it's equivalent to (cons 'a (cons 'b (cons 'c (cons 'd '()))). What's the result of (reduce (lambda (x rest) (cons (* x 2) rest))) '() '(10 15 20 25)) What's the result of (reduce (lambda (x rest) (+ 1 rest)) 0 '(1 2 3 4 5 6 7)) (Your answers should explain the general function that is computed by handing these functions and base values to reduce, not just the particular answers for these particular lists.) 3. The reduce procedure above is handy, because you can use it for many different kinds of computations over different kinds of values. 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 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). Write a procedure MAKE-REDUCER that will automatically construct a reducer procedure, given a function and a base value. Here's an example usage: Scheme> (define list-sum (make-reducer + 0)) LIST-SUM Scheme> (define list-product (make-reducer * 1)) LIST-PRODUCT Scheme> (list-sum '(1 2 3 4)) 10 Scheme> (list-product '(1 2 3 4)) 24 Make sure you understand the expressions above. The define forms are 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: Scheme> ((make-reducer + 0) '(1 2 3 4)) 10 Scheme> ((make-reducer * 1) '(1 2 3 4)) 24 This is very much like calling our original REDUCE procedure, except that each time we're constructing a specialized procedure that's like 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. -------------------------------------------------------------------------- SOLUTIONS 1. (define (reduce fn base-value lis) (if (null? lis) base-value (fn (car lis) (reduce fn base-value (cdr lis))))) 2. The reduction of a list using cons copies the list. We made the base value '() so that the end of the list would be appropriately copied as the end of the new list. The reduction of a list using (lambda (x rest) (cons (* x 2) rest)) constructs a new lists whose elements are twice the values of the corresponding elements in the original list. (Of course, it will blow up if you give it a list containing non-numbers.) 3. Here's a simple solution: (define (make-reducer fn base-value) (lambda (lis) (reduce fn base-value lis))) Where here we're calling the general REDUCE procedure we defined before. Notice that we ARE using procedure definition syntax here, so the 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 reduce procedure as a local procedure, and create closures of it in different environments to customize it for different functions and base values. (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 This procedure uses closure creation to create a customized version of REDUCE. When 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: (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 Make sure that you understand that these are equivalent---the local define is equivalent to a letrec and a lambda, and in either case the closure created (by the lambda or the define) will capture the environment where the arguments to make-reducer are bound.