T en un combinador de Fibonacci: ¿cómo se traduce este código para Python?

Question

Estoy tratando de aprender acerca de combinadores y estoy teniendo problemas para entender el ejemplo dado en ( Y imperiosas de auto-aplicación ). Creo que estoy empezando a comprender el concepto pero todavía estoy lejos de comprender.

Me gustaría traducir el código siguiente para 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

He intentado un 'literal' de traducción al escribir:

U = lambda u: u(u)

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

Pero esto no funciona (creo que tiene que ver con el orden de las funciones se evalúan dentro de la lambda).

Así que traté de usar la composición de funciones como:

# 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()

    def __call__(self, *args, **kwargs):
        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))

Sin embargo, aún no funcionaba, al llamar a mi último fragmento de código consigo una copia lambda:

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

Entonces, ¿es posible escribir un 'literal' de traducción del ejemplo dado en Python? ¿Cómo podría hacerlo?

Answer 1

Me escribió una traducción simple que parece producir resultados correctos:

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

O si realmente te gusta lambdas:

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

Creo que su problema inicial fue la traducción de Lisp ((f f) x) en Python f(f(x)) en lugar de f(f)(x).

Buena suerte combinadores comprensión:)