church_numerals.clj

; Church Numerals in Clojure
;
; Church numerals use anonymous functions to represent numbers.
;
; ((zero f) x) -- returns x
; ((one f)  x) -- return (f x)
; ((two f)  x) -- return (f (f x))
; ...

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

; incr increments church numeral n by return a function that applies f
; one more time than n.
(defn incr [n] (fn [f] (fn [x] (f ((n f) x)))))

; Here's an easy way to test if a church numeral is zero.
(defn zero-cn? [n] ((n (fn [x] false)) true) )

; Add two church numerals to produce a new church numeral.
(defn +cn [a b]
  (fn [f] (fn [x] ((a f) ((b f) x)))))