Combinateur U sur un fibonacci: comment traduiriez-vous ce code en python?

Question

J'essaie d'apprendre à propos des combinateurs et j'ai de la difficulté à comprendre l'exemple donné en (Y overriding self-application). Je pense que je commence à saisir le concept mais je suis encore loin de comprendre.

Je voudrais traduire le code suivant à 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 

J'ai essayé une traduction « littéral » en écrivant:

U = lambda u: u(u) 

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

Mais ce travail ne marche pas (je pense qu'il doit faire avec l'ordre, les fonctions sont évaluées à l'intérieur du lambda).

J'ai donc essayé d'utiliser la composition de fonction:

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

Mais ne fonctionnait toujours pas, lors de l'appel de mon dernier bout de code je reçois un lambda de retour:

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

Alors, -il possible d'écrire une traduction 'littérale' de l'exemple donné en Python? Comment pourrais-je le faire?

Answer 1

J'ai écrit une traduction simple qui semble produire des résultats corrects:

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 

Ou si vous aimez vraiment lambdas:

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

Je pense que votre problème initial a été traduit Lisp ((f f) x) en Python f(f(x)) au lieu de f(f)(x).

Bonne chance compréhension combinateurs :)