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

SICP Exercise 1.31: A Higher-Order Product

1. The sum procedure is only the simplest of a vast number of similar abstractions that can be captured as higher-order procedures. Write an analogous procedure called product that returns the product of the values of a function at points over a given range. Show how to define factorial in terms of product. Also use product to compute approximations to using the formula

   π = 2·4·4·6·6·8···
   4   3·3·5·5·7·7···
   

2. If your product 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.

So what are the differences between calculating the sum and calculating the product of a set of terms? When calculating a sum we start with 0 and use addition. When calculating a product we start with 1 and use multiplication. Other than that they're the same. We can use this to produce product. Here's the original implementation of sum:

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

To convert this to calculate a product we simply change the base value, the operation performed and, of course, the name of the procedure to produce:

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

We then want to use this to produce the procedure factorial and also the calculation of π/4 given above. Now to calculate the factorial of n we simply multiply the numbers between 1 and n. To do this we can set the start and end of the range to 1 and n respectively, use inc to produce the next values and identity to produce the terms to multiply. We also need to account for the fact that, by convention, 0! = 1. Here's the implementation I produced:

(define (factorial x)
  (if (= x 0)
      1
      (product identity 1 inc x)))

And here's some factorials for us:

> (factorial 0)
1
> (factorial 1)
1
> (factorial 2)
2
> (factorial 3)
6
> (factorial 4)
24
> (factorial 5)
120

How about the calculation of π/4? The numerator progresses with the sequence {2, 4, 4, 6, 6, 8, 8, ...}. The denominator progresses with the sequence {3, 3, 5, 5, 7, 7, 9, ...}. Assuming we have a sequence of numbers 1..n (i.e. a = 1, b = n and we use inc for next) then we could calculate the numerator and denominator using the somewhat convoluted calculations:

(define (numerator n) (* 2 (+ (floor (/ n 2)) 1)))
(define (denominator n) (+ (* 2 (floor (/ (+ n 1) 2))) 1))

However, it's easier if we look at the odd and even elements of the two sequences separately. For the numerator, the sequence of odd values is {2, 4, 6, 8, ...} and the sequence of even values is {4, 6, 8, ...}. Similarly for the denominator the sequence of odd values is {3, 5, 7, 9, ...} and for even values is {3, 5, 7, ...}. When n is odd, the numerator is n + 1 and the denominator is n + 2. When n is even these are reversed: the numerator is n + 2 and the denominator is n + 1. So we can simply figure out whether n is even or odd and perform the appropriate calculation to produce the term:

(define (pi-prod n)
  (define (pi-term n)
    (if (even? n)
        (/ (+ n 2) (+ n 1))
        (/ (+ n 1) (+ n 2))))
  (product pi-term 1 inc n))

And let's use this to give us an approximation to π:

> (* 4 (pi-prod 100))
3.1570301764551645
> (* 4 (pi-prod 1000))
3.143160705532257

That's part (a) of the exercise completed. For part (b) we're asked to produce an iterative version of product if we produced a recursive process or vice versa. Well, we produced a recursive process above, so we need to translate this to an iterative one. To do this we follow much the same process as we did for exercise 1.30. We want to produce a procedure with the form:

(define (product term a next b)
  (define (iter a result)
    (if <??>
        <??>
        (iter <??> <??>)))
  (iter <??> <??>))

The only differences in the translation process are the base value we start with and the operation to apply. When calculating the product of a sequence of terms we start with the base value of 1 and we use multiplication to combine the terms:

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

Exercising this version of product produces identical results to the recursive version. For example, calculating factorials with this directly gives:

> (product identity 1 inc 1)
1
> (product identity 1 inc 2)
2
> (product identity 1 inc 3)
6
> (product identity 1 inc 4)
24
> (product identity 1 inc 5)
120

SICP Exercise 1.30: Summing Iteratively

The sum procedure above generates a linear recursion. The procedure can be rewritten so that the sum is performed iteratively. Show how to do this by filling in the missing expressions in the following definition:

(define (sum term a next b)
  (define (iter a result)
    (if <??>
        <??>
        (iter <??> <??>)))
  (iter <??> <??>))

To produce a recursive version of sum we need to start at a. We also need to start with the "null" value for a sum, 0, in case a > b. If that is the case then there will be no terms to sum, and so the result should be 0. This allows us to fill in the gaps in the call to iter:

(define (sum term a next b)
  (define (iter a result)
    (if <??>
        <??>
        (iter <??> <??>)))
  (iter a 0))

We can also quickly fill in a couple of the other blanks... We know we want to terminate when a > b, and when we terminate we want the value of sum to be the accumulated result:

(define (sum term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter <??> <??>)))
  (iter a 0))

Finally, we need to fill in the recursive call to iter. When we make the recursive call to iter we need to call it with the next of the values we are iterating over. This is generated by (next a). We also need to call it with the updated result, which we produce by adding (term a) to the accumulated result so far. This gives us our final implementation:

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

So let's try it out:

> (sum cube 1 inc 10)
3025
> (sum cube 4 inc 7)
748
> (sum identity 1 inc 10)
55
> (sum identity 4 inc 7)
22