SICP 問題1.32

2017/08/30

#sicp

a. sumと(問題1.31の)productは, 一般的なアキュムレーションの関数:
(accumulate combiner null-value term a next b)
を使い, 項の集りを組み合せるaccumulateという更に一般的なものの特殊な場合であることを示せ.
accumulateは引数としてsumや productと同様, 項と範囲指定と, 先行する項のアキュムレーションと現在の項をどう組み合せるかを指定する(二引数の)combiner手続き, 項がなくなった時に使う値を指定するnull-valueをとる.
accumulateを書き, sumやproductがaccumulateの単なる呼出しで定義出来ることを示せ.
b. 上のaccumulateが再帰的プロセスを生成するなら, 反復的プロセスを生成するものを書け. 反復的プロセスを生成するなら, 再帰的プロセスを生成するものを書け.

a

これはパッと見簡単そう。おさらいがてらsumとproductを持ってくる。

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

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

簡単簡単。

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

; 試す
(define (inc n) (+ n 1))
(define (cube x) (* x x x))

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

(define (sum-cubes a b)
  (sum cube a inc b))
(print (sum-cubes 1 10))
; => 3025

(define (factorial n)
  (product + 1 inc n))
(print (factorial 10))
; => 3628800

できたっぽい。

b

aでは反復的プロセスで書いたので、次に再帰的プロセスで書く。上記と同じように再帰的プロセス版のsumとproductを持ってくる。

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

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

accumulateを定義する。

(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 (inc n) (+ n 1))
(define (cube x) (* x x x))

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

(define (sum-cubes a b)
  (sum cube a inc b))
(print (sum-cubes 1 10))
; => 3025

(define (factorial n)
  (product + 1 inc n))
(print (factorial 10))
; => 3628800

できたー:)