A demonstration of usage of the Z fixed point combinator in Python

gistfile1.py

In [1]: # Our definition of fib

In [2]: fib = lambda f: lambda n: 1 if n in (0, 1) else f(n - 1) + f(n - 2)

In [3]: # The Z fixpoint combinator

In [4]: Z = lambda f: (lambda x: f(lambda *args: x(x)(*args)))(lambda x: f(lambda *args: x(x)(*args)))

In [5]: # Works as expected

In [6]: Z(fib)(10)
Out[6]: 89

In [7]: # A fixpointcombinator-compatible memoization decorator

In [8]: def memoized(fun, memory):
   ...:     def inner1(f):
   ...:         def inner2(i):
   ...:             if i in memory:
   ...:                 return memory[i]
   ...:             value = memory[i] = fun(f)(i)
   ...:             return value
   ...:         return inner2
   ...:     return inner1
   ...: 

In [9]: # Create a cache (normally you'd create this inside memoize but then we can't peek inside)

In [10]: my_memory = dict()

In [11]: # Create the memoizing function (apply memoized on fib, passing in the memory)

In [12]: memoized_fib = memoized(fib, my_memory)

In [13]: type(memoized_fib)

Out[13]: <type 'function'>

In [14]: # And run the whole thing

In [15]: Z(memoized_fib)(10)
Out[15]: 89

In [16]: # Inspect the generated cache, looks ok!

In [17]: print my_memory
------> print(my_memory)
{0: 1, 1: 1, 2: 2, 3: 3, 4: 5, 5: 8, 6: 13, 7: 21, 8: 34, 9: 55, 10: 89}

In [18]: %timeit Z(fib)(200)

In [19]: # I was too optimistic and had to ^C the previous :-D

In [20]: %timeit Z(fib)(25)
1 loops, best of 3: 537 ms per loop

In [21]: %timeit Z(fib)(28)
1 loops, best of 3: 2.25 s per loop

In [22]: # Even Z(fib)(50) made my CPU go crazy, anyway... Create a memoize testcase

In [23]: def test_memoized(n):
   ....:     the_memory = dict()
   ....:     the_fun = memoized(fib, the_memory)
   ....:     return Z(the_fun)(n)
   ....: 

In [24]: # And test the thing

In [25]: %timeit test_memoized(28)
10000 loops, best of 3: 177 us per loop

In [26]: %timeit test_memoized(10)
10000 loops, best of 3: 63.7 us per loop

In [27]: %timeit Z(fib)(10)
1000 loops, best of 3: 393 us per loop

In [28]: %timeit test_memoized(50)
1000 loops, best of 3: 314 us per loop

In [29]: %timeit test_memoized(100)
1000 loops, best of 3: 645 us per loop

In [30]: %timeit test_memoized(200)
1000 loops, best of 3: 1.37 ms per loop

In [31]: # Go figure... Remember even Z(fib)(50) was too heavy?

In [32]: # Note we added memoization to the recursive fib() implementation without ever re-implementing fib() or changing anything to the implementation!