recursión de cola en Haskell

Question

estoy tratando de entender la recursividad de cola en Haskell. Creo que entiendo de qué se trata y cómo funciona, pero me gustaría asegurarme de no estropear las cosas.

Aquí es el "estándar" definición de factorial:

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

Cuando se ejecuta, por ejemplo, factorial 3, mi función asume el nombre de 3 veces (darle más o menos). Esto podría plantear un problema si quisiera calcular factorial 99999999 ya que podría tener un desbordamiento de pila. Después llego a factorial 1 = 1 voy a tener que "volver" en la pila y multiplicar todos los valores, por lo que tengo 6 operaciones (3 por llamar a la función en sí y 3 para multiplicar los valores).

Ahora les presento otra posible aplicación factorial:

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

Ésta es recursivo, también. Se llamará a sí mismo 3 veces. Pero no tiene el problema de tener que "volver" 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 Tail Recursion. Ahora, parece un poco mejor que el primero, pero igual puede tener desbordamientos de pila tan fácilmente. He oído que el compilador de Haskell convertirá las funciones recursivas de cola en bucles for the behind. Supongo que esa es la razón por la que vale la pena hacer las funciones recursivas de la cola.

Si ese es el motivo, entonces no hay necesidad de tratar de hacer las funciones recursivas si el compilador no va a hacer este truco inteligente, ¿estoy en lo cierto? Por ejemplo, aunque en teoría el compilador de C# podía detectar y convertir las funciones recursivas de la cola en bucles, sé (al menos es lo que he escuchado) que actualmente no lo hace. Por lo tanto, no tiene ningún sentido hoy en día hacer que las funciones sean recursivas. ¿Es asi?

Gracias!

Answer 1

Hay dos problemas aquí. Uno es la recursividad de cola en general, y el otro es cómo maneja Haskell las cosas.

En cuanto a la recursividad de cola, parece que tiene 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í mismo", la función hace algo más parecido a "reemplazarse", lo que termina pareciendo un ciclo iterativo. Esta es una optimización bastante directa que generalmente proporcionan los compiladores decentes.

El segundo problema es evaluación floja. Debido a que Haskell solo evalúa la expresión según sea necesario, de manera predeterminada, la recursión de cola no funciona del modo habitual. En lugar de reemplazar cada llamada a medida que avanza, crea una gran pila anidada de "thunks", es decir, expresiones cuyo valor no se ha solicitado aún. Si esta pila de procesador aumenta lo suficiente, producirá un desbordamiento de la pila.

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

• Si el resultado consiste en constructores de datos anidados - al igual que la producción de una lista - entonces usted quiere evitar recursividad de la cola; en su lugar ponga la recursión en uno de los campos de constructor. Esto permitirá que el resultado también sea flojo y no cause desbordamientos de pila.

• Si el resultado consiste en un único valor, desea evaluarlo estrictamente, de modo que cada paso de la recursión se fuerce tan pronto como se necesite el valor final. Esto le da la pseudo-iteración habitual que esperaría de la recursividad final.

Además, tenga en cuenta que GHC es bastante maldito inteligente y, si se compila con optimizaciones, a menudo detectar lugares donde la evaluación debe ser estricta y cuidar de él para usted. Sin embargo, esto no funcionará en GHCi.

Answer 2

Debe utilizar los mecanismos incorporados, entonces usted no tiene que pensar en maneras de hacer su función recursiva de cola

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

O si el producto no se ya definido:

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

(ver http://www.haskell.org/haskellwiki/Foldr_Foldl_Foldl%27 que se pliegan sobre ... versión utilizar)