¿Por qué s ++ t no lleva a un desbordamiento de pila para s grande?

Question

me pregunto por qué

Prelude> head $ reverse $ [1..10000000] ++ [99] 
99 

no conduce a un error de desbordamiento de pila. La ++ en el preludio parece sencillo y no recursiva de cola:

(++) :: [a] -> [a] -> [a] 
(++) []  ys = ys 
(++) (x:xs) ys = x : xs ++ ys 

EDIT: Al principio, pensé que el problema tiene algo que ver con la forma ++ se define en el preámbulo, en especial con la reescritura reglas, por lo tanto la pregunta continuó como abajo. La discusión me mostró que este no es el caso. Ahora creo que un efecto de evaluación lento provoca que el código se ejecute sin un desbordamiento de pila, pero no entiendo cómo.

Así que solo con esto, debería encontrarse con un desbordamiento de pila, ¿verdad? Así que averiguar es probable que tenga algo que ver con la magia GHC que sigue la definición de ++:

{- # REGLAS "++" [~ 1] forall xs ys. xs ++ ys = aumento (\ c n -> foldr c n xs) ys # -}

* ¿Eso es lo que ayuda a evitar el desbordamiento de la pila? ¿Podría alguien dar alguna pista de lo que está sucediendo en este código? **

Answer 1

Esto no acumula desbordamiento, incluso en el intérprete, donde no hay optimizaciones ni reglas de reescritura, porque no usa la pila.

Mira la definición de (++), por ejemplo ,:

(++) :: [a] -> [a] -> [a] 
(++) []  ys = ys 
(++) (x:xs) ys = x : xs ++ ys 

La clave es x : (xs ++ ys) - es decir, es la recursividad vigilado por el constructor :) ("contras". Debido a que Haskell es flojo, asigna un procesador para la operación de contras, y la llamada recursiva va a este procesador (asignado por el montón). Entonces su asignación de pila ahora es asignación de montón, que puede expandirse bastante. Así que todo lo que hace es recorrer la gran lista, asignando nuevos objetos contra en el montón para reemplazar los que está atravesando. ¡Fácil!

"atrás" es un poco diferente:

reverse l = rev l [] 
    where 
    rev []  a = a 
    rev (x:xs) a = rev xs (x:a) 

Esa es una cola recursiva, la función de estilo acumulador, por lo que una vez más, que asignará en el montón.

Como ve, las funciones se basan en el uso de celdas cons en el montón, en lugar de en la pila, por lo tanto, no hay desbordamiento de pila.

para clavar realmente esto, un vistazo a las estadísticas de tiempo de ejecución de la máquina virtual GC:

$ time ./B +RTS -s 
99 

     833 MB total memory in use (13 MB lost due to fragmentation) 
     Generation 0: 3054 collections,  0 parallel, 0.99s, 1.00s elapsed 
     %GC time  82.2% (85.8% elapsed) 

Ahí está su lista grande - que se asigna en el montón, y que gastan el 80% del tiempo de la limpieza de los contras nodos que son creados por (++).

Lección: a menudo puede intercambiar pila por montón.

Answer 2

EDIT: La respuesta a continuación es completamente irrelevante, si no francamente incorrecta. Don Stewart, que demuestra que él realmente entiende evaluación diferida, tiene la explicación correcta.

---

Si ejecuta ghc -ddump-simpl, verá que las funciones que se utilizan son GHC.Base.++ y GHC.List.reverse. Estas funciones están diseñadas para no desbordar la pila en grandes listas. Lo que ve en el Preludio es una "implementación de referencia", no el código que realmente se compila.

Aquí hay un código saqué de la distribución de fuentes de GHC:

reverse     :: [a] -> [a] 
#ifdef USE_REPORT_PRELUDE 
reverse     = foldl (flip (:)) [] 
#else 
reverse l = rev l [] 
    where 
    rev []  a = a 
    rev (x:xs) a = rev xs (x:a) 
#endif 

Y esto:

(++) :: [a] -> [a] -> [a] 
(++) []  ys = ys 
(++) (x:xs) ys = x : xs ++ ys 

{-# RULES 
"++" [~1] forall xs ys. xs ++ ys = augment (\c n -> foldr c n xs)  ys 
    #-} 

En el primer caso, debe quedar claro lo que está pasando. En el segundo, estoy un poco confuso sobre las reglas de reescritura ...

Answer 3

El ++ en el preludio parece sencillo y no recursivo ... Así que solo con esto, debería toparse con un desbordamiento de pila, ¿verdad?

No-cola-recursivo es a menudo mejor que la cola recursiva en Haskell, porque las cosas recursivas no pueden ser perezosas. La definición que enumera allí es mucho mejor que una recursiva de cola, porque una cola recursiva mantendría la recurrencia y generaría la lista completa, incluso si solo necesitas el primer elemento; mientras que un recursivo sin cola solo haría tanto trabajo como sea necesario.