SICP Exercise 1.32: Accumulator

From SICP section 1.3.1 Procedures as Arguments

Exercise 1.32 asks us to show how sum and product are special cases of an even more abstract concept called accumulate that combines a collection of terms. We're given the following procedure signature to start with:

(accumulate combiner null-value term a next b)

The arguments term, a, next, and b serve the same purpose as they did in sum and product. The new arguments are combiner, which takes a procedure of two arguments that specifies how the current term should be combined with the accumulation of all the preceding terms, and null-value, which specifies what base value to use when the terms run out.

We need to test accumulate by implementing both sum and product in terms of the new procedure. We also need to implement both recursive and iterative versions of accumulate.

We saw in exercise 1.31 how similar sum and product are. To create a higher-order procedure that can be used to implement both of these ideas, we need to look at where they're different. Let's look at the recursive version first.

(define (sum term a next b)
(if (> a b)
0
(+ (term a)
(sum term (next a) next b))))

(define (product term a next b)
(if (> a b)
1
(* (term a)
(product term (next a) next b))))

At a casual glance these two functions look almost exactly the same. They're only different in name, the null value used when a > b, and the operator used to combine terms.

(define (<name> term a next b)
(if (> a b)
<null-value>
(<operator> (term a)
(<name> term (next a) next b))))

These are exactly the parameters that need to change to create a higher-order accumulate procedure.

(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))))

Given their similarities, redefining sum and product in terms of accumulate is easy.

(define (sum term a next b)
(accumulate + 0 term a next b))

(define (product term a next b)
(accumulate * 1 term a next b))

An iterative version can be created using the same technique of substituting what's different about the iterative versions of sum and product from previous exercises.

(define (accum-iter 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))

Any of these procedures can be tested using the same tests from the previous exercises and comparing the results.


Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.