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.

根据练习 1.30和练习 1.31掌握的 sum 与 product，我们可以看到实际 + 与 * 的部分可以变为一个可变的东西，这样就能又抽象出一个过程来，用这个新的过程来定义 sum 和 product：

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

要写出迭代的版本，与上面的思路一直，只要把 product 与 sum 的迭代的过程作对比就可以得到了。

(define (accumulate/iter combiner null-value term a next b)
  (define (iter c result)
    (if (> c b)
        result
        (iter (next c)
              (combiner result (term c)))))
  (iter a null-value))

(define (sum/iter term a next b)
  (accumulate/iter + 0 term a next b))

(define (product/iter term a next b)
  (accumulate/iter * 1 term a next b))

然后是进行测试。我们先对递归与迭代的 accumulate 版本同时进行 product 与 sum 的定义，然后测试：

(load "../testframe.scm")

;; product tests
(let ((p (product (lambda (x) x)
                  1
                  (lambda (x) (+ 1 x))
                  10))
      (p1 (product/iter (lambda (x) x)
                        1
                        (lambda (x) (+ 1 x))
                        10)))
  (assert= p
           (* 2 3 4 5 6 7 8 9 10))
  (assert= p1
           (* 2 3 4 5 6 7 8 9 10)))

;; sum tests
; cube
(define (inc n) (+ n 1))
(define (cube x) (* x x x))
(define (sum-cubes a b)
  (sum cube a inc b))
(define (sum-cubes/iter a b)
  (sum/iter cube a inc b))
(assert= (sum-cubes 1 10) 3025)
(assert= (sum-cubes/iter 1 10) 3025)

; sum-integers
(define (identity x) x)
(define (sum-integers a b)
  (sum identity a inc b))
(define (sum-integers/iter a b)
  (sum/iter identity a inc b))
(assert= (sum-integers 1 10) 55)
(assert= (sum-integers/iter 1 10) 55)

这一题中，我们看到了将过程作为参数传递到另外一个过程中可以带给我们一种抽象的能力。但这里也只是对比较明显的两个过程进行一种抽象，在第 XXX 节中，我们将对两个完全不一样的两个过程进行抽象。在那里，我们将学会在我们构造一个大型系统时如何使用一种思路来构造抽象。

SICP 全笔记