python - ¿Expresiones lambda recursivas posibles?

recursion

Question

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

Esencialmente, lo que quería transferir la siguiente función a la siguiente expresión lambda: (Me doy cuenta de que es una aplicación tonta, solo agrega, pero estoy explorando qué puedo hacer con las expresiones lambda 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 llamar 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 incluso posible hacer esto en python? ¿O simplemente estoy cometiendo un error estúpido? Oh, estoy usando python3.0, pero no creo que eso deba importar.

Answer 1

¿Tal vez necesitas un combinador en Y?

Editar : haz que sea un combinador Z (no me había dado cuenta de que los combinadores Y son más para llamar por nombre)

Usando la definición del combinador Z de Wikipedia

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

Usando esto, puede definir agregar como una función completamente anónima (es decir, no hay 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

Desea el combinador de Y, o algún otro Wikipedia .

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

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

Úsalo así:

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

Es decir, se pasa a Y () una función de argumento único (o lambda), que recibe como argumento una versión recursiva de sí misma. Por lo tanto, la función no necesita conocer su propio nombre, ya que obtiene una referencia a sí misma en su lugar.

Tenga en cuenta que esto se complica para su función add () porque el combinador Y solo admite la transmisión de un solo argumento. Puedes obtener más argumentos al currying , pero dejaré eso como un ejercicio para el lector. :-)

Answer 3

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, debe tener un nombre. Pero las expresiones lambda no son más que funciones anónimas. Entonces, si le das 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 crealo con una definición 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 máxima de recursión. Así que es recursivo, está bien. Su problema es que siempre se llama agregar en la expresión, por lo que la recursión nunca se detiene. No hagas eso Tu expresión se puede expresar así en su lugar:

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

Que se encarga de ese problema. Sin embargo, tu primera definición es la forma correcta de hacerlo.

Answer 4

Quizás deberías probar el Wikipedia , de donde viene este ejemplo:

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

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

Answer 6

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