hiroshi-manabe様の日本語訳を使わせてもらいます。
練習問題等はGaucheで実行。
1.3.4 返り値としての手続き
本題に入る前に、関数の不動点を求める手続きを再掲しておこう。
(define tolerance 0.00001)
(define (fixed-point f first-guess)
(define (close-enough? v1 v2)
(< (abs (- v1 v2))
tolerance))
(define (try guess)
(let ((next (f guess)))
(if (close-enough? guess next)
next
(try next))))
(try first-guess))
関数 $x \mapsto x/y$ の不動点を求めることで、$x$の平方根を求めることができる、という例を1.3.3で取り上げた。
この際、平均緩和法というテクニックを利用したのだが、これを手続きにして抽象化してしまおう。
(define (average-damp f)
(lambda (x) (average x (f x))))
これは、手続きを返す手続きだ。
これを使って平方根を求める手続きを書きなおそう。
(define (sqrt x)
(fixed-point (average-damp (lambda (y) (/ x y)))
1.0))
sqrt手続きはこれでずいぶん見通しがよくなった。fixed-pointが不動点探索、average-dampが平均緩和法を表し、そして関数 $y\mapsto x/y$ がそのまま表れている。
例えば$x$の三乗根は $y\mapsto x/y^2$ の不動点だ。ここまでのお膳立てが整ってれば、すぐ応用できる。
(define (cube-root x)
(fixed-point (average-damp (lambda (y) (/ x (square y))))
1.0))
ニュートン法
$Dg(x)$は$g$の導関数だとする。
Dg(x)=\frac{g(x+dx)-g(x)}{dx}
これを手続きにしよう。
(define dx 0.000001)
(define (deriv g)
(lambda (x) (/ (- (g (+ x dx)) (g x)) dx)))
ところで、$x \mapsto g(x)$が微分可能ならば、方程式$g(x)=0$の解は以下に示す関数$x \mapsto f(x)$の不動点となる。
f(x) = x - \frac{g(x)}{Dg(x)}
すでに不動点探索の手続きfixed-pointがあるんだから、以下のように実装できる。
(define (newton-transform g)
(lambda (x) (- x (/ (g x) ((deriv g) x)))))
(define (newtons-method g guess)
(fixed-point (newton-transform g) guess))
$x$の平方根を求めるには、関数 $y \mapsto y^2-x$ のゼロ点を求めればいい。
(define (sqrt x)
(newtons-method
(lambda (y) (- (square y) x)) 1.0))
抽象化とファーストクラス手続き
ここまで、平方根を求める手続きを2つ実装した。
比較のため、ちょっと修正を加えた上で並べてみよう。
(define (sqrt-fixed-point x)
(fixed-point
(average-damp (lambda (y) (/ x y)))
1.0))
(define (sqrt-newton x)
(fixed-point
(newton-transform (lambda (y) (- (square y) x)))
1.0))
これだけ似てるんなら、そのパターンを取り出して抽象化できる。
(define (fixed-point-of-transform g transform guess)
(fixed-point (transform g) guess))
それぞれのsqrt手続きを書き直してみよう。
(define (sqrt-fixed-point-2 x)
(fixed-point-of-transform
(lambda (y) (/ x y)) average-damp 1.0))
(define (sqrt-newton-2 x)
(fixed-point-of-transform
(lambda (y) (- (square y) x)) newton-transform 1.0))
こんな芸当が可能なのは、Lispでは手続きがファーストクラスの地位を持っているから、
つまり、次のような特権を持っているからなのだ。
- 変数によって名前をつけることができる。
- 手続きに引数として渡すことができる
- 手続きの返り値になることができる。
- データ構造に組み込むことができる。
練習問題1.40
newtons-methodを利用して、方程式$x^3+ax^2+bx+c=0$の解を求める。
以下のような手続きを作っておけばOK。
(define (cubic a b c)
(lambda (x) (+ (* x x x) (* a x x) (* b x) c)))
検算しながら動かしてみよう。
gosh> (newtons-method (cubic 2 3 4) 1)
-1.650629191485064
gosh> ((cubic 2 3 4) -1.650629191485064)
-2.0879387108152514e-10
gosh> (newtons-method (cubic 10 9 8) 1)
-9.108322961992677
gosh> ((cubic 10 9 8) -9.108322961992677)
1.9895196601282805e-13
練習問題1.41
引数が１つの手続きを引数として受け取り、その手続きを２回適用する手続きを返す手続きdoubleを作ってみよう。早口言葉みたい。
(define (double p) (lambda (x) (p (p x))))
実行結果。incは引数に1を足す手続き。
gosh> ((double inc) 3)
5
gosh> (((double (double double)) inc) 5)
21 ; 2^2^2=16回incを適用する
練習問題1.42
$f,g$はそれぞれ１引数関数だったとき、$x\mapsto f(g(x))$ とすることを合成という。
合成を行う手続きcomposeを作ってみよう。
(define (compose f g) (lambda (x) (f (g x))))
実行結果。
gosh> ((compose square inc) 6)
49 ; (6+1)^2