confusión con respecto a la pereza

Question

I tiene una función

myLength = foldl (\ x _ -> x + 1) 0 

que falla con desbordamiento de pila con la entrada de alrededor de 10^6 elementos (myLength [1..1000000] falla). Creo que eso se debe a la acumulación de thunk, ya que cuando reemplazo foldl con foldl ', funciona. Hasta ahora todo bien.

pero ahora tengo otra función de revertir una lista:

myReverse = foldl (\ acc x -> x : acc) [] 

que utiliza la versión foldl perezoso ( en lugar de foldl ')

Cuando hago myLength . myReverse $ [1..1000000]. Esta vez funciona bien. No entiendo por qué foldl funciona para el caso posterior y no para el anterior.

Para aclarar aquí myLength utiliza foldl' mientras myReverse utiliza foldl

Answer 1

Aquí está mi mejor conjetura, aunque no soy un experto en el funcionamiento interno de Haskell (todavía).

Al compilar el procesador, Haskell asigna todas las variables del acumulador intermedio en el montón .

Al realizar la adición como en myLength, necesita usar la pila para variables intermedias. Ver this page. Extracto:

El problema comienza cuando finalmente evaluamos z1000000:

Tenga en cuenta que z1000000 = z999999 + 1000000. Así 1000000 se empuja en la pila. Entonces se evalúa z999999.

Tenga en cuenta que z999999 = z999998 + 999999. Entonces 999999 se empuja en la pila. Luego se evalúa z999998:

Tenga en cuenta que z999998 = z999997 + 999998. Entonces 999998 se empuja en la pila. Entonces z999997 se evalúa:

Sin embargo, cuando se realiza la construcción de la lista, aquí es lo que creo que sucede (aquí es donde comienza la conjetura):

Al evaluar z1000000:

Tenga en cuenta que z1000000 = 1000000: z999999. Por lo tanto, 1000000 se almacena dentro de z1000000, junto con un enlace (puntero) a z999999. Entonces se evalúa z999999.

Tenga en cuenta que z999999 = 999999: z999998. Entonces 999999 se almacena dentro de z999999, junto con un enlace a z999998. Luego se evalúa z999998.

etc.

Tenga en cuenta que z999999, z999998 etc.cambiar de una expresión aún no evaluada a un solo elemento de lista es algo cotidiano de Haskell :)

Dado que z1000000, z999999, z999998, etc. están todos en el montón, estas operaciones no usan ningún espacio de pila. QED.