Note: this wiki is now retired and will no longer be updated!

The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.

SICP exercise 1.32

From Drewiki
Jump to: navigation, search

This exercise has two parts.

Contents

Problem A

Show that sum from section 1.3.1 of the text and product from 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.

Solution A

Here's a recursive process-generating 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))))

And here are a couple of tests using sum and product:

(define (sum term a next b)
  (accumulate + 0 term a next b))
 
(define (inc n) (+ n 1))
 
(define (simpsons-rule-integral f a b n)
  (define (helper h)
    (define (y k)
      (f (+ a (* k h))))
    (define (term k)
      (cond ((or (= k 0) (= k n)) (y k))
            ((even? k) (* 2 (y k)))
            (else (* 4 (y k)))))
    (* (sum term 0 inc n)
       (/ h 3)))
  (helper (/ (- b a) n)))
 
(define (cube x) (* x x x))
 
(simpsons-rule-integral cube 0 1 100)

Output:

0.25
(define (product term a next b)
  (accumulate * 1 term a next b))
 
(define (factorial n)
  (define (identity n) n)
  (product identity 1 inc n))
(factorial 1)

Output:

1
(factorial 2)

Output:

2
(factorial 3)

Output:

6
(factorial 4)

Output:

24
(factorial 5)

Output:

120
(factorial 6)

Output:

720


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

Solution B

The definition of accumulate given above in Solution A generates a recursive process, so here's one that generates an iterative process:

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

Tests:

(simpsons-rule-integral cube 0 1 100)

Output:

0.25
(factorial 1)

Output:

1

</source> {{scheme-output|

(factorial 2)

Output:

2
(factorial 3)

Output:

6
(factorial 4)

Output:

24
(factorial 5)

Output:

120
(factorial 6)

Output:

720
Personal tools