Skip to content

Instantly share code, notes, and snippets.

@cbeuw
Last active February 16, 2018 14:10
Show Gist options
  • Save cbeuw/c45e77c6dc5e8c9bca47d6ad4be64d8c to your computer and use it in GitHub Desktop.
Save cbeuw/c45e77c6dc5e8c9bca47d6ad4be64d8c to your computer and use it in GitHub Desktop.
Anonymous Y combination implementation for Python. Derived from https://rosettacode.org/wiki/Y_combinator#Python but more elegant
Y = lambda f:(lambda y: f(lambda n: y(y)(n)))(lambda y: f(lambda n: y(y)(n)))
"""
Proof:
Y = lambda f:(lambda y: f(lambda n: y(y)(n)))
(lambda y: f(lambda n: y(y)(n)))
Y(g) = (lambda y: g(lambda n: y(y)(n))
(lambda y: g(lambda n: y(y)(n))
Y(g) = g(
lambda n: (
(lambda y: g(lambda n: y(y)(n)))
(lambda y: g(lambda n: y(y)(n)))
)(n))
)
Y(g) = g(
(lambda y: g(lambda n: y(y)(n)))
(lambda y: g(lambda n: y(y)(n)))
)
Y(g) = g(Y(g))
"""
# Factorial example
fac = lambda g:lambda i: 1 if i==1 else i*g(i-1)
# 6!
print(Y(fac)(6))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment