Last active
February 16, 2018 14:10
-
-
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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