読者です 読者をやめる 読者になる 読者になる

Arantium Maestum

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

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]
    (cond
      (pos? x) (recur (dec x) y (* 2 r))
      (pos? y) (recur x (dec y) (* 3 r))
      :else    r)))

(defn car [z]
  (loop [z z r 0]
    (if (zero? (rem z 2))
      (recur (/ z 2) (inc r))
      r)))

(defn cdr [z]
  (loop [z z r 0]
    (if (zero? (rem z 3))
      (recur (/ z 3) (inc r))
      r)))

題意的にremを使っていいのかが微妙だが・・・

2.6

自然数を関数で表す。(Church数の実装)

まずは問題で定義されているzeroとadd-1をclojureで定義し直す:

(def zero 
  (fn [f] (fn [x] x)))

(defn add-1 [n]
  (fn [f] (fn [x] (f ((n f) x)))))

それを踏まえて、one、two、そしてaddがどのようになるか、直接定義してみる:

(def one
  (fn [f] (fn [x] (f x))))

(def two
  (fn [f] (fn [x] (f (f x)))))

(def add [a b]
  (fn [f] (fn [x] ((a f) ((b f) x)))))

fを何回重ねて適用するか、で数字を表している。