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 (defn add [m n]
  48   (fn [f] (fn [x]
  49             ((m f) ((n f) x)))))
  50
  51 (comment
  52 (((add one two) inc) 1)
  53 ;;=> 4
  54 )
  55 ;; continueing the same logic, (add one two) => three
  56 ;; and inc applied three times to 1 is 4. This proves
  57 ;; that our definition of add is correct.
  58
  59 ;; I used the wikipedia article to study Church Numerals:
  60 ;; <http://en.wikipedia.org/wiki/Church_encoding#Computation_with_Church_numerals>
  61
  62 ;; comments?