SICPの勉強 問題1.46

SICP1.3.4の問題1.46を解いてみる。

iterative-improveの定義。これは再帰で書くのがすごくしっくりくる。

(defn iterative-improve [good-enough? improve]
  (fn [guess]
    (if (good-enough? guess)
      guess
      (recur (improve guess)))))

iterative-improveを使った平方根の求め方：

(defn sqrt [x]
  (let [tolerance    0.00001
        good-enough? (fn [y] (< (Math/abs (- x (* y y))) tolerance))
        improve      (fn [z] (/ (+ z (/ x z)) 2))]
    ((iterative-improve good-enough? improve) 1.0)))

比較的楽。

fixed-pointの定義：

(defn fixed-point [f guess]
  (let [tolerance     0.00001
        close-enough? (fn [x] (< (Math/abs (- x (f x))) tolerance))]
    ((iterative-improve close-enough? f) guess)))

こちらはどうだろう。隣接するguessの差がtolerance以下になるのが停止条件なので、good-enough?の定義にimprove関数が使われているのはあまり嬉しくない気がするが・・・　さらにいうとimprove関数が毎回二回呼ばれていて非効率。まあ、これは本当に気になるならmemoizeできるか。

これで第一章が終わり。取りこぼしの問題も後から埋めてみたいが、とりあえずデータ抽象化の話題に移る。