Skip to content

Instantly share code, notes, and snippets.

@tianyicui
Created March 25, 2011 02:56
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save tianyicui/886292 to your computer and use it in GitHub Desktop.
Save tianyicui/886292 to your computer and use it in GitHub Desktop.
Deriving Y combinator in Scheme
(define fact0
(lambda (n)
(if (= n 0)
1
(* n (fact0 (- n 1))))))
(define fact1
(let
((g
(lambda (h)
(lambda (n)
(if (= n 0)
1
(* n ((h h) (- n 1))))))))
(g g)))
(define fact2
(let
((g
(lambda (h)
(lambda (n)
(let
((f
(lambda (q)
(lambda (n)
(if (= n 0)
1
(* n (q (- n 1))))))))
((f (h h)) n))))))
(g g)))
(define fact3
(let
((y
(lambda (f)
(let
((g
(lambda (h)
(lambda (n)
((f (h h)) n)))))
(g g)))))
(y
(lambda (q)
(lambda (n)
(if (= n 0)
1
(* n (q (- n 1)))))))))
(define Y
(lambda (h)
(let
((g
(lambda (f)
(lambda (n)
((h (f f)) n)))))
(g g))))
(define fact4
(Y
(lambda (f)
(lambda (n)
(if (= n 0)
1
(* n (f (- n 1))))))))
(define fib
(Y
(lambda (f)
(lambda (n)
(if (<= n 1)
1
(+ (f (- n 1)) (f (- n 2))))))))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment