ochalog

RubyとMediaWikiとIRCが好き。

SICP: Exercise 1.32

問題 1.32

  1. sum と(問題 1.31 の)product は、一般的なアキュムレーションの関数:

     (accumulate combiner null-value term a next b)
    

    を使い、項の集りを組み合せる accumulate という更に一般的なものの特殊な場合であることを示せ。accumulate は引数として sumproduct と同様、項と範囲指定と、先行する項のアキュムレーションと現在の項をどう組み合せるかを指定する(二引数の)combiner 手続き、項がなくなった時に使う値を指定する null-value をとる。accumulate を書き、sumproductaccumulate の単なる呼出しで定義出来ることを示せ。

  2. 上の accumulate再帰的プロセスを生成するなら、反復的プロセスを生成するものを書け。反復的プロセスを生成するなら、再帰的プロセスを生成するものを書け。

計算機プログラムの構造と解釈 第二版 1.3.1 引数としての手続き」より

脚注 51 で触れられているように、後に並び(リスト)が出たとき、アキュミュレーションは fold とか reduce としてよく使われる。

まずは再帰的プロセスで書いてみる。

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

次に反復的プロセスで書く。問題 1.30 と同様。

ochaochaocha3.hateblo.jp

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

sumproductaccumulate を使って書くとこうなる。

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

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

とても簡潔。