Arantium Maestum

プログラミング、囲碁、読書の話題

SICPの勉強 問題1.41~44

SICP1.3.4の問題1.41、42、43そして44を解いてみる。

1.41問

引数1の関数を取り、その関数を倍掛けするdouble関数:

(defn double [f]
  (fn [x] (f (f x))))

問題文に出てくる(((double (double double)) inc) 5)について、パッと見だと5+8で13かな?と思った。

実際は「倍掛けを倍掛けする」という関数、つまり4倍掛けの関数をその関数自身の引数にしているので、16倍掛け関数になって5+16で結果21になる。

((double (double (double inc))) 5)だと結果は普通に13。

1.42問

(defn compose [f g]
  (fn [x] (f (g x))))

倍掛けは(defn double [f] (compose f f))になる。

1.43問

(defn repeated [f n]
  (if (= 1 n)
    f
    (compose f (repeated f (dec n)))))

composeを使ったdouble関数の普遍化。(compose f (compose f ... (compose f f) ... ))のような形になる。

1.44問

(defn smooth [f]
  (let [dx 0.00001]
    (fn [x]
      (/ (+ (f (- x dx))
            (f x)
            (f (+ x dx)))
         3))))

(defn n-fold-smooth [f n]
  ((repeated smooth n) f))

O(3n)で計算量もメモリ消費も増えていく恐ろしい関数。n=10とかだったらまだ知覚できるほど遅くはないが・・・