Arantium Maestum

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

SICP

100 Days of Codeをやってみた

ツイッターで100 Days Of Codeというチャレンジがたまに流れていて、面白そうだったのでやってみた。今年も終わりに近づいているので今更ながら振り返ってみる。 100 Days Of Code概要 ルールは簡単: なるべく毎日1時間以上、業務外のコードを書く github…

SICPの勉強 問題2.30~32

2.30 木構造のデータ(nestしたリスト)の全ての葉ノードを二乗する関数: (defn square-tree [tree] (cond (empty? tree) () (seq? (first tree)) (cons (square-tree (first tree)) (square-tree (rest tree))) :else (cons (sq (first tree)) (square-tre…

SICPの勉強 問題2.27~28

2.27 リストの要素を逆順にするだけでなく、そのリストに含まれる全てのリストも同時に逆にする関数: (defn deep-reverse [x] (if (not (seq? x)) x (loop [items x result ()] (if (empty? items) result (recur (rest items) (cons (deep-reverse (first …

SICPの勉強 問題2.23

リストの要素全てに副作用ありの関数を適用していく関数(戻り値はnil): (defn for-each [f items] (if (empty? items) nil (do (f (first items)) (for-each f (rest items))))) そういえばこの関数に関してyoutubeのコメント欄でものすごいツッコマれて…

SICPの勉強 問題2.20~21

2.20 引数のリストの先頭の要素が奇数なら奇数の要素のみ全て、偶数なら偶数の要素のみ全てのリストを返す関数: (defn same-parity [x & xs] (letfn [(p? [n] (= (rem x 2) (rem n 2))) (f [items] (cond (empty? items) nil (p? (first items)) (cons (fir…

SICPの勉強 問題2.17~18

題意的に再帰を使って組み上げていくのがポイントなのだと思うが、やっぱり面倒くさい。 この章で作り上げていくmapやreduceといった抽象的にリストを捉えられる関数の偉大さを実感出来るのが最大の収穫だろうか。 2.17 リストの最後の要素を取り出す関数: …

SICPの勉強 問題2.7~11

2.7 (defn make-interval [a b] [a b]) (defn upper-bound [c] (first c)) (defn lower-bound [c] (last c)) 2.8 (defn sub-interval [x y] (max-interval (- (upper-bound x) (lower-bound y)) (- (lower-bound x) (upper-bound y)))) 2.10 (defn div-inter…

SICPの勉強 問題2.4~6

2.4 cons, car, cdrをclosureを使って作成: (defn cons [x y] (fn [m] (m x y))) (defn car [z] (z (fn [p q] p))) (defn cdr [z] (z (fn [p q] q))) 2.5 自然数に限定してcons, car, cdrを2と3の積を使って表す。 (defn cons [x y] (loop [x x y y r 1] (c…

SICPの勉強 問題2.2

線のデータを定義。 (defn make-segment [start-point end-point] [start-point end-point]) (defn start-segment [segment] (first segment)) (defn end-segment [segment] (last segment)) その前提となる点のデータを定義。 (defn make-point [x y] [x y]…

SICPの勉強 問題2.1

有理数のデータタイプがマイナスな場合は分子の方に必ず負号がくるように修正する。 まずは元のmake-rat関数をclojureで書く: (defn gcd [a b] (let [c (rem a b)] (if (zero? c) b (recur b c)))) (defn make-rat [n d] (let [g (gcd n d)] [(/ n g) (/ d …

SICPの勉強 Lecture 2B-2

www.youtube.com あと、この講義の終わりの方でcons-cellをclosureのみで作るコードが提示される。cons-cellがあればlinked listが作れて、複雑なデータ構造を組み上げていくことができる(遅いので実装上は使わないが)。データ構造すら、closureを持つproc…

SICPの勉強 Lecture 2B-1

www.youtube.com 37:40からの質問への答えがすごい。 Q: What does this "delayed decision through abstraction layers" do to the maxim of "do your design before any of your code"? A: Well that's someone's axiom, and I bet that's the axiom of so…

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を使…

SICPの勉強 問題1.45

SICP1.3.4の問題1.45を解いてみる。 average-dampとfixed-pointを使って任意のx、nにおけるxのn乗根の開方を求める。 average-dampを一回かけるだけの場合、y -> x/y3までは大丈夫だが y -> x/y4だと収束しない。 とりあえずaverage-dampを任意の回数繰り返…

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かな?と思っ…

SICPの勉強 問題1.40

SICP1.3.4の問題1.40を解いてみる。 x3 + ax2 + bx + c = 0の解をNewton's Methodで解く関数を作成する。 とりあえずNewton's Methodの実装: (defn deriv [g] (let [dx 0.00001] (fn [x] (/ (- (g (+ x dx)) (g x)) dx)))) (defn newton-transform [g] (fn …

SICPの勉強 問題1.38~39

SICP1.3.3の問題1.38と1.39を解いてみる。 1.38問はネイピア数から2引いた数を近似するもの。 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, ...というめんどくさい数列をdの関数としてcont-fracに入れる。 (defn d [x] (if (= 2 (rem x 3)) (* 2 (inc (quot x 3))) 1)…

SICPの勉強 問題1.37

SICP1.3.3の問題1.37を解いてみる。 recursive process: (defn cont-frac [n d k] (letfn [(rec [i] (if (= i k) (/ (n i) (d i)) (/ (n i) (+ (d i) (rec (inc i))))))] (rec 1))) iterative process: (defn cont-frac [n d k] (loop [i k result 0] (if (z…

SICPの勉強 問題1.36

SICP1.3.3の問題1.36を解いてみる。 と、その前にまずfixed-pointをClojureっぽく書いてみる。 シーケンス[a0 a1 ... an-1 an]から[a0 a1 ... ai-2 ai-1] [a1 a2 ... ai-1 ai] [a2 a3 ... ai ai+1]と続くベクトルのシーケンスを作成する関数: (defn conseq …

SICPの勉強 問題1.33

SICP1.3.1の問題1.33を解いてみる。 filtered-accumulateのiterative process版: (defn filtered-accumulate [combiner null-value filt f a next b] (loop [a a result null-value] (cond (> a b) result (filt a) (recur (next a) (combiner (f a) result…

SICPの勉強 問題1.32

SICP1.3.1の問題1.32を解いてみる。 accumulateのrecursive process版: (defn accumulate [combiner null-value f a next b] (if (> a b) null-value (combiner (f a) (accumulate combiner null-value f (next a) next b)))) iterative process版: (defn …

SICPの勉強 問題1.31

SICP1.3.1の問題1.31を解いてみる。 productのrecursive process版: (defn product [f a next b] (if (> a b) 1 (* (f a) (product f (next a) next b)))) iterative process版: (defn product [f a next b] (loop [a a result 1] (if (> a b) result (rec…

SICPの勉強 問題1.30

SICP1.3.1の問題1.30を解いてみる。 末尾再帰にするのがポイント。問いの中のコードをできるだけ利用するなら: (defn sum [f a next b] (letfn [(iter [a result] (if (> a b) result (recur (next a) (+ (f a) result))))] (iter a 0))) これで先ほどの(in…

SICPの勉強 問題1.29

SICP1.3.1の問題1.29を解いてみる。 とりあえずSimpson Ruleを使わない積分法: (defn sum [f a next b] (if (> a b) 0 (+ (f a) (sum f (next a) next b)))) (defn integral [f a b dx] (letfn [(add-dx [x] (+ x dx))] (* (sum f (+ a (/ dx 2.0)) add-dx …

SICPの勉強 問題1.17~18

SICP1.2.4の問題1.17と1.18を解いてみる。 とりあえずdoubleとhalveを定義: (defn double [x] (* 2 x)) (defn halve [x] (/ x 2)) linear recursiveに書くとこんな感じ: (defn mul [a b] (cond (zero? b) 0 (even? b) (double (mul a (halve b))) :else (+…

SICPの勉強 問題1.16

SICP1.2.4の問題1.16を解いてみる。 (defn fast-exp-iter [b n] (loop [n n x 1 y b z 1] (cond (zero? n) z (< n (* 2 x)) (recur (- n x) 1 b (* y z)) :else (recur n (* 2 x) (* y y) z)))) 引数名が考えつかなかった、というのはいつもの弁。 n = 2a1 +…

SICPの勉強 Lecture 1A-2

レクチャービデオの頭の方でHarold Abelsonの紹介テキストがちょこっと出るのだが、Assoc. Prof. EE & CSとある。 「電気工学と計算機科学の准教授」というわけだ。実際ちょくちょく電磁信号処理の話題が出てくる。そして信号処理はLisp(あるいは関数型言語…

SICPの勉強 Lecture 1A-1

というわけで本命のStructure and Interpretation of Computer Programs読解。 作者二人がヒューレット・パッカード社員向けにやったレクチャービデオと合わせて読んでいきたい。 www.youtube.com Computer Science is a terrible nameというのはまさにその…