y_combinator.py

# Inspiration from http://matt.might.net/articles/implementation-of-recursive-fixed-point-y-combinator-in-javascript-for-memoization/

def y_comb(f):
    def outer(x):
        def inner(y):
            return (x(x))(y)
        return f(inner)

    return outer(outer)

## Anonymous form
# Y = lambda F: (lambda x: F(lambda y: (x(x))(y)))(lambda x: F(lambda y: (x(x))(y)))


def y_mem(f, cache=None):
    if cache is None:
        cache = {}

    def _(arg):
        try:
            return cache[arg]
        except KeyError:
            def __(n):
                return y_mem(f, cache)(n)
            answer = f(__)(arg)
            cache[arg] = answer
            return answer
    return _


@y_mem
def fib_gen(fib):
    def f(n):
        if n == 0:
            return 0
        if n == 1:
            return 1

        return fib(n-1)+fib(n-2)
    return f

print(fib_gen(200))