Some experiments with implementations of fixed point combinators in Python

fixed_point_combinators.py

from __future__ import print_function
from collections import defaultdict

import functools

def Y(f):
    @functools.wraps(f)
    def Yf(*args):
        return inner(*args)
    inner = f(Yf)
    return Yf


Y0 = lambda f: (lambda x: x(x))(lambda y: f(lambda *args: y(y)(*args)))

# without lambda expressions
def Y1(f):
    def recurse(x):
        return x(x)
    def Yf(y):
        def apply_args(*args):
            return y(y)(*args)
        return f(apply_args)
    return recurse(Yf)

# remove variable and apply recursion
def Y2(f):
    def Yf():
        def apply_args(*args):
            return Yf()(*args)
        return f(apply_args)
    return Yf()

# remove inner func
def Y3(f):
    def Yf(*args):
        return f(Yf)(*args)
    return f(Yf)

# memoizing version, works for fac fib and qsort
# doesn't mess up autodict b/c it's inner func has no args
# only works with hashable args (NOT for i.e. tuple(dict()))
def Y4(f):
    sub = {}
    def Yf(*args):
        if args:
            if not args in sub:
                ret = sub[args] = f(Yf)(*args)
            else:
                print('reusing', *args)
                ret = sub[args]
            return ret
        return f(Yf)()
    return f(Yf)

Y = Y4

# fac = lambda f: lambda n: (1 if n<2 else n*f(n-1))
@Y
def fac(f):
    def inner_fac(n):
        if n < 2:
            return 1
        else:
            return n * f(n - 1)
    return inner_fac

# fib = lambda f: lambda n: 0 if n == 0 else (1 if n == 1 else f(n-1) + f(n-2))
@Y
def fib(f):
    def inner_fib(n):
        if n > 1:
            return f(n-1) + f(n-2)
        else:
            return n
    return inner_fib

# autodict = lambda f: lambda: defaultdict(f)
@Y
def autodict(f):
    def inner_autodict():
        return defaultdict(f)
    return inner_autodict

# qsort = lambda h: lambda lst: (lst if len(lst) <= 1 else (
# h(tuple(item for item in lst if item < lst[0])) +
# (lst[0],)*lst.count(lst[0]) + h(tuple(item for item in lst if item > lst[0]))))
# doesn't randomize start point
@Y
def qsort(h):
    def inner_qsort(lst):
        if len(lst) < 2:
            return lst
        else:
            pivot = lst[0]
            return (h(tuple(i for i in lst if i < pivot)) +
                    (pivot,)*lst.count(pivot) +
                    h(tuple(i for i in lst if i > pivot)))
    return inner_qsort

d = autodict()
d['q']['w']['r'] = 777

print('fac', 5)
assert 120 == fac(5)
print('fac', 6)
assert 720 == fac(6)
print('fib', 10)
assert 55 == fib(10)
print('fib', 11)
assert 89 == fib(11)
print('autodict')
assert 777 == d['q']['w']['r']
print('qsort')
assert (1, 2, 2, 4, 7, 8) == qsort((2,4,2,7,1,8))
print('Success!')