Pereza y recursividad de cola en Haskell, ¿por qué se cuelga?

Question

tengo esta función bastante simple para calcular la media de los elementos de una lista grande, con 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 recursivo de la cola, y no habría 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. Así que todo esto esta cosa accidentes y quemaduras:

Stack space overflow: current size 8388608 bytes. 

Tras Google aún más, he encontrado 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 resuelve todo cambiando la llamada recursiva:

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

, pero no estoy feliz con esto, como -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 demasiado)

Para que lo entienda mi falta de entendimiento, esto es lo que he intentado (el único try que compilado, se entiende):

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

Por lo que pude entender, SEC debería 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.

Answer 1

He escrito extensamente sobre esto:

• Real World Haskell, ch 24: controlling evaluation
• On recursion and strictness in Haskell

En primer lugar, si, si desea requerir una evaluación estricta de los acumuladores utilizan seq y permanecer 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 entrará en funcionamiento si se le da algunas anotaciones de tipos, y compilar 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 'Doble' es un envoltorio sobre el tipo estricta atómica doble #, con optimizaciones, y una precisa tipo, GHC ejecuta el 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

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

Al usar $! puede forzar la evaluación de la suma (dos veces, para ambos argumentos).Esto logra el mismo efecto que el uso de 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) 

Así y es forzado primero en cabeza débil forma normal, 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 en un número antes de pasarse al go.

---

Ah, y es probable que recibió el mensaje de error de tipo infinito debido a que no tiene el paréntesis en el lugar correcto. Tengo el mismo error cuando escribí por primera vez el programa de abajo :-)

Debido a que el operador es asociativo $! derecha, sin paréntesis go $! (s+x) $! (l+1) significa lo mismo que: go $! ((s+x) $! (l+1)), que es obviamente erróneo.

Answer 3

La función seq fuerza la evaluación del primer parámetro una vez que se llama a la función. Cuando pase seq s (s+x) como parámetro, la función seq es no llamada inmediata, porque no hay necesidad de evaluar el valor de ese parámetro. Desea que se evalúe la llamada al seq 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 de enlace siguiente:

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

Ésta 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 al seq con los parámetros todavía no evaluados s y seq l (go (s+x) (l+1) xs), evaluando los parámetros se difiere hasta el punto en que alguien realmente intenta acceder a sus valores.

Ahora seq puede forzar 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 al 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 seq s 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.