SICP読書録 #10 1.3.1 引数としての手続き

hiroshi-manabe様の日本語訳を使わせてもらいます。
練習問題等はGaucheで実行。

前回はこちら

1.3.1 引数としての手続き

指定した範囲で、何らかの集計を行う手続きを作ってみる。

(define (sum-integers a b)
  (if (> a b)
      0
      (+ a (sum-integers (+ a 1) b))))

(define (sum-cubes a b)
  (define (cube x) (* x x x))
  (if (> a b)
      0
      (+ (cube a) (sum-cubes (+ a 1) b))))

(define (pi-sum a b) ; pi/8 に収束する
  (if (> a b)
      0
      (+ (/ 1.0 (* a (+ a 2)))
         (pi-sum (+ a 4) b))))

どれも似ている。というか、以下のパターンに当てはまるものばかりだ。

(define (<name> a b)
  (if (> a b)
      0
      (+ (<term> a))
         (<name> (<next> a) b))))

このパターンを再利用するには？ termとnextを引数として渡せるようにしてしまえばよい。

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

sum-integers、sum-cubes、pi-sumを、これを使って定義しなおそう。

(define (inc n) (+ n 1))
(define (identity x) x)
(define (cube x) (* x x x))

(define (sum-integers a b)
  (sum identity a inc b))

(define (sum-cubes a b)
  (sum cube a inc b))

(define (pi-sum a b)
  (define (pi-term x)
    (/ 1.0 (* x (+ x 2))))
  (define (pi-next x)
    (+ x 4))
  (sum pi-term a pi-next b))

このパターンを再利用すれば、積分だってできる。

(define (integral f a b dx)
  (define (add-dx x)
    (+ x dx))
  (* (sum f (+ a (/ dx 2.0)) add-dx b) dx))

cubeを0から1の範囲で積分すると、1/4になるはず。やってみよう。

gosh> (integral cube 0 1 0.01)
0.24998750000000042
gosh> (integral cube 0 1 0.001)
0.249999875000001

練習問題 1.29

シンプソンの公式というのを利用すると、より正確な積分ができる。
nは適当な偶数、$h=(b-a)/n$で、$y_k=f(a+kh)$とすると、

\int_{a}^{b}f=\frac{h}{3}(y_0+4y_1+2y_2+4y_3+2y_4+...+2y_{n-2}+4y_{n-1}+y_n)

実装してみよう。

(define (integral f a b n)
  (define h (/ (- b a) n))
  (define (term k)
    (* (f (+ a (* k h)))
       (cond ((= k 0) 1.0)
             ((= k n) 1.0)
             ((= (remainder k 2) 1) 4.0)
             ((= (remainder k 2) 0) 2.0))))
  (* (/ h 3.0) (sum term 0 inc n)))

実行してみる。

gosh> (integral cube 0 1 10)
0.24999999999999997
gosh> (integral cube 0 1 100)
0.24999999999999992
gosh> (integral cube 0 1 1000)
0.2500000000000002

練習問題1.30

sum手続きは再帰プロセスになる。反復プロセスに書き換えよう。

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

先ほどのintegralを再びロードして実行してみる。

gosh> (integral cube 0 1 10)
0.25
gosh> (integral cube 0 1 100)
0.25
gosh> (integral cube 0 1 1000)
0.25000000000000006