The Y combinator in Python

I’ve been asked how would the Y combinator look like in Python (see comments of this post; comments are lost with the migration). In that post the Y combinator is also explained detailedly (and may be an interesting reading).

Python is an imperative language, however, its functions are first class citizens and can be manipulated in a quite functional way. We have closures, anonymous functions and recursion. That’s all we need to build the Y combinator in Python.

Moreover, the Y combinator in Python looks like a decorator. Quite unfortunately, using recursion in Python is usually a poor choice. Python has a rather low limit on recursive calls (and even if you can rise it, it’s not good programming practice).

In Python function calls are quite expensive and there is no tail recursion optimization.
Indeed, even though Python is great in manipulating functions (and is something I use relatively often), recursion should not the preferred method to loop. It’s much better to use iterators/generators in for loops ore as a second (usually inferior) choice, while loops.

However, this is the implementation of the Y combinator in Python (along with the traditional factorial example):

def y(f):
    def g(k):
        return f(lambda a: (k(k))(a))
    return g(g)

@y
def fact(h):
    def fact_aux(n):
        if n == 0:
            return 1
        else:
            return n * h(n-1)
    return fact_aux

print fact(5)