Skip to content

Instantly share code, notes, and snippets.

@alandipert
Created January 3, 2010 18:56
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save alandipert/268082 to your computer and use it in GitHub Desktop.
;; 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