]> git.rkrishnan.org Git - sicp.git/blob - src/sicp/ex2_6.clj
rewrite `quote->cons' using `match'.
[sicp.git] / src / sicp / ex2_6.clj
1 (ns sicp.ex2_6
2   (:use [sicp utils]
3         [clojure.test]))
4
5 ;; from the problem
6 (def zero
7   (fn [f] (fn [x] 
8             x)))
9
10 (defn add-1 [n]
11   (fn [f] (fn [x]
12             (f ((n f) x)))))
13
14 (comment
15 (((add-1 zero) inc) 0)
16 ;; => 1
17 (((add-1 zero) inc) 1)
18 ;; => 2
19 )
20 ;; the above examples should be read as follows:
21 ;; (add-1 zero) returns the function which represents 1.
22 ;; i.e. You apply inc once to 0 and that yields 1.
23 ;; in the second example, we apply inc once to 1, and
24 ;; that yields 2. This is just to convert Churl numeral
25 ;; definition to roman numeral definition.
26
27 ;; as said in the hint, using substitution to evaluate (add-1 zero)
28 ;; tells us that (add-1 zero) == one has one composition of (f x)
29 ;; and (add-1 (add-1 zero)) == 1 is (f (f x)), so here is their formal
30 ;; definition.
31 (def one (fn [f] (fn [x] (f x))))
32
33 (def two (fn [f] (fn [x] (f (f x)))))
34
35 (comment
36 (((add-1 one) inc) 1)
37 ;;=> 3
38 (((add-1 one) inc) 2)
39 ;;=> 4
40 (((add-1 two) inc) 2)
41 ;;=> 5
42 )
43 ;; (add-1 one) => two. Apply inc twice on 1 => 3
44 ;; similarly the other examples.
45
46 ;; Definition of an add operator
47 ;; To do m + n, we should have a function which is applied f, n+m times.
48 ;;
49 ;; i.e.
50 ;;
51 ;; (m f) = takes a function f and composes a new function which composes
52 ;; f, m times and applies this new function to x.
53 ;; 
54 ;; (lambda (f) (lambda (x) ((m f) ((n f) x)))) will create this new
55 ;; function which compose a given function n+m times and hence is equiv
56 ;; to addition of m+n. Some simple repl experiments seem to verify the
57 ;; result.
58 (defn add [m n]
59   (fn [f] (fn [x]
60             ((m f) ((n f) x)))))
61
62 (comment
63 (((add one two) inc) 1)
64 ;;=> 4  
65 )
66
67 ;; another definition of add is this:
68 ;; m + n == (m + [1 + 1 + 1 + ... ]
69 (defn new-add [m n]
70   ((m add-1) n))
71
72 ;; continueing the same logic, (add one two) => three
73 ;; and inc applied three times to 1 is 4. This proves
74 ;; that our definition of add is correct.
75
76 ;; I used the wikipedia article to study Church Numerals:
77 ;; <http://en.wikipedia.org/wiki/Church_encoding#Computation_with_Church_numerals>
78
79 ;; comments?
80
81 (defn church-to-numeral [chfn]
82   ((chfn inc) 0))
83
84 (deftest test-church-to-numeral
85   (are [x y] [= x y]
86        (church-to-numeral one) 1
87        (church-to-numeral two) 2))
88
89 ;; church to roman: func to integer
90 (defn church-to-roman [f]
91   ((f (fn [x] (+ x 1))) 0))
92
93 ;; integer to func
94 (defn roman-to-church [n]
95   (fn [f] (fn [x] (first (drop n (take (inc n) (iterate f x)))))))
96
97 (defn church [n]
98   (loop [n n cf (fn [f] (fn [x] x))]
99     (if (zero? n)
100       cf
101       (recur (- n 1) (fn [f] (fn [x]
102                                (f ((cf f) x))))))))
103
104 (defn unchurch [f]
105   ((f (fn [x] (+ x 1))) 0))