confusione riguardo pigrizia

Question

Ho una funzione

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

che non riesce a straripamento stack con ingresso circa 10^6 elementi (myLength [1..1000000] fallisce). Credo che sia dovuto al thunk build up da quando sostituisco foldl with foldl ', funziona. Fin qui tutto bene.

ma ora ho un'altra funzione per invertire una lista:

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

che utilizza la versione pigro foldl (invece di foldl ')

Quando faccio myLength . myReverse $ [1..1000000]. Questa volta funziona perfettamente. Non riesco a capire perché foldl funzioni per il caso successivo e non per il precedente?

Per chiarire qui myLength utilizza foldl' mentre myReverse utilizza foldl

Answer 1

Ecco la mia ipotesi migliore, anche se non sono un esperto di interni Haskell (ancora).

Durante la creazione del thunk, Haskell assegna tutte le variabili di accumulo intermedie nello stack .

Quando si esegue l'aggiunta come in myLength, è necessario utilizzare lo stack per le variabili intermedie. Vedi this page. Estratto:

Il problema inizia quando finalmente valutiamo z1000000:

Nota che z1000000 = z999999 + 1000000. Così 1000000 viene spinto sullo stack. Quindi viene valutato z999999.

Nota che z999999 = z999998 + 999999. Quindi 999999 viene inserito in pila. Quindi z999998 viene valutato:

Si noti che z999998 = z999997 + 999998. Quindi 999998 viene inserito in pila. Poi z999997 viene valutata:

Tuttavia, durante l'esecuzione di costruzioni lista, ecco cosa penso accade (è qui che inizia la congettura):

Nel valutare z1000000:

noti che z1000000 = 1000000: z999999. Quindi 1000000 viene memorizzato all'interno di z1000000, insieme a un collegamento (puntatore) a z999999. Quindi viene valutato z999999.

Si noti che z999999 = 999999: z999998. Quindi 999999 è memorizzato all'interno di z999999, insieme a un collegamento a z999998. Quindi viene valutato z999998.

ecc

noti che z999999, z999998 etc.passare da un'espressione non ancora valutata in una singola voce di lista è una cosa di Haskell quotidiana :)

Poiché z1000000, z999999, z999998, ecc. sono tutti nello heap, queste operazioni non utilizzano alcuno spazio di stack. QED.