Skip to content

Instantly share code, notes, and snippets.

@zbskii
Created April 10, 2012 03:38
  • Star 1 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 zbskii/2348175 to your computer and use it in GitHub Desktop.
Y-Combinator
# -*- coding: utf-8 -*-
# a functional is a function that takes a function for its input
def fact(factorial):
def fn(n):
if n == 0: return 1
else:
return n * factorial(n - 1)
return fn
def fib1(fib):
def fn(n):
if n == 0: return 0
if n < 2: return 1
else:
return fib(n - 2) + fib(n - 1)
return fn
# Y = λf.(λx.f (x x)) (λx.f (x x))
# Computes the fixed point of a functional, Y(F) = F(Y(F))
def Y(f):
def inner(cc):
return f(lambda x: cc(cc)(x))
return inner(inner)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment