These exercises are due at the beginning of class on Tuesday, April 8. In each case, you should submit the source code for your procedure and also show what happens when your procedure is invoked, in enough different cases to satisfy me that it works as described. Once again, use submit to create a log file and elm to mail it to me.

1. Procedures as arguments.

Design, write, and test a procedure named accumulate, which takes three arguments -- a procedure proc of arity 2, an initial value start, and a list ls -- and returns the result of applying proc first to the initial value and the first element of the list, then to the result of the first step and the second element of the list, then to the result of the second step and the third element of the list, and so on. (If ls is the null list, accumulate should simply return the initial value unchanged.)

(accumulate + 12 '(4 -3 7)) ===> 20
(accumulate / 360 '(5 6 7 8)) ===> 3/14
(accumulate string-append "" '("pat" "hog" "ens")) ===> "pathogens"
(accumulate (lambda (rest first) (cons first rest)) '() '(a b c d))
    ===> (d c b a)
(accumulate - -23 '()) ===> -23

2. A variation on map.

Scheme's built-in map procedure applies one procedure successively to each element of a list and collects the results in a list. One could alternatively have variant form of map that takes a list of procedures and applies each of these procedures in turn to the same argument, collecting the results in a list:

(variant-map (list sqrt / (lambda (n) (* 4 n)) -) 144)
    ===> (12 1/144 576 -144)

Design, write, and test a definition of the variant-map procedure.

3. Returning procedures.

If f is a procedure of one argument that returns a value of the same type as its argument, one can often usefully consider what happens when that procedure is applied again to the value returned from the first application, and perhaps yet again to the value returned from the second, and so on. The procedure that consists of two such successive applications of f is called ``the second iterate of f'', the procedure that consists of three such applications is ``the third iterate of f,'' and so on.

For example, if f is the procedure that multiplies its argument by 3 -- that is, (lambda (n) (* 3 n)) -- then the second iterate of f is a procedure that multiplies its argument by 9 (because it performs two successive multiplications by 3), the third iterate is a procedure that multiplies its argument by 27, and so on. Another example: The second iterate of the sqrt procedure returns the fourth root of its argument (the square root of the square root), the third iterate returns the eighth root, and so on.

Naturally, the first iterate of any procedure is that procedure itself, and it is conventional to specify that the ``zeroth'' iterate of any procedure is the identity procedure (lambda (x) x).

Design, write, and test a higher-order procedure iterate that takes two arguments, a natural number n and a procedure f, and returns a procedure that is the nth iterate of f.

(Hint: There are two good ways to do this problem. One of them uses the compose procedure on page 201 of the text.)

This document is available on the World Wide Web as

http://www.math.grin.edu/courses/Scheme/spring-1997/exercise-3.html