SICP

毎日ちょっとずつやろうと思ってたけど月曜に飲み会があってから見事にgdgdに。なんという三日坊主。

11ページ

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

(define (sum-of-squares x y) (+ (square x) (square y)))

;; 問題1.3 三つの数を引数としてとり, 大きい二つの数の二乗の和を返す手続き
(define (sum-of-bigger-squares x y z)
  (if (and (<= x y) (<= x z))
      (sum-of-squares y z)
      (sum-of-bigger-squares y z x)))

14ページ

問題1.6ではまさに何故condがあるのにifも存在するのかが問われている。シンタクスシュガーかと思ってた私の考えは完全に読まれてるな。実際やってみると無限ループになったのか終わらなくなった:

;; 1.1.7.Newton法による平方根

(define (sqrt-iter guess x)
  (if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x) x)))

(define (improve guess x)
  (average guess (/ x guess)))

(define (average x y) (/ (+ x y) 2))

(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.0001))

(define (sqrt x) (sqrt-iter 1.0 x))

(print (sqrt 2)) ; -> 1.4142156862745097

;; 問題1.6 ifの新版
(define (new-if predicate then-clause else-clause)
  (cond (predicate then-clause)
        (else else-clause)))

;; sqrt-iterをnew-ifで上書き
(define (sqrt-iter guess x)
  (new-if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x) x)))

(print (sqrt 2)) ; -> 無限ループ

はて何故だろう? きっと評価順序が違うんだな。

• ifは正規順序で実行するから述語が真なら帰結式だけ評価して代替式は評価しない。
• new-ifは作用的順序で実行するから述語が真でも代替式まで評価してから帰結式を返す->代替式が再帰だから無限ループ

;; 問題1.7
(print (sqrt 1.0E-6))   ; -> 0.031260655525445276

;(print (sqrt 1.0E256)) ; -> 無限ループ

(define (good-enough? guess x)
  (< (abs (- (improve guess x) guess)) 1.0E-20))

(print (sqrt 1.0E-6))   ; -> 0.001

(print (sqrt 1.0E256))  ; -> 1.0e128

最初に定義した good-enouch? だと定数と比較しているので、その定数より小さな値の平方根を求めた場合に十分な精度が得られない。でも大きすぎると何故無限ループするのか、また guess の変化分で判定することで何故解消するのかよくわからないな。きっと有効桁数と評価順序の話なんだろうけど。
ちなみに上の解法では guess の変化分を見るために improve を一回余分に呼んで次回分の guess と比較することで対応した。 improve の呼び出しが増えたのは無駄な気もするけど前回分の guess と比較すると引数増やさなきゃいけないし、全体の結合度が上がるよりはこっちの方が健全な気がする。

;; 問題1.8 より一般的なNewton法を実装せよ。

;; まず立方根を実装してみる

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

(define (cbrt-iter guess x)
  (if (good-enough? guess x)
      guess
      (cbrt-iter (improve guess x) x)))

(define (improve guess x)
  (/ (+ (/ x (* guess guess)) (* 2 guess)) 3))

(define (good-enough? guess x)
  (< (abs (- (improve guess x) guess)) 1.0E-20))

(define (cbrt x) (cbrt-iter 1.0 x))

(print (cbrt 27)) ; -> 3.0


; 一般的な累乗の定義
(define (power x y) (power-iter x y x))

(define (power-iter x y temp)
  (cond ((> -1 y) (power-iter x (+ y 1) (* temp x)))
        ((= -1 y) (/ 1.0 temp))
        ((= 0 y) 1.0)
        ((= 1 y) temp )
        ((< 1 y) (power-iter x (- y 1) (* temp x)))))

(print (power 2 -3)) ; -> 0.25

(print (power 2 -1)) ; -> 0.5

(print (power 2 0)) ; -> 1

(print (power 2 4)) ; -> 16

(print (power 3 3)) ; -> 27


; 一般的な累乗根の定義
(define (pwrt-iter guess x root)
  (if (good-enough? guess x root)
      guess
      (pwrt-iter (improve guess x root) x root)))

(define (improve guess x root)
  (/ (+ (/ x (power guess (- root 1))) (* (- root 1) guess)) root))

(define (good-enough? guess x root)
  (< (abs (- (improve guess x root) guess)) 1.0E-20))

(define (pwrt x root) (pwrt-iter 1.0 x root))

(print (pwrt 16 2)) ; -> 4.0

(print (pwrt 27 3)) ; -> 3.0

(print (pwrt 4 4))  ; -> 1.4142156...

power-iter の定義がもうちょっとシンプルになりそうなものだけど眠いからパス。各関数の仮引数に root がついてまわってるのも何か臭うけど。あとでまた考える。