La pereza y la recursión de la cola en Haskell, ¿por qué se está estrellando?
-
06-07-2019 - |
Pregunta
Tengo esta función bastante simple para calcular la media de los elementos de una gran lista, usando dos acumuladores para contener la suma hasta ahora y el recuento hasta ahora:
mean = go 0 0
where
go s l [] = s / fromIntegral l
go s l (x:xs) = go (s+x) (l+1) xs
main = do
putStrLn (show (mean [0..10000000]))
Ahora, en un lenguaje estricto, esto sería recursivo, y no habría ningún problema. Sin embargo, como Haskell es perezoso, mi búsqueda en Google me ha llevado a comprender que (s + x) y (l + 1) pasarán por la recursión como thunks. Así que todo esto se estrella y se quema:
Stack space overflow: current size 8388608 bytes.
Después de buscar en Google, encontré seq
y $!
. Parece que no lo entiendo porque todos mis intentos de usarlos en este contexto resultaron inútiles, con mensajes de error que dicen algo sobre tipos infinitos.
Finalmente encontré -XBangPatterns
, que resuelve todo cambiando la llamada recursiva:
go !s !l (x:xs) = go (s+x) (l+1) xs
Pero no estoy contento con esto, ya que -XBangPatterns
es actualmente una extensión. Me gustaría saber cómo hacer que la evaluación sea estricta sin el uso de -XBangPatterns
. (¡Y tal vez aprender algo también!)
Para que entiendas mi falta de comprensión, esto es lo que intenté (el único intento que compiló, eso es):
go s l (x:xs) = go (seq s (s+x)) (seq l (l+1)) xs
Por lo que pude entender, a continuación, se debe forzar la evaluación del argumento s y l, evitando así el problema causado por los thunks. Pero todavía tengo un desbordamiento de pila.
Solución
He escrito mucho sobre esto:
Primero, sí, si desea exigir una evaluación estricta de los acumuladores, utilice seq
y permanezca en Haskell 98:
mean = go 0 0
where
go s l [] = s / fromIntegral l
go s l (x:xs) = s `seq` l `seq`
go (s+x) (l+1) xs
main = print $ mean [0..10000000]
*Main> main
5000000.0
En segundo lugar: el análisis de rigor se activará si se dan algunas anotaciones de tipo y se compila con -O2:
mean :: [Double] -> Double
mean = go 0 0
where
go :: Double -> Int -> [Double] -> Double
go s l [] = s / fromIntegral l
go s l (x:xs) = go (s+x) (l+1) xs
main = print $ mean [0..10000000]
$ ghc -O2 --make A.hs
[1 of 1] Compiling Main ( A.hs, A.o )
Linking A ...
$ time ./A
5000000.0
./A 0.46s user 0.01s system 99% cpu 0.470 total
Debido a que 'Double' es una envoltura sobre el tipo atómico Doble #, con optimizaciones y un tipo preciso, GHC ejecuta un análisis de rigor e infiere que la versión estricta estará bien.
import Data.Array.Vector
main = print (mean (enumFromToFracU 1 10000000))
data Pair = Pair !Int !Double
mean :: UArr Double -> Double
mean xs = s / fromIntegral n
where
Pair n s = foldlU k (Pair 0 0) xs
k (Pair n s) x = Pair (n+1) (s+x)
$ ghc -O2 --make A.hs -funbox-strict-fields
[1 of 1] Compiling Main ( A.hs, A.o )
Linking A ...
$ time ./A
5000000.5
./A 0.03s user 0.00s system 96% cpu 0.038 total
Como se describe en el capítulo de RWH anterior.
Otros consejos
La función seq
obliga a evaluar el primer parámetro una vez que se llama a la función. Cuando pasa seq s (s + x)
como parámetro, la función seq
no se llama inmediatamente no , porque no hay necesidad de evaluar el Valor de ese parámetro. Desea que la llamada a seq
se evalúe antes de la llamada recursiva, para que a su vez pueda forzar la evaluación de su parámetro.
Por lo general, esto se hace vincular esto:
go s l (x:xs) = s `seq` l `seq` go (s+x) (l+1) xs
Esta es una variación sintáctica de seq s (seq l (ir (s + x) (l + 1) xs))
. Aquí las llamadas a seq
son las llamadas de función más externas en la expresión. Debido a la pereza de Haskell, esto hace que se evalúen primero: se llama a seq
con los parámetros aún sin evaluar s
y seq l (go (s + x) (l +1) xs)
, la evaluación de los parámetros se aplaza hasta el punto en que alguien intenta acceder a sus valores.
Ahora seq
puede hacer que se evalúe su primer parámetro antes de devolver el resto de la expresión. Luego, el siguiente paso en la evaluación sería el segundo seq
. Si las llamadas a seq
están enterradas en algún lugar de algún parámetro, es posible que no se ejecuten durante mucho tiempo, lo que anula su propósito.
Con las posiciones cambiadas de los seq
s, el programa se ejecuta bien, sin utilizar cantidades excesivas de memoria.
Otra solución al problema sería simplemente habilitar las optimizaciones en GHC cuando se compile el programa ( -O
o -O2
). El optimizador reconoce la pereza prescindible y produce un código que no asigna memoria innecesaria.
Tiene razón en su entendimiento de que seq s (s + x)
obliga a la evaluación de s
. Pero no obliga a s + x
, por lo que aún estás acumulando trucos.
Al utilizar $!
puede forzar la evaluación de la adición (dos veces, para ambos argumentos). Esto logra el mismo efecto que usando los patrones de explosión:
mean = go 0 0
where
go s l [] = s / fromIntegral l
go s l (x:xs) = ((go $! s+x) $! l+1) xs
El uso de la función $!
traducirá el go $! (s + x)
al equivalente de:
let y = s+x
in seq y (go y)
Por lo tanto, y
se fuerza primero en forma normal de cabeza débil , lo que significa que se aplica la función más externa. En el caso de y
, la función más externa es +
, por lo que y
se evalúa completamente a un número antes de pasar a go .
Ah, y probablemente recibiste el mensaje de error de tipo infinito porque no tenías el paréntesis en el lugar correcto. Recibí el mismo error cuando escribí por primera vez su programa :-)
Debido a que el operador $!
es asociativo correcto, sin paréntesis go $! (s + x) $! (l + 1)
significa lo mismo que: go $! ((s + x) $! (l + 1))
, que obviamente es incorrecto.