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))