Help us understand the problem. What is going on with this article?

SICP読書録 #15 1.3.4 返り値としての手続き

More than 1 year has passed since last update.

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

前回はこちら

1.3.4 返り値としての手続き

本題に入る前に、関数の不動点を求める手続きを再掲しておこう。

_.scm
(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で取り上げた。
この際、平均緩和法というテクニックを利用したのだが、これを手続きにして抽象化してしまおう。

_.scm
(define (average-damp f)
  (lambda (x) (average x (f x))))

これは、手続きを返す手続きだ。
これを使って平方根を求める手続きを書きなおそう。

_.scm
(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$ の不動点だ。ここまでのお膳立てが整ってれば、すぐ応用できる。

_.scm
(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}

これを手続きにしよう。

_.scm
(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があるんだから、以下のように実装できる。

_.scm
(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$ のゼロ点を求めればいい。

_.scm
(define (sqrt x)
  (newtons-method
   (lambda (y) (- (square y) x)) 1.0))

抽象化とファーストクラス手続き

ここまで、平方根を求める手続きを2つ実装した。
比較のため、ちょっと修正を加えた上で並べてみよう。

_.scm
(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))

これだけ似てるんなら、そのパターンを取り出して抽象化できる。

_.scm
(define (fixed-point-of-transform g transform guess)
  (fixed-point (transform g) guess))

それぞれのsqrt手続きを書き直してみよう。

_.scm
(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。

_.scm
(define (cubic a b c)
  (lambda (x) (+ (* x x x) (* a x x) (* b x) c)))

検算しながら動かしてみよう。

_.scm
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

引数が1つの手続きを引数として受け取り、その手続きを2回適用する手続きを返す手続きdoubleを作ってみよう。早口言葉みたい。

_.scm
(define (double p) (lambda (x) (p (p x))))

実行結果。incは引数に1を足す手続き。

_.scm
gosh> ((double inc) 3)
5
gosh> (((double (double double)) inc) 5)
21 ; 2^2^2=16回incを適用する

練習問題1.42

$f,g$はそれぞれ1引数関数だったとき、$x\mapsto f(g(x))$ とすることを合成という。
合成を行う手続きcomposeを作ってみよう。

_.scm
(define (compose f g) (lambda (x) (f (g x))))

実行結果。

_.scm
gosh> ((compose square inc) 6)
49 ; (6+1)^2
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away