Create a gist now

Instantly share code, notes, and snippets.

;; Y combinator and fib in clojure
;; see also:
;; http://www.fatvat.co.uk/2009/04/understanding-y-combinator.html
;; ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-453.pdf p72
(defn Y [f]
((fn [g]
(f (g g)))
(fn [g]
(fn [x]
((f (g g)) x)))))
(defn fib [k]
((Y (fn [f]
(fn [n]
(cond
(= n 0) 0
(= n 1) 1
:else (+ (f (- n 1)) (f (- n 2))))))) k))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment