Ich lerne Haskell und ich den folgenden Ausdruck auf Haskell Wiki wirklich verwirrt:
%Vor%Ich kann nicht recht herausfinden, warum das funktioniert.
Wenn ich die Standard-Curry-Logik anwende, gibt (zipWith (+))
eine Funktion zurück, die eine Liste als Argument übernimmt, und gibt wiederum eine andere Funktion zurück, die eine andere Liste als Argument akzeptiert und eine Liste zurückgibt ( zipWith::(a -> b -> c) -> [a] -> [b] -> [c]
). Also, fibs
ist eine Referenz auf eine Liste (die noch nicht ausgewertet wurde) und (tail fibs)
ist das Ende derselben (unevaluierten) Liste. Wenn wir versuchen zu bewerten ( take 10 fibs
), sind die ersten beiden Elemente an 0
und 1
gebunden. Mit anderen Worten: fibs==[0,1,?,?...]
und (tail fibs)==[1,?,?,?]
. Nachdem die erste Addition abgeschlossen ist, wird fibs
[0,1,0+1,?,..]
. Ähnlich erhalten wir nach der zweiten Addition [0,1,0+1,1+(0+1),?,?..]
fibs !! 4
? EDIT2: Ich habe gerade die obige Frage gestellt und gut beantwortet hier . Es tut mir leid, wenn ich jemandes Zeit verschwendet habe.
EDIT: Hier ist ein schwieriger Fall zu verstehen (Quelle: Project Euler Foren ):
%Vor% Beachten Sie, dass all (\y -> x mod y /= 0)...
Wie kann die Bezugnahme auf x hier KEINE unendliche Rekursion verursachen?
Ich werde die Bewertung für Sie verfolgen:
%Vor%Mit:
%Vor%Also:
%Vor%usw. Wenn Sie also in diese Struktur indexieren, wird jeder Schritt der Auswertung von FIBs erzwungen, bis der Index gefunden wird.
Warum ist das effizient? Ein Wort: teilen .
Wenn fibs
berechnet wird, wächst es im Heap und zeichnet Werte auf, die Computer waren. Spätere Rückverweise auf fibs
können alle zuvor berechneten Werte für fibs
wiederverwenden. Kostenlose Memotisierung!
Wie sieht diese Freigabe im Heap aus?
Wenn Sie nach dem Objekt am Ende der Liste fragen, berechnet Haskell den nächsten Wert, zeichnet ihn auf und verschiebt diese Selbstreferenz in einen Knoten.
Die Tatsache, dass dies endet, hängt entscheidend von der Faulheit ab.
Tags und Links haskell self-reference recursion lazy-evaluation