Church Numerals in Clojure

gistfile1.clj

; f -> x -> x
(def zero 
  (fn [f,x] x))

; 1: f -> x -> f(x)
(def one
 (fn [f,x] (f x)))

; 2: f -> x-> f(f(x))
(def two
 (fn [f,x] (f (f x))))

; f -> x -> f(n(f), x)
(defn succ [n]
 (fn [f,x] 
   (f (n f x))))

(def three 
  (succ two))

; a -> b -> (f -> x -> a(f,b(f,x)))
(defn add [a,b]
 (fn [f,x]
   (a f (b f x))
   ))

; just call a, b times
; a -> b -> (f -> x -> b(a(f),x))
(defn mult [a,b]
  (fn [f,x]
    (b (partial a f) x)))

((add one three) inc 0) -> 4
((mult one three) inc 0) -> 3
((mult three three) inc 0) -> 9

I had to de-curry some of the functions as all the partial applications were making my brain explode. In a Scheme, you wouldn't need the (partial) function for mult because functions are automatically partially applied when supplying less than the necessary args.

This was motivated by a problem from Structure and Interpretation of Computer Programs.