(ns e2-4-5-6
  (:use [clojure.contrib.test-is :only (deftest is run-tests)])
  (:use [util.util :only (pow id)])
  (:use [clojure.contrib.generic.math-functions :only ()]))
(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)))
(deftest test-car-cdr
  (is (= (car (cons! 1 2)) 1))
  (is (= (cdr (cons! 1 2)) 2)))
(defn cons-n [x y]
  (* (pow 2 x) (pow 3 y)))

Can this be written as a fold . take-while? Should think about implementing this with a fold.

(defn- iter [z n x]
  (if (= (rem z x) 0)
      (recur (/ z x) (inc n) x)
(defn car-n [z]
  (iter z 0 2))
(defn cdr-n [z]
  (iter z 0 3))
(deftest test-car-cdr-n
  (is (= (car-n (cons-n 3 2)) 3))
  (is (= (cdr-n (cons-n 3 2)) 2)))
(def *zero*
  (fn [f] id))

At step 5 we have a function which returns a closure over its argument (which itself must be a function). The closure, when applied, applies the argument of the function it closes over to the argument of its own (the argument of the closure). In simple terms - (add-1 zero) returns a function which must be applied two times to yield a result.

For the sake of fun and profit, lets expand the add-1 with the result of the previous expansion 1. (add-1 (add-1 zero)) -> 2. (fn [f] (fn [x] (f (((fn [g] (fn [h] (g h))) f) x)))) -> 3. (fn [f] (fn [x] (f ((fn [h] (f h)) x)))) -> 4. (fn [f] (fn [x] (f (f x))))

Here we see that 'f' is applied 2 times (which represents the 'number 2' in the church encoding).

(defn add-1 [n]
  (fn [f]
    (fn [x]
      (f ((n f) x)))))
(def *one*
  (fn [f] (fn [x] (f x))))
(def *two*
  (fn [f] (fn [x] (f (f x)))))
(deftest one-two-test
  (is (= (((add-1 *one*) #(+ 1 %)) 0) 2))
  (is (= (((add-1 *two*) #(+ 1 %)) 0) 3)))
(defn plus [a b]
  (fn [f] (fn [x] ((a f) ((b f) x)))))
(deftest plus-test
  ; should be equal to (*two*)
  (is (= (((plus (add-1 *zero*) (add-1 *zero*)) #(+ 1 %)) 0) 2)))