Take the 2-minute tour ×

I am trying to learn about combinators and I am having trouble understand the example given at (Y overriding self-application). I think I am beginning to grasp the concept but I am still far from understanding.

I would like to translate the following code to Python:

     (define (U f) (f f))

     (define (fib-nr f)
       (lambda (n)
         (if (< n 2) 1 (+ ((f f) (- n 1)) ((f f) (- n 2))))))

     # Usage:   
     ((U fib-nr) 35) ;==> 14930352

I tried a 'literal' translation by writing:

U = lambda u: u(u)

def fibnr(f):
    return lambda n:  1 if (n<2) else (f (f (n-1))) + (f (f (n-2)))

But this doesnt work (I think it has to do with the order the functions are evaluated inside the lambda).

So I tried to use function composition as:

# http://code.activestate.com/recipes/52902-function-composition/
class compose:
    '''compose functions. compose(f,g,x...)(y...) = f(g(y...),x...))'''
    def __init__(self, f, g, *args, **kwargs):
        self.f = f
        self.g = g
        self.pending = args[:]
        self.kwargs = kwargs.copy()

        return self.f(self.g(*args, **kwargs), *self.pending, **self.kwargs)

U = lambda u: compose(u, u)

def fibnr(f):
    ff = compose(f, f)
    return lambda n:  1 if (n<2) else (ff (n-1)) + (ff (n-2))

But still didn't work, when calling my last snippet of code I get a lambda back:

>>> U(fibnr)(35)
<function <lambda> at 0x01A1B6B0>

So, is it possible to write a 'literal' translation of the given example in Python? How could I do it?

share|improve this question

1 Answer 1

up vote 3 down vote accepted

I wrote a simple translation that seems to produce correct results:

def U(f): return f(f)

def fibnr(f):
    def lam(n):
        if (n < 2): return 1
        return f(f)(n-1) + f(f)(n-2)
    return lam

Or if you really like lambdas:

def fibnr(f): return lambda n: 1 if (n < 2) else f(f)(n-1) + f(f)(n-2)

I think your initial problem was translating Lisp ((f f) x) into Python f(f(x)) instead of f(f)(x).

Good luck understanding combinators :)

share|improve this answer
Yes, you are totally right! I thought it had something to do with the ((f f) x) but I wasn't sure of what. I changed a bit my code to f(f)(x) and it worked. I took about 1 minute to compute U(fibnr)(35) from the python interpreter. –  JPCosta Jun 22 '10 at 22:07

Your Answer


