Selbstreferenz in Haskell-Funktionen

8

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),?,?..]

  • Ist meine Logik richtig?
  • Gibt es eine einfachere Möglichkeit dies zu erklären? (irgendwelche Einblicke von Leuten, die wissen, was Haskell-Compiler mit diesem Code macht?) (Links und Referenzen sind willkommen)
  • Es ist wahr, dass diese Art von Code nur wegen der faulen Auswertung funktioniert?
  • Welche Bewertungen passieren, wenn ich fibs !! 4 ?
  • mache
  • Geht dieser Code davon aus, dass zipWith die Elemente zuerst verarbeitet? (Ich denke, es sollte nicht, aber ich verstehe nicht warum nicht)

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?

    
Vladimir Bychkovsky 15.06.2011, 23:44
quelle

1 Antwort

15

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.

    
Don Stewart 16.06.2011, 00:17
quelle