Y-Combinator in Clojure

gistfile1.clj

(ns dynamacros.fib)

;; Y-Combinator in Clojure
;; Based on http://citizen428.net/blog/2010/12/14/clojure-deriving-the-y-combinator-in-7-stolen-steps/

;; This is the simple naive implementation.
(defn simple-factorial
  "A simple, naive implementation of the factorial function."
  [n]
  (if (= n 0)
    1
    (* n (simple-factorial (dec n)))))
;; (simple-factorial 5) => 120


;; This is one that doesn't blow the stack.
(defn recur-factorial
  "Factorial with semi-optimized tail-recursion."
  [x]
  (loop [n x s 1]
    (if (= n 0)
      s
      (recur (dec n) (*' s n)))))
;; (recur-factorial 5) => 120


;; This is one that doesn't use explicit recursion.
(defn calls-itself-fact
  "A factorial that calls itself.
   ((f f) n)"
  [f]
  (fn [n]
    (if (< n 2)
      1
      (* n ((f f) (dec n))))))
;; ((calls-itself-fact calls-itself-fact) 5)


;; Further abstracting out the recursion.
(defn yrecur
  [f]
  (f f))

(def yrecur-fact
  (yrecur (fn [f]
            (fn [n]
              (if (< n 2)
                1
                (* n ((f f) (dec n))))))))
;; (yrecur-fact 5) => 120


;; Factor out the yrecur, and make it look like the basic factorial function.
(defn wrap
  [h]
  (yrecur
   (fn [f]
     (let [g (fn [n]
               ((f f) n))]
       (h g)))))

(def wrap-fact
  (wrap
   (fn [g]
     (fn [n]
       (if (< n 2)
         1
         (* n (g (dec n))))))))
;; (wrap-fact 5) => 120


;; Inline the "g"
(defn wrap2
  [h]
  (yrecur
   (fn [f]
     (h (fn [n]
          ((f f) n))))))

(def wrap2-fact
  (wrap2
   (fn [g]
     (fn [n]
       (if (< n 2)
         1
         (* n (g (dec n))))))))
;; (wrap2-fact 5) => 120


;; Inline yrecur and wrap2 and you get the Y Combinator!
(defn Y
  [h]
  ((fn [f]
     (f f)) (fn [f]
              (h (fn [n]
                   ((f f) n))))))

(def fact
  (Y (fn [g]
       (fn [n]
         (if (< n 2)
           1
           (* n (g (dec n))))))))
;; It works
;; (fact 5) => 120