Posted at

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

More than 1 year has passed since last update.

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

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

(define (sum term a next b)

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

sum-integerssum-cubespi-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