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とかだったらまだ知覚できるほど遅くはないが・・・