SICP を読んでみる #26 第一章 pp.31-44

昨日も一応問題に手をつけたものの、差し込み作業が入ってしまってほとんど進まなかったので今日も第一章の最後の問題二つ。
内容を見る感じ、第一章の総まとめになる内容なので、キッチリと片をつけたいものです。

1.3 おさらい

全体的に流れが把握できていない感じがしたので、1.3 のおさらいから始めました。

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

(define (square x)
  (* x x))


(define (sum-square a b)
  (define (inc x)
    (+ x 1)
  (sum square a inc b))

上のコードは lambda を使えばこのように書ける

(define (sum-square a b)
  (sum square a (lambda (x) (+ x 1)) b))

(define (sum-square a b)
  (sum (lambda (x) (* x x))  a (lambda (x) (+ x 1)) b))

square まで lambda で書いてしまうのはちょっとやりすぎ感がある

区間積分

(define (cube x)
  (* x x x))

(define dx 0.00001)
(define (integral f a b)
  (* (sum f a (lambda (x) (+ x dx) b) dx)))

(integral cube 0 1)

問1.32 accumulate

(define (accumulate combiner null-value term a next b)
  (define (iter v)
    (if (> v b)
        null-value
        (combiner (term v) (iter (next v)))))

  (* (iter (+ a (/ dx 2))) dx))

(define (integral f a b)
  (accumulate + 0 f a (lambda (x) (+ x dx)) b))

(integral cube 0 1)

関数の不動点の探索

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

(fixed-point cos 1.0)

1.3.4 値として返される手続き

平均緩和のコード化

(define (average v1 v2)
  (/ (+ v1 v2) 2))
(define (average-damp f)
  (lambda (x) (average x (f x))))

平均緩和付き平方根の計算
y → x/y :

(define (sqrt x)
  (fixed-point (lambda (y) (/ x y)) 1.0))

上記は収束しないので平均緩和を使用する

y → (average-damp (x/y))

(define (sqrt x)
  (fixed-point (average-damp (lambda (y) (/ x y))) 1.0))

(sqrt 2.0)

Newton 法

微分

(define dx 0.00001)
(define (deriv g)
  (lambda (x) (/ (- (g (+ x dx)) (g x)) dx)))

Newton 法で実装

(define (newton-transform g)
  (lambda (x) (- x (/ (g x) ((deriv g) x)))))
(define (newton-method g guess)
  (fixed-point (newton-transform g) guess))

Newton 法で平方根を求める

sqrt(y) = x
y^2 = x
g(x) = y^2 - x

g(x) = 0 になればよいので、Newton 法に落しこめる。

(define (sqrt x)
  (newton-method (lambda (y) (- (square y) x)) 1.0))

(sqrt 2.0)

抽象と第一手続き

平均緩和法と Newton 法を用いた平方根の計算方法を導き出したが、これを抽象化できる

平均緩和法はこのように書かれていた :

(define (sqrt x)
  (fixed-point (average-damp (lambda (y) (/ x y))) 1.0))

Newton 法はこのように書かれていた :

(define (newton-method g guess)
  (fixed-point (newton-transform g) guess))
(define (sqrt x)
  (newton-method (lambda (y) (- (square y) x)) 1.0))

fixed-point-of-transform を定義して、それぞれを書きなおす

(define (fixed-point-of-transform g transform guess)
  (fixed-point (transform g) guess))

平均緩和法 :

(define (sqrt x)
  (fixed-point-of-transform (lambda (y) (/ x y))
                            average-damp
                            1.0))

Newton 法 :

(define (sqrt x)
  (fixed-point-of-transform (lambda (y) (- (square y) x))
                            newton-transform
                            1.0))

問題回答

問1.45

(define (compose f g)
  (lambda(x) (f (g x))))

(define (repeated f n)
  (if (= n 0)
      (lambda(x) x)
      (compose f (repeated f (- n 1)))))


(define (n-th-root n x k)
  (fixed-point-of-transform (lambda (y) (/ x (expt y (- n 1))))
                            (repeated average-damp k)
                            1.0))

(n-th-root 2 2.0 1) ; OK
(n-th-root 3 2.0 1) ; OK
(n-th-root 4 2.0 1) ; NG

条件を追い切れなかったのでカンニング。

;n=2,3       はk=1で出来る. 
;n=4,5,..,7  はk=2で出来る. 
;n=8,9,...,15はn=3で出来る. 
;n=16,...    はn=4でないと出来ないらしい.

らしい。

(define (n-th-root n x)
  (let ((k (floor (/ (log n) (log 2)))))
    (fixed-point-of-transform (lambda (y) (/ x (expt y (- n 1))))
                              (repeated average-damp k)
                              1.0)))

(n-th-root 4 2.0) ;OK

全体の流れがもやっとしていたので、1.3 を一通りおさらいしつつ問題に取り組んでみました。
おかげで前よりも理解が進んだ気がします。

これで第一章は残るところ問1.46 の一つのみです。

philo式