La pereza y la recursión de la cola en Haskell, ¿por qué se está estrellando?

Question

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.

Answer 1

He escrito mucho sobre esto:

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

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.

Answer 2

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.

Answer 3

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.