haskell - recursivas - recursividad multiple ejemplos

Recursión de cola en Haskell

Question

Estoy tratando de entender la recursión de cola en Haskell. Creo que entiendo qué es y cómo funciona, pero me gustaría asegurarme de que no esté arruinando las cosas.

Aquí está la definición factorial "estándar":

factorial 1 = 1
factorial k = k * factorial (k-1)

Cuando se ejecuta, por ejemplo, factorial 3 , mi función se llamará a sí misma 3 veces (dar o tomar). Esto podría plantear un problema si quisiera calcular el factorial 99999999 ya que podría tener un desbordamiento de pila. Después de llegar al factorial 1 = 1 , tendré que "volver" en la pila y multiplicar todos los valores, así que tengo 6 operaciones (3 para llamar a la función en sí y 3 para multiplicar los valores).

Ahora les presento otra posible implementación factorial:

factorial 1 c = c
factorial k c = factorial (k-1) (c*k)

Este también es recursivo. Se llamará a sí mismo 3 veces. Pero no tiene el problema de tener que "regresar" para calcular las multiplicaciones de todos los resultados, ya que ya estoy pasando el resultado como argumento de la función.

Esto es, por lo que he entendido, de lo que se trata Turs Recursion. Ahora, parece un poco mejor que el primero, pero aún puede tener desbordamientos de pila con la misma facilidad. He oído que el compilador de Haskell convertirá las funciones recursivas de Tail en bucles entre bastidores. ¿Supongo que esa es la razón por la que vale la pena hacer funciones recursivas de la cola?

Si esa es la razón, entonces no hay absolutamente ninguna necesidad de intentar hacer que las funciones sean recursivas si el compilador no va a hacer este truco inteligente. ¿Tengo razón? Por ejemplo, aunque en teoría el compilador de C # podría detectar y convertir las funciones recursivas de la cola en bucles, sé (al menos es lo que he oído) que actualmente no hace eso. Por lo tanto, no tiene ningún sentido en la actualidad hacer que las funciones de la cola sean recursivas. ¿Es asi?

¡Gracias!

Answer 1

Debe usar los mecanismos incorporados, entonces no tiene que pensar en maneras de hacer que su función sea recursiva.

fac 0 = 1
fac n = product [1..n]

O si el producto no estaba definido:

fac n = foldl'' (*) 1 [1..n]

(vea http://www.haskell.org/haskellwiki/Foldr_Foldl_Foldl%27 sobre qué pliegue ... versión usar)

Answer 2

Hay dos problemas aquí. Una es la recursión de la cola en general, y la otra es cómo Haskell maneja las cosas.

Con respecto a la recursión de la cola, parece que tienes la definición correcta. La parte útil es que, dado que solo se necesita el resultado final de cada llamada recursiva, las llamadas anteriores no necesitan mantenerse en la pila. En lugar de "llamarse a sí misma", la función hace algo más parecido a "reemplazarse" a sí misma, que termina pareciéndose a un bucle iterativo. Esta es una optimización bastante sencilla que los compiladores decentes generalmente proporcionarán.

El segundo tema es la evaluación perezosa . Debido a que Haskell solo evalúa la expresión según sea necesario, la recursión de la cola por defecto no funciona de la forma habitual. En lugar de reemplazar cada llamada a medida que avanza, se acumula una enorme pila anidada de "thunks", es decir, expresiones cuyo valor aún no se ha solicitado. Si esta pila de procesador se hace lo suficientemente grande, producirá un desbordamiento de pila.

En realidad, hay dos soluciones en Haskell, dependiendo de lo que necesita hacer:

• Si el resultado consiste en constructores de datos anidados, como producir una lista, entonces usted quiere evitar la recursión de la cola; en lugar de poner la recursión en uno de los campos del constructor. Esto permitirá que el resultado también sea perezoso y no causará desbordamientos de pila.

• Si el resultado consiste en un solo valor, desea evaluarlo estrictamente , de modo que cada paso de la recursión sea forzado tan pronto como se necesite el valor final. Esto proporciona la pseudo iteración habitual que se esperaría de la recursión de la cola.

Además, tenga en cuenta que GHC es bastante inteligente y, si compila con optimizaciones, a menudo encontrará lugares donde la evaluación debe ser estricta y cuidarla por usted. Sin embargo, esto no funcionará en GHCi.