Verwirrung hinsichtlich Trägheit

Question

Ich habe eine Funktion

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

die um 10^6 Elemente mit Stapelüberlauf mit dem Eingang fehlschlägt (myLength [1..1000000] ausfällt). Ich glaube, das liegt an der Verdunkelung, da, wenn ich foldl durch faltl 'ersetze, es funktioniert. So weit so gut.

Aber jetzt habe ich eine andere Funktion eine Liste zu umkehren:

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

, die die faulen Version foldl (statt von foldl ') verwendet

Wenn ich myLength . myReverse $ [1..1000000] tun. Diesmal funktioniert es gut. Ich verstehe nicht warum Foldl für den späteren Fall und nicht für den ehemaligen Fall funktioniert?

Um zu klären, hier myLength foldl verwendet‘, während myReverse foldl verwendet

Answer 1

Hier ist meine beste Vermutung, obwohl ich kein Experte auf Haskell Interna bin (noch) nicht.

Beim Erstellen des Thunks ordnet Haskell alle Zwischenakkumulatorvariablen dem Heap zu.

Bei der Addition wie in myLength muss der Stack für Zwischenvariablen verwendet werden. Siehe this page. Auszug:

Das Problem beginnt, wenn wir endlich z1000000 bewerten:

Beachten Sie, dass z1000000 = z999999 + 1000000. So 1000000 wird auf dem Stapel abgelegt. Dann wird z999999 ausgewertet.

Beachten Sie, dass z999999 = z999998 + 999999. So wird 999999 auf den Stapel geschoben. Dann wird z999998 ausgewertet:

zu beachten, dass z999998 = z999997 + 999998. So 999998 wird auf dem Stapel abgelegt. Dann z999997 ausgewertet:

Wenn jedoch Liste Bau durchgeführt wird, ist hier, was ich denke, geschieht (das ist, wo die Spekulation beginnt):

Bei der Bewertung z1000000:

Beachten Sie, dass z1000000 = 1000000: z999999. So wird 1000000 innerhalb z1000000 zusammen mit einem Link (Zeiger) bis z999999 gespeichert. Dann wird z999999 ausgewertet.

Beachten Sie, dass z999999 = 999999: z999998. So wird 999999 in z999999, zusammen mit einem Link zu z999998 gespeichert. Dann wird z999998 ausgewertet.

usw.

Beachten Sie, dass z999999, z999998 usw.das Wechseln von einem noch nicht ausgewerteten Ausdruck in einen einzelnen Listeneintrag ist eine alltägliche Haskell-Sache :)

Da z1000000, z999999, z999998 usw. alle auf dem Heap stehen, verwenden diese Operationen keinen Stack-Platz. QED.