Another Clojure Y-Combinator

Another-Clojure-Y-Combinator.clj

;; Y-Combinator in Clojure
;; based on: http://mvanier.livejournal.com/2897.html

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

(defn part-fact
  [self n]
  (if (= n 0)
    1
    (* n (self self (dec n)))))
;; (part-fact part-fact 5) => 120


(defn part-fact2
  [self]
  (fn [n]
    (if (= n 0)
      1
      (* n ((self self) (dec n))))))
;; ((part-fact2 part-fact2) 5) => 120


(defn part-fact3
  [self]
  (let [f (self self)]
    (fn [n]
      (if (= n 0)
        1
        (* n (f (dec n)))))))

(defn fact3
  [n]
  ((part-fact3 part-fact3) n))
;; (fact2 5) => BOOM! stack overflow
;; due to (self self) outside of a func


;; To avoid stack overflow, delay evalution
;; of (self self) by burying it in a func.
(defn part-fact4
  [self]
  (let [f (fn [y] ((self self) y))]
    (fn [n]
     (if (= n 0)
       1
       (* n (f (dec n)))))))

(defn fact4
  [n]
  ((part-fact4 part-fact4) n))


;; factor out the factorial func
(defn almost-factorial
  [f]
  (fn [n]
    (if (= n 0)
      1
      (* n (f (dec n))))))

(defn part-fact5
  [self]
  (let [f (fn [y] ((self self) y))]
    (almost-factorial f)))

(defn fact5
  [n]
  ((part-fact5 part-fact5) n))


;; rewrite part-fact in place, similar to fact5
(def fact6
  (let [part-fact (fn [self]
                    (let [f (fn [y] ((self self) y))]
                      (almost-factorial f)))]
    (part-fact part-fact)))


;; require, replacing part-fact with x
(def fact7
  (let [x (fn [self]
            (let [f (fn [y] ((self self) y))]
              (almost-factorial f)))]
    (x x)))


;; let ==> lambda
(def fact8
  ((fn [x]
     (x x)) (fn [self]
              (let [f (fn [y] ((self self) y))]
                (almost-factorial f)))))

;; again replace self with x
(def fact9
  ((fn [x] (x x)) (fn [x]
                   (let [f (fn [y] ((x x) y))]
                     (almost-factorial f)))))


;; generalize it
(defn make-recursive
  [g]
  ((fn [x] (x x)) (fn [x]
                   (let [f (fn [y] ((x x) y))]
                     (g f)))))

(def fact10
  (make-recursive almost-factorial))


;; again replace let ==> lambda
;; And, the Y combinator!
(defn Y
  [g]
  ((fn [x] (x x)) (fn [x]
                   (g (fn [y] ((x x) y))))))

(defn factorial
  [n]
  ((Y almost-factorial) n))