Small and pluggable Y combinator in clojure.

small-Y.clj

;; ; made this macro scraching my head between the simplicity of Haskell for fix
;; ; and the absence of curryfication in Clojure.

;; (P expr-fn) ; makes expr-fn lazy
;; (P P expr-fn) ; curry one time expr-fn
;; (P P P expr-fn) ; curry two time expr-fn
;; (= ((((P P P str) "a") "b") "c") "abc") ;=> true
(defmacro P [& f]
  (let [x (gensym 'x)] ;; cannot be replaced by x# due to nested macro expansion.
    `(fn[~x] (~@f ~x))))

(defn U [f]
  (P (f f)))

(defn Y [f]
  (U (comp (P P f) U)))


;; ; I don't really like Y combinator definition like
;; (defn fac [f] (fn [n] ,,, ))
(defn fac [f n]
  (if (zero? n) 1 (* n (f (dec n)))))


(defn fib [f n]
  (if (< n 2) 1
        (+ (f (- n 1))
           (f (- n 2)))))


((Y fac) 4)

((Y fib) 6)


;; ; inspiration from : http://www.viksit.com/tags/clojure/practical-applications-y-combinator-clojure/
;; ; and UM in this case

;; ; More generic Y combinator that can take an application function
(defn YM [ap f]
  (let [g (comp (P P f) U)]
    (g (comp (P P ap) g))))


;; ; example ap
(defn ap [f a] (f a))


(defn make-memoizer []
  (let [application-cache (atom {})]
    (fn [function arg]
        (if-let [result (@application-cache arg)]
                 result
          (let [result (function arg)]
            (swap! application-cache assoc arg result)
            result)))))


(time ((YM ap fib) 35))


(time ((YM (make-memoizer) fib) 35))