espressioni lambda ricorsive possibili?

Question

Sto provando a scrivere un'espressione lambda che chiama se stessa, ma non riesco a trovare alcuna sintassi per quello, o anche se è possibile.

Essenzialmente quello che volevo trasferire la seguente funzione nella seguente espressione lambda: (mi rendo conto che è una domanda di stupido, si aggiunge solo, ma sto esplorando quello che posso fare con lambda-espressioni in Python)

def add(a, b): 
    if a <= 0: 
     return b 
    else: 
     return 1 + add(a - 1, b) 

add = lambda a, b: [1 + add(a-1, b), b][a <= 0] 

ma chiamando la forma lambda di aggiungi risultati in un errore di runtime perché viene raggiunta la profondità massima di ricorsione. È persino possibile farlo in python? O sto solo facendo un errore stupido? Oh, sto usando python3.0, ma non penso che dovrebbe essere importante?

Answer 1

Forse avete bisogno di un combinatore Y?

Modifica - fanno si che un combinatore Z (non si era reso conto che combinatori Y sono più per chiamata per nome)

Utilizzando la definizione del combinatore Z da Wikipedia

>>> Z = lambda f: (lambda x: f(lambda *args: x(x)(*args)))(lambda x: f(lambda *args: x(x)(*args))) 

Utilizzando questo, è possibile definire aggiungere come una funzione completamente anonima (cioè nessun riferimento al suo nome nella sua definizione)

>>> add = Z(lambda f: lambda a, b: b if a <= 0 else 1 + f(a - 1, b)) 
>>> add(1, 1) 
2 
>>> add(1, 5) 
6 

Answer 2

Prima di tutto le espressioni lambda ricorsive sono completamente inutili. Come tu stesso fai notare, perché l'espressione lambda possa chiamarsi, deve avere un nome. Ma le espressioni lambda non sono altro che funzioni anonime. Quindi se dai un nome a un'espressione lambda, non è più un'espressione lambda, ma una funzione.

Quindi, l'uso di un'espressione lambda è inutile e confonderebbe solo le persone. Quindi crealo con un def invece.

Ma sì, come hai scoperto tu stesso, le espressioni lambda possono essere ricorsive. Il tuo esempio è. In effetti è così straordinariamente ricorsivo che superi la massima profondità di ricorsione. Quindi è ricorsivo, va bene. Il tuo problema è che chiami sempre aggiungi nell'espressione, quindi la ricorsione non si ferma mai. Non farlo. La tua espressione può essere espressa in questo modo:

add = lambda a, b: a > 0 and (1 + add(a-1, b)) or b 

Che si prende cura di questo problema. Tuttavia, il tuo primo def è il modo corretto di farlo.

Answer 3

add = lambda a, b: b if a <= 0 else 1 + add(a - 1, b) 

Answer 4

Forse si dovrebbe provare il Z combinator, dove questo esempio è da:

>>> Z = lambda f: (lambda x: f(lambda *args: x(x)(*args)))(lambda x: f(lambda *args: x(x)(*args))) 
>>> fact = lambda f: lambda x: 1 if x == 0 else x * f(x-1) 
>>> Z(fact)(5) 
120 

Answer 5

Si desidera che il combinatore Y, o qualche altro fixed point combinator.

Ecco un esempio di implementazione come espressione Python lambda:

Y = lambda g: (lambda f: g(lambda arg: f(f)(arg))) (lambda f: g(lambda arg: f(f)(arg))) 

Utilizzare questo modo:

factorial = Y(lambda f: (lambda num: num and num * f(num - 1) or 1)) 

Cioè, si passa in Y() una funzione a singolo argomento (o lambda), che riceve come argomento una versione ricorsiva di se stesso.Quindi la funzione non ha bisogno di conoscere il proprio nome, poiché ottiene invece un riferimento a se stesso.

Nota che ciò risulta complicato per la funzione add() perché il combinatore Y supporta solo il passaggio di un singolo argomento. Puoi ottenere più argomenti per currying - ma lo lascerò come esercizio per il lettore. :-)

Answer 6

un po 'in ritardo ... ma ho appena trovato questo gioiello @http://metapython.blogspot.com/2010/11/recursive-lambda-functions.html

def myself (*args, **kw): 
    caller_frame = currentframe(1) 
    code = caller_frame.f_code 
    return FunctionType(code, caller_frame.f_globals)(*args,**kw) 

print "5! = " 
print (lambda x:1 if n <= 1 else myself(n-1)*n)(5)