haskell - pagina - Fuga de espacio solo en ciertos casos en el intérprete de GHC al hacer: concat<some list> !! norte

haskell pagina oficial

Question

myConcat mi propia versión de concat , myConcat :

module Eh where
myConcat [] = []
myConcat ([]:os) = myConcat os
myConcat ((x:xs):os) = x : myConcat (xs:os)
(!!!) :: [a] -> Int -> a
xs !!! n | n < 0 = error "negative index"
[] !!! _ = error "index too large"
(x:_) !!! 0 = x
(_:xs) !!! n = xs !!! (n-1)

Si hago myConcat <some huge list> !! n En el intérprete de GHC, me roba la memoria a 300 MB / s, y tengo que matarlo antes de que pueda convocar al asesino de OOM. Tenga en cuenta que carga Eh como "interpretado", no lo compilo antes de cargarlo.

code run in the GHC interpreter space leak? myConcat (repeat [1,2,3,4]) !! (10^8) Yes concat (repeat [1,2,3,4]) !! (10^8) No myConcat (repeat [1,2,3,4]) !!! (10^8) No concat (repeat [1,2,3,4]) !!! (10^8) No

Ahora, si compilo Eh ( ghc --make -O2 Eh.hs ), y luego lo carga en el intérprete y ghc --make -O2 Eh.hs ejecutar estas pruebas, ninguna de ellas deja espacio. Lo mismo si compilo cada caso de prueba en lugar de ejecutarlos en el intérprete.

¿Que esta pasando?

Estoy corriendo GHC 6.12.3.

Answer 1

El tema aquí es el rigor. La evaluación en Haskell no es estricta, por lo que los cálculos generalmente se realizan solo si sus resultados son realmente necesarios. En su lugar, se crea un llamado procesador que representa el cálculo que aún no se ha realizado.

En ciertos casos, el compilador puede, sin embargo, detectar que el resultado del cálculo será necesario de todos modos y, por lo tanto, reemplaza la creación de thunks por el cálculo real.

El Haskell Wiki probablemente explica esto mejor.

Para arreglar su función myConcat , debe asegurarse de que no cree millones de thunks forzando manualmente una evaluación estricta. Una manera (no muy bonita) de hacer esto podría ser:

myConcat [] = []
myConcat ([]:os) = myConcat os
myConcat ((x:xs):os) = ((:) $! x) myConcat (xs:os)