expresiones lambda recursivas posibles?

Question

Estoy tratando de escribir una expresión lambda que se llame a sí misma, pero no puedo encontrar ninguna sintaxis para eso, o incluso si es posible.

Esencialmente lo que quería transferir la función siguiente en la siguiente expresión lambda: (I cuenta de que es una aplicación de tonto, que sólo añade, pero estoy explorando lo que puedo hacer con lambda-expresiones en 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] 

pero llamando a la forma lambda de agregar resultados en un error de tiempo de ejecución porque se alcanza la profundidad máxima de recursión. ¿Es posible hacerlo en Python? ¿O solo estoy cometiendo un error estúpido? Oh, estoy usando python3.0, pero no creo que eso importe?

Answer 1

¿Tal vez necesita un combinador en Y?

Editar - hacer que un combinador Z (que no se había dado cuenta de que combinadores Y son más por llamada por nombre)

Usando la definición del combinador Z desde Wikipedia

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

uso de este, a continuación, puede definir agregar como una función totalmente anónima (es decir. no se hace referencia a su nombre en su definición)

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

En primer lugar, las expresiones lambda recursivas son completamente innecesarias. Como usted mismo señala, para que la expresión lambda se llame a sí misma, necesita tener un nombre. Pero las expresiones lambda no son más que funciones anónimas. Entonces, si le da un nombre a la expresión lambda, ya no es una expresión lambda, sino una función.

Por lo tanto, usar una expresión lambda es inútil, y solo confundirá a las personas. Así que créelo con una def en su lugar.

Pero sí, como usted mismo descubrió, las expresiones lambda pueden ser recursivas. Tu propio ejemplo es De hecho, es tan fantásticamente recursivo que excede la profundidad de recursión máxima. Entonces es recursivo bien Su problema es que siempre llama agregar en la expresión, por lo que la recursión nunca se detiene. No hagas eso. Su expresión se puede expresar así en su lugar:

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

que soluciona ese problema. Sin embargo, su primera definición es la forma correcta de hacerlo.

Answer 3

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

Answer 4

Tal vez debería probar el Z combinator, en este ejemplo es de:

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

Usted quiere que el combinador Y, o alguna otra fixed point combinator.

Aquí hay un ejemplo de implementación como una expresión lambda Python:

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

usarlo como así:

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

Es decir, se pasa en Y() una función de un solo argumento (o lambda), que recibe como argumento una versión recursiva de sí mismo.Por lo tanto, la función no necesita saber su propio nombre, ya que se convierte en una referencia a sí mismo.

Tenga en cuenta que esto se vuelve complicado para su función add() porque el combinador Y solo admite pasar un único argumento. Puede obtener más argumentos al currying, pero lo dejo como ejercicio para el lector. :-)

Answer 6

un poco tarde ... pero acabo de encontrar esta joya @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)