recursivas - ¿Tiene Haskell una optimización recursiva de la cola?

funciones recursivas ejemplos (4)

Cabe mencionar que la función fac no es un buen candidato para la recursión protegida. La recurrencia de la cola es el camino a seguir aquí. Debido a la pereza, no está obteniendo el efecto de TCO en la función fac'' porque los argumentos del acumulador siguen generando grandes thunks, que cuando se evalúan requerirán una enorme pila. Para evitar esto y obtener el efecto deseado de TCO, es necesario que estos argumentos del acumulador sean estrictos.

{-# LANGUAGE BangPatterns #-} fac :: (Integral a) => a -> a fac x = fac'' x 1 where fac'' 1 y = y fac'' x !y = fac'' (x-1) (x*y)

Si compila con -O2 (o solo -O ), es probable que GHC lo haga solo en la fase de análisis de rigor .

Descubrí el comando "tiempo" en Unix hoy y pensé que lo usaría para verificar la diferencia en los tiempos de ejecución entre las funciones recursivas recursivas y recursivas normales en Haskell.

Escribí las siguientes funciones:

--tail recursive fac :: (Integral a) => a -> a fac x = fac'' x 1 where fac'' 1 y = y fac'' x y = fac'' (x-1) (x*y) --normal recursive facSlow :: (Integral a) => a -> a facSlow 1 = 1 facSlow x = x * facSlow (x-1)

Estos son válidos, teniendo en cuenta que eran únicamente para el uso con este proyecto, por lo que no me molesté en buscar ceros o números negativos.

Sin embargo, al escribir un método principal para cada uno, compilarlos y ejecutarlos con el comando "tiempo", ambos tenían tiempos de ejecución similares con la función recursiva normal superando el recursivo de la cola. Esto es contrario a lo que había escuchado con respecto a la optimización recursiva de la cola en lisp. ¿Cuál es el motivo de esto?

Deberías echarle un vistazo al artículo de la wiki sobre la recursividad de la cola en Haskell . En particular, debido a la evaluación de la expresión, el tipo de recursión que desea es recursión protegida . Si resuelve los detalles de lo que ocurre debajo del capó (en la máquina abstracta de Haskell) obtiene el mismo tipo de cosas que con la recursividad de cola en lenguajes estrictos. Junto con esto, tiene una sintaxis uniforme para las funciones perezosas (la recursividad de cola lo vinculará a una evaluación estricta, mientras que la recursión protegida funciona de forma más natural).

(¡Y al aprender Haskell, el resto de esas páginas de wiki también son increíbles!)

Haskell utiliza la evaluación diferida para implementar la recursión, por lo que trata cualquier cosa como una promesa de proporcionar un valor cuando sea necesario (esto se conoce como "thunk"). Los thunk se reducen solo tanto como sea necesario para continuar, nada más. Esto se asemeja a la forma en que simplifica una expresión matemáticamente, por lo que es útil pensar de esa manera. El hecho de que la orden de evaluación no esté especificada por su código le permite al compilador hacer muchas optimizaciones aún más inteligentes que solo la eliminación de la llamada final que usted está acostumbrado. ¡Compila con -O2 si quieres optimización!

Veamos cómo evaluamos facSlow 5 como un estudio de caso:

facSlow 5 5 * facSlow 4 -- Note that the `5-1` only got evaluated to 4 5 * (4 * facSlow 3) -- because it has to be checked against 1 to see 5 * (4 * (3 * facSlow 2)) -- which definition of `facSlow` to apply. 5 * (4 * (3 * (2 * facSlow 1))) 5 * (4 * (3 * (2 * 1))) 5 * (4 * (3 * 2)) 5 * (4 * 6) 5 * 24 120

Así que, como te preocupaba, tenemos una acumulación de números antes de que ocurra cualquier cálculo, pero a diferencia de ti, no hay una pila de facSlow función facSlow pendientes esperando terminar: cada reducción se aplica y se va, dejando un marco de pila en su estela (eso es porque (*) es estricta y desencadena la evaluación de su segundo argumento).

¡Las funciones recursivas de Haskell no se evalúan de manera recursiva! La única pila de llamadas que acechan son las multiplicaciones mismas. Si (*) se ve como un constructor de datos estricto, esto es lo que se conoce como recursión protegida (aunque normalmente se conoce como tal con constructores de datos no restringidos, donde lo que queda son los constructores de datos, cuando se ve forzado por más acceso).

Ahora veamos el fac 5 recursivo de cola:

fac 5 fac'' 5 1 fac'' 4 {5*1} -- Note that the `5-1` only got evaluated to 4 fac'' 3 {4*{5*1}} -- because it has to be checked against 1 to see fac'' 2 {3*{4*{5*1}}} -- which definition of `fac''` to apply. fac'' 1 {2*{3*{4*{5*1}}}} {2*{3*{4*{5*1}}}} -- the thunk "{...}" (2*{3*{4*{5*1}}}) -- is retraced (2*(3*{4*{5*1}})) -- to create (2*(3*(4*{5*1}))) -- the computation (2*(3*(4*(5*1)))) -- on the stack (2*(3*(4*5))) (2*(3*20)) (2*60) 120

Para que pueda ver cómo la recursividad de la cola en sí misma no le ha ahorrado tiempo ni espacio. No solo facSlow 5 más pasos que facSlow 5 , sino que también crea un procesador anidado (que se muestra aquí como {...} ), que necesita un espacio adicional para él, que describe el cálculo futuro, las multiplicaciones anidadas que se realizarán.

Este thunk se desenreda al atravesarlo hacia abajo, recreando el cálculo en la pila. Aquí también existe el peligro de causar un desbordamiento de la pila con cálculos muy largos, para ambas versiones.

Si queremos optimizar a mano esto, todo lo que tenemos que hacer es hacerlo estricto. ¡Podría usar el operador de aplicación estricta $! definir

facSlim :: (Integral a) => a -> a facSlim x = facS'' x 1 where facS'' 1 y = y facS'' x y = facS'' (x-1) $! (x*y)

Esto obliga a facS'' a ser estricto en su segundo argumento. (Ya es estricto en su primer argumento porque debe evaluarse para decidir qué definición de facS'' aplicar).

A veces el rigor puede ayudar enormemente, a veces es un gran error porque la pereza es más eficiente. Aquí es una buena idea:

facSlim 5 facS'' 5 1 facS'' 4 5 facS'' 3 20 facS'' 2 60 facS'' 1 120 120

Que es lo que querías lograr, creo.

Resumen

Si quiere optimizar su código, el primer paso es compilar con -O2
La recursividad de cola solo es buena cuando no hay una acumulación de thunk, y agregar rigidez suele ayudar a prevenirla, si es necesario. Esto sucede cuando se está creando un resultado que se necesita más adelante a la vez.
A veces, la recursividad de la cola es un mal plan y la recursión protegida es una mejor opción, es decir, cuando el resultado que se está creando se necesitará poco a poco, en porciones. Consulte esta pregunta sobre foldr y foldl por ejemplo, y foldl uno contra el otro.

Prueba estos dos:

length $ foldl1 (++) $ replicate 1000 "The size of intermediate expressions is more important than tail recursion." length $ foldr1 (++) $ replicate 1000 "The number of reductions performed is more important than tail recursion!!!"

foldl1 es cola recursiva, mientras que foldr1 realiza recursión protegida para que el primer artículo se presente inmediatamente para su posterior procesamiento / acceso. _{(El primer "paréntesis" a la izquierda de una vez, (...((s+s)+s)+...)+s , forzando su lista de entrada completamente hasta su final y construyendo un gran golpe de computación futura mucho antes de que se necesiten sus resultados completos, el segundo paréntesis a la derecha gradualmente, s+(s+(...+(s+s)...)) , consumiendo la lista de entrada poco a poco, por lo que todo es capaz de operar en espacio constante, con optimizaciones).}

Es posible que deba ajustar el número de ceros según el hardware que esté utilizando.

Si recuerdo correctamente, GHC automáticamente optimiza las funciones recursivas simples en las recursivas optimizadas para la cola.