Ich habe versucht, eine faule Bewertung in Haskell zu verstehen, und ich habe es im Grunde genommen nur als evaluiert, wenn es sein muss. Aber als ich versuchte, Fibonacci effizient zu implementieren, stieß ich auf dieses (seltsame?) Verhalten: Diese Implementierung:
%Vor%funktioniert auch, wenn Sie mit
aufgerufen werden %Vor%beim Austauschen der übergebenen Argumente im rekursiven Aufruf:
%Vor%ergibt:
%Vor%Warum muss ich dem Compiler im ersten Beispiel nicht eifrig eine Bewertung geben? Warum funktioniert das zweite Beispiel nicht, während das erste funktioniert?
Ich habe dafür GHCi 8.0.1 unter Windows 10 verwendet.
Beachten Sie zunächst, dass der Unterschied zwischen Ihren beiden Versionen quantitativ und nicht qualitativ ist. Der erste Stapel wird bei einer Eingabe von 40000000 den Stapel überschreiben, und der zweite wird bei einer Eingabe von 10000000 erfolgreich abgeschlossen. Es sieht so aus, als ob die zweite Version doppelt so viel Stack wie die erste verwendet.
Im Grunde ist der Grund, dass, wenn wir die Notation {n} für die Thunks einführen, die in den x und y Argumenten leben, Ihre erste Version
während die zweite Version
%Vor% Überlegen Sie sich nun, was passiert, wenn die fib2 Rekursion beendet ist und es Zeit ist, {n} (oder {n+1} zu bewerten; ignorieren Sie diesen Unterschied einfach). Jeder der Thunks {0} , ..., {n} wird nur einmal in einer bestimmten Reihenfolge ausgewertet. Es kommt vor, dass (+) zuerst sein linkes Argument und dann sein rechtes Argument auswertet. Zur Definitivität nehmen wir einfach n = 6 . Die Auswertung sieht aus wie
Der Stapel wird nie tiefer als n/2 levels, da wir zuerst von {n} auf {n-2} rekursieren und wenn wir {n-1} berechnen müssen, haben wir {n-2} bereits berechnet.
Im Gegensatz dazu werden wir in der zweiten Version zuerst von {n} auf {n-1} rekursieren, also wird der Stapel n levels haben.
Tags und Links haskell recursion lazy-evaluation