SICP Exercise 1.32: Accumulate

1. Show that sum and product (exercise 1.31) are both special cases of a still more general notion called accumulate that combines a collection of terms, using some general accumulation function:

   (accumulate combiner null-value term a next b)
   

   Accumulate takes as arguments the same term and range specifications as sum and product, together with a combiner procedure (of two arguments) that specifies how the current term is to be combined with the accumulation of the preceding terms and a null-value that specifies what base value to use when the terms run out. Write accumulate and show how sum and product can both be defined as simple calls to accumulate.
2. If your accumulate procedure generates a recursive process, write one that generates an iterative process. If it generates an iterative process, write one that generates a recursive process.

As I noted in the previous exercise, the differences between the sum and product procedures come down to the base value and the operation to apply when building the result. To produce an implementation of accumulate from either sum or product then becomes a case of simply changing the name of the procedure and parameterizing these differences:

(define (accumulate combiner null-value term a next b)
  (if (> a b)
      null-value
      (combiner (term a)
                (accumulate combiner null-value term (next a) next b))))

And we can then use this to implement sum and product:

(define (sum term a next b)
  (accumulate + 0 term a next b))
 
(define (product term a next b)
  (accumulate * 1 term a next b))

These should work just the same as the original versions:

> (sum (lambda (x) (* x 2)) 1 inc 10)
110
> (sum identity 1 inc 10)
55
> (product identity 1 inc 10)
3628800
> (product (lambda (x) (* x 3)) 3 inc 5)
1620

And of course we then need to translate this to its iterative equivalent. We do this in pretty much the same way as we did in the previous exercises, only this time we start with null-value and use combiner as the operator to accumulate the result:

(define (accumulate combiner null-value term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (combiner (term a) result))))
  (iter a null-value))

Let's see what we get:

> (accumulate + 0 cube 1 inc 10)
3025
> (accumulate * 1 cube 1 inc 10)
47784725839872000000