Y Combinator in Python

ycombinator.py

# Y Combinator in Python
# See <http://d.hatena.ne.jp/nowokay/20090409#1239268405>

true  = lambda x: lambda y: x
false = lambda x: lambda y: y

# `bool` to `true|false`
#
# >>> boolean(3 < 4)(2)(5)
# 2
# >>> boolean(3 < 1)(2)(5)
# 5
boolean = lambda b: true if b else false

# Y Combinator
#
# >>> Y(lambda f: lambda n: n if n < 2 else f(n-1) + f(n-2))(7)
# Traceback (most recent call last):
#     ...
# RuntimeError: maximum recursion depth exceeded
Y = lambda f: (lambda x: f(x(x)))(lambda x: f(x(x)))

# Z Combinator
#
# Example: A recursive function to compute fibonacci numbers.
#
# >>> from * import ycombinator
# >>> Z(lambda f: lambda n: n if n < 2 else f(n-1) + f(n-2))(7)
# 13
# >>> Z(lambda f: lambda n: boolean(n < 2)(n)(f(n-1) + f(n-2)))(7)
# Traceback (most recent call last):
#     ...
# RuntimeError: maximum recursion depth exceeded
# >>> Z(lambda f: lambda n: boolean(n < 2)(lambda: n)(lambda: f(n-1) + f(n-2))())(7)
# 13
Z = lambda f: (lambda x: (lambda m: f(x(x))(m)))(lambda x: (lambda m: f(x(x))(m)))