exercise 1.30と1.32 - nyaago69のブログ

SICPのexercise 1.30と1.32

Excersize 1.30

a から bまで値をnext手続きで増分していき、
それらの値にterm手続きで指定した演算を適用した値を合計する手続き.
(term, nextとも１つの引数を要求する手続き)
例で、linear recursiveの例が出ているので、それのiterative版(末尾再帰)をつくるというもの.
例のlinear recursiveは以下のとおり.

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

で、解答してみたのが以下のとおり.
増分値といままで加算してきた値を引数に渡しながら反復すれば、よいはず.

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

これを使って、指定した範囲の連続したで整数値の合計を算出する手続きをつくって(linear recursiveの例と同じ)

(define (sum-integers a b)
  (define (inc x)  (+ x 1) )
  (define (identity x) x)
  (sum identity a inc b)
)

実際にあたいを求めてみました。

(sum-integers 1 10)
55      ; 1 + 2 + 3 ... 10
(sum-integers 1 100)
5050     ; 1 + 2 + 3 ... 100

Excersize 1.32

a から bまで値をnext手続きで増分していき、
それらの値にterm手続きで指定した演算を適用した値をcombinerで指定した手続きで積み上げる手続きを書く.
excersize 1.30のより抽象化(汎用化）した版で、combiner手続きとして、加算や積をとる手続きをとる.

linear recursive版

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

末尾再帰

iterative(末尾再帰)版

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

以上(いずれか)を使用して、累計をよる手続きと積をとる手続きを定義

(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-integers a b)
  (define (inc x)  (+ x 1) )
  (define (identity x) x)
  (sum identity a inc b)
)
; 
(define (product-integers a b)
  (define (inc x)  (+ x 1) )
  (define (identity x) x)
  (product identity a inc b)
)

そして、実際に値を求める

gosh> (sum-integers 1 10)
55      ; 1 + 2 + 3 ... 10
gosh> (sum-integers 1 100)
5050     ; 1 + 2 + 3 ... 100
gosh> (product-integers 1 5)
120     ; 1 * 2 * 3  * 4 * 5
gosh> (product-integers 1 6)
720    ; 1 * 2 * 3  * 4 * 5 * 6
gosh>