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