mahata@Choklog

問題1.32

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が再帰的プロセスを生成するなら,反復的プロセスを生成するものを書け.反復的プロセスを生成するなら,再帰的プロセスを生成するものを書け.

--

; --                                                                                                                          
; 標準的関数をロード                                                                                                          
; --                                                                                                                          
(load "./util.scm")

; --                                                                                                                          
; 再帰的なaccumulateの実装                                                                                                    
; --                                                                                                                          
(define (accumulate-rec combiner null-value term a next b)
  (if (> a b)
      null-value
      (combiner (term a)
                (accumulate-rec combiner null-value term (next a) next b))
  )
)
(print "再帰的な実装: " (accumulate-rec + 0 identity 1 inc 10))

; --                                                                                                                          
; 反復的なaccumulateの実装                                                                                                    
; --                                                                                                                          
(define (accumulate-rep 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)
)
(print "反復的な実装: " (accumulate-rep + 0 identity 1 inc 10))

実行する。

$ gosh 1.32.scm
再帰的な実装: 55
反復的な実装: 55

再帰的な実装も反復的な実装も、同じ値が返る。