Exercise 1.32 of SICP

sicp

Exercise 1.32:

a. 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.

b. 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.

Part A

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

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

;Test the sum function
(define (cube x) (* x x x))
(define (simpson-integral f a b n)
  (define h (/ (- b a) n))
  (define (next k) (+ k 1))
  (define (coeff k)
    (cond ((or (= k 0) (= k n)) 1)
     	  ((even? k) 2)
	  (else 4)))
  (define (term k) 
    (* (coeff k) (f (+ a (* k h)))))
  (* (/ h 3.0)
     (sum term 0 next n)))

;Test the product function
(define (wallis n)
  (define (next n) (+ n 1))
  (define (term-num i) (if (even? i) (+ i 2) (+ i 1)))
  (define (term-den i) (if (even? i) (+ i 1) (+ i 2)))
  (define (fraction i) (/ (term-num i) (term-den i)))
  (* 4.0 (product fraction 1 next n)))

> (simpson-integral cube 1 2 1000)
3.75
> (wallis 5000)
3.1419067029355268

It’s good to know general version of sum and product still work.

Part B

Iterative versions of product and sum via iterative accumulate function

(define (accumulate-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))
(define (sum term a next b)
  (accumulate-iter + 0 term a next b))
(define (product term a next b)
  (accumulate-iter * 1 term a next b))