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.
1 comment:
In paragraph 4:
Let's look at the iterative versions first.
That should have been recursive (instead of iterative).
Post a Comment