performance - sobre - multiplos en haskell

La pereza y la recursividad de la cola en Haskell, ¿por qué se cuelga?

Question

Tengo esta función bastante simple para calcular la media de los elementos de una gran lista, usando dos acumuladores para mantener la suma hasta el momento y el recuento hasta el momento:

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 de la cola, y no habría ningún problema. Sin embargo, como Haskell es flojo, mi Google me ha llevado a entender que (s + x) y (l + 1) se transmitirán por la recursión como thunks. Entonces todo esto se bloquea y arde:

Stack space overflow: current size 8388608 bytes.

Después de buscar en Google, ¡encontré seq y $! . Lo cual parece que no entiendo porque todos mis intentos de usarlos en este contexto resultaron inútiles, con mensajes de error que dicen algo acerca de los tipos infinitos.

Finalmente encontré -XBangPatterns , que lo 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 también aprenda algo!)

Para que entiendas mi falta de comprensión, esto es lo que probé (el único intento que compilé, es decir):

go s l (x:xs) = go (seq s (s+x)) (seq l (l+1)) xs

Por lo que pude entender, seq debería forzar aquí la evaluación del argumento syl, evitando así el problema causado por los thunks. Pero todavía tengo un desbordamiento de pila.

Answer 1

He escrito mucho sobre esto:

• Real World Haskell, ch 24: control de evaluación
• En recursividad y rigor en Haskell

En primer lugar, sí, si desea solicitar una evaluación estricta de los acumuladores, use seq y quédese 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 rigurosidad se activará si proporciona algunas anotaciones de tipo y 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

Como ''Doble'' es un contenedor sobre el tipo atómico estricto Double #, con optimizaciones activadas 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 anterior de RWH.

Answer 2

La función seq fuerza la evaluación del 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, 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 enlace 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 (go (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 seq con los parámetros no evaluados todavía s y seq l (go (s+x) (l+1) xs) , la evaluación de los parámetros se difiere hasta el punto en que alguien realmente intenta acceder a sus valores

Ahora, seq puede forzar la evaluación de su primer parámetro antes de devolver el resto de la expresión. Entonces el próximo paso en la evaluación sería la segunda seq . Si las llamadas a seq están enterradas en alguna parte de algún parámetro, es posible que no se ejecuten durante un tiempo prolongado, lo que frustra su propósito.

Con las posiciones modificadas de las seq , el programa se ejecuta correctamente, sin utilizar cantidades excesivas de memoria.

Otra solución al problema sería simplemente habilitar optimizaciones en GHC cuando se compila el programa ( -O o -O2 ). El optimizador reconoce la pereza prescindible y produce código que no asigna memoria innecesaria.

Answer 3

Tiene razón en su comprensión de que seq s (s+x) obliga a la evaluación de s . Pero no fuerza s+x , por lo tanto, todavía estás creando thunks.

¡Usando $! puede forzar la evaluación de la suma (dos veces, para ambos argumentos). Esto logra el mismo efecto que usar 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) go $! (s+x) al equivalente de:

let y = s+x
in seq y (go y)

Por lo tanto, y se fuerza primero a la forma normal de la 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 tanto, y se evalúa por completo 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. Obtuve el mismo error cuando primero escribí tu programa :-)

Porque los $! el operador es asociativo correcto, sin paréntesis go $! (s+x) $! (l+1) go $! (s+x) $! (l+1) go $! (s+x) $! (l+1) significa lo mismo que: go $! ((s+x) $! (l+1)) go $! ((s+x) $! (l+1)) , lo cual es obviamente incorrecto.