¿Haskell tiene optimización recursiva de cola?

Descubrí el comando "time" en Unix hoy y pensé en usarlo para verificar la diferencia en tiempos de ejecución entre funciones recursivas normales y recursivas de cola 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 usar con este proyecto, por lo que no me molesté en verificar si había ceros o números negativos.

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

Haskell usa la evaluación diferida para implementar la recursividad, por lo que trata cualquier cosa como una promesa de proporcionar un valor cuando sea necesario (esto se llama procesador). Los thunks se reducen solo lo necesario para continuar, no más. Esto se parece a la forma en que simplifica una expresión matemáticamente, por lo que es útil pensar en ello de esa manera. El hecho de que el código no especifique el orden de evaluación le permite al compilador realizar muchas optimizaciones aún más inteligentes que las eliminaciones de llamadas finales a las que está acostumbrado. Compile con -O2si desea optimización.

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

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, tal como le preocupaba, tenemos una acumulación de números antes de que ocurra cualquier cálculo, pero a diferencia de lo que le preocupaba, no hay una pila de facSlowllamadas a funciones esperando para terminar: cada reducción se aplica y desaparece, dejando un marco de pila en su wake (eso se debe a que (*)es estricto y, por lo tanto, desencadena la evaluación de su segundo argumento).

¡Las funciones recursivas de Haskell no se evalúan de una manera muy recursiva! La única pila de llamadas pendientes son las propias multiplicaciones. Si (*)se ve como un constructor de datos estricto, esto es lo que se conoce como recursividad protegida (aunque generalmente se la conoce como tal con los constructores de datos no estrictos, donde lo que queda a su paso son los constructores de datos, cuando son forzados por un acceso adicional).

Ahora echemos un vistazo a la cola recursiva fac 5:

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

Entonces puede ver cómo la recursividad de cola por sí sola no le ha ahorrado tiempo ni espacio. No solo toma más pasos en general 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 golpe seco y luego se deshizo por la que atraviesa que a la parte inferior, la recreación de la computación en la pila. Aquí también existe el peligro de provocar un desbordamiento de pila con cálculos muy largos, para ambas versiones.

Si queremos optimizar esto manualmente, todo lo que tenemos que hacer es hacerlo estricto. Puede utilizar el operador de aplicación estricto $!para 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 facS'a ser estricto en su segundo argumento. (Ya es estricto en su primer argumento porque debe evaluarse para decidir qué definición 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 desea optimizar su código, el primer paso es compilar con -O2
• La recursividad de cola solo es buena cuando no hay acumulación de thunk, y agregar rigor generalmente ayuda a prevenirla, si es apropiado. Esto sucede cuando está creando un resultado que se necesita más adelante de una vez.
• A veces, la recursividad de cola es un mal plan y la recursividad protegida es una mejor opción, es decir, cuando el resultado que está generando será necesario poco a poco, en porciones. Vea esta pregunta sobre foldry, foldlpor ejemplo, y compárelos entre sí.

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

foldl1es tail recursive, mientras que foldr1realiza una recursividad protegida para que el primer elemento se presente inmediatamente para su posterior procesamiento / acceso. _{(El primero "entre paréntesis" a la izquierda a la vez, (...((s+s)+s)+...)+sforzando su lista de entrada por completo hasta el final y construyendo un gran número de cálculos futuros mucho antes de que se necesiten sus resultados completos; el segundo entre paréntesis a la derecha gradualmente s+(s+(...+(s+s)...)), consumiendo la entrada lista poco a poco, por lo que todo puede funcionar en un espacio constante, con optimizaciones).}

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

Cabe mencionar que la facfunción no es un buen candidato para la recursividad protegida. La recursividad de cola es el camino a seguir aquí. Debido a la pereza, no está obteniendo el efecto de TCO en su fac'función porque los argumentos del acumulador siguen creando procesadores grandes, que cuando se evalúan requerirán una pila enorme. Para evitar esto y obtener el efecto deseado de TCO, debe hacer que estos argumentos acumuladores 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 usando -O2(o simplemente -O) GHC probablemente lo hará por sí solo en la fase de análisis de rigor .

Debería consultar el artículo de la wiki sobre recursividad de cola en Haskell . En particular, debido a la evaluación de expresiones, el tipo de recursividad que desea es recursividad protegida . Si averiguas los detalles de lo que está sucediendo bajo el capó (en la máquina abstracta de Haskell) obtienes el mismo tipo de cosas que con la recursividad de cola en lenguajes estrictos. Junto con esto, tiene una sintaxis uniforme para funciones perezosas (la recursividad de cola lo vinculará a una evaluación estricta, mientras que la recursividad protegida funciona de manera más natural).

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

Si mal no recuerdo, GHC optimiza automáticamente funciones recursivas simples en funciones optimizadas recursivas de cola.