Grundlegendes zu einer rekursiv definierten Liste (Fibs in Bezug auf zipWith)

Ich lerne Haskell und bin auf folgenden Code gestoßen:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Ich habe ein bisschen Probleme beim Parsen, was die Funktionsweise betrifft. Es ist sehr ordentlich, ich verstehe, dass nichts mehr benötigt wird, aber ich würde gerne verstehen, wie Haskell es schafft, Fibs beim Schreiben "auszufüllen":

take 50 fibs

Irgendeine Hilfe?

Vielen Dank!

Ich werde ein bisschen erklären, wie es intern funktioniert. Zunächst müssen Sie erkennen, dass Haskell für seine Werte ein sogenanntes Thunk verwendet. Ein Thunk ist im Grunde ein Wert, der noch nicht berechnet wurde - stellen Sie sich das als Funktion von 0 Argumenten vor. Wann immer Haskell möchte, kann er den Thunk bewerten (oder teilweise bewerten) und ihn in einen realen Wert umwandeln. Wenn ein Thunk nur teilweise ausgewertet wird, enthält der resultierende Wert mehr Thunks.

Betrachten Sie zum Beispiel den Ausdruck:

(2 + 3, 4)

In einer gewöhnlichen Sprache würde dieser Wert als gespeichert (5, 4), in Haskell jedoch als (<thunk 2 + 3>, 4). Wenn Sie nach dem zweiten Element dieses Tupels fragen, wird "4" angezeigt, ohne dass jemals 2 und 3 addiert werden. Nur wenn Sie nach dem ersten Element dieses Tupels fragen, bewertet es den Thunk und stellt fest, dass es 5 ist.

Mit Fibs ist es etwas komplizierter, weil es rekursiv ist, aber wir können die gleiche Idee verwenden. Da fibsHaskell keine Argumente akzeptiert, werden alle entdeckten Listenelemente dauerhaft gespeichert - das ist wichtig.

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Es hilft Haskells aktuelles Wissen von drei Ausdrücke sichtbar zu machen: fibs, tail fibsund zipWith (+) fibs (tail fibs). Wir gehen davon aus, dass Haskell zunächst Folgendes weiß:

fibs                         = 0 : 1 : <thunk1>
tail fibs                    = 1 : <thunk1>
zipWith (+) fibs (tail fibs) = <thunk1>

Beachten Sie, dass die 2. Reihe nur die erste nach links verschobene ist und die 3. Reihe die ersten beiden summierten Reihen.

Fragen Sie nach take 2 fibsund Sie werden bekommen [0, 1]. Haskell muss das oben Gesagte nicht weiter auswerten, um dies herauszufinden.

Fragen Sie nach take 3 fibsund Haskell wird die 0 und 1 erhalten und dann erkennen, dass es den Thunk teilweise bewerten muss . Um vollständig ausgewertet zu werden zipWith (+) fibs (tail fibs), müssen die ersten beiden Zeilen summiert werden - das kann es nicht vollständig, aber es kann beginnen , die ersten beiden Zeilen zu summieren:

fibs                         = 0 : 1 : 1: <thunk2>
tail fibs                    = 1 : 1 : <thunk2>
zipWith (+) fibs (tail fibs) = 1 : <thunk2>

Beachten Sie, dass ich die "1" in der 3. Zeile ausgefüllt habe und sie automatisch auch in der ersten und zweiten Zeile angezeigt wurde, da alle drei Zeilen denselben Thunk verwenden (stellen Sie sich das wie einen Zeiger vor, auf den geschrieben wurde). Und weil die Auswertung noch nicht abgeschlossen war, wurde ein neuer Thunk erstellt, der den Rest der Liste enthält, falls dies jemals benötigt werden sollte.

Es wird jedoch nicht benötigt, da take 3 fibses erledigt ist : [0, 1, 1]. Aber jetzt sagen Sie, Sie fragen nach take 50 fibs; Haskell erinnert sich bereits an die 0, 1 und 1. Aber es muss weitergehen. Also summiert es die ersten beiden Zeilen weiter:

fibs                         = 0 : 1 : 1 : 2 : <thunk3>
tail fibs                    = 1 : 1 : 2 : <thunk3>
zipWith (+) fibs (tail fibs) = 1 : 2 : <thunk3>

...

fibs                         = 0 : 1 : 1 : 2 : 3 : <thunk4>
tail fibs                    = 1 : 1 : 2 : 3 : <thunk4>
zipWith (+) fibs (tail fibs) = 1 : 2 : 3 : <thunk4>

Und so weiter, bis es 48 Spalten der 3. Zeile ausgefüllt und damit die ersten 50 Zahlen ausgearbeitet hat. Haskell wertet genau so viel aus, wie es braucht, und lässt den unendlichen "Rest" der Sequenz als Thunk-Objekt, falls es jemals mehr braucht.

Beachten Sie take 25 fibs, dass Haskell es nicht erneut auswertet , wenn Sie später danach fragen - es werden nur die ersten 25 Zahlen aus der Liste berechnet, die es bereits berechnet hat.

Bearbeiten : Jedem Thunk wurde eine eindeutige Nummer hinzugefügt, um Verwirrung zu vermeiden.

Ich habe vor einiger Zeit einen Artikel darüber geschrieben. Sie finden es hier .

Wie ich dort erwähnte, lesen Sie Kapitel 14.2 in Paul Hudaks Buch "The Haskell School of Expression", in dem er am Beispiel von Fibonacci über rekursive Streams spricht.

Hinweis: Das Ende einer Sequenz ist die Sequenz ohne das erste Element.

| --- + --- + --- + --- + ---- + ---- + ---- + ---- + ------------- ----------------------- |
| 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | Fibonacci-Sequenz (Fibs) |
| --- + --- + --- + --- + ---- + ---- + ---- + ---- + ------------- ----------------------- |
| 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | Schwanz der Fib-Sequenz (Schwanz Fibs) |
| --- + --- + --- + --- + ---- + ---- + ---- + ---- + ------------- ----------------------- |

Fügen Sie die beiden Spalten hinzu: Fügen Sie Fibs (Tail Fibs) hinzu , um den Schwanz der Fib- Sequenz zu erhalten

| --- + --- + --- + --- + ---- + ---- + ---- + ---- + ------------- ----------------------- |
| 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | Schwanz des Schwanzes der Fibonacci-Sequenz |
| --- + --- + --- + --- + ---- + ---- + ---- + ---- + ------------- ----------------------- |

add fibs (tail fibs) können als zipWith (+) fibs (tail fibs) geschrieben werden

Jetzt müssen wir nur noch die Generierung vorbereiten, indem wir mit den ersten beiden Fibonacci-Zahlen beginnen, um die vollständige Fibonacci-Sequenz zu erhalten.

1: 1: zipWith (+) fibs (tail fibs)

Hinweis: Diese rekursive Definition funktioniert nicht in einer typischen Sprache, die eifrig ausgewertet wird. Es funktioniert in Haskell, da es eine verzögerte Auswertung macht. Wenn Sie also nach den ersten 4 Fibonacci-Zahlen fragen, nehmen Sie 4 Fibs , haskell berechnet nur genug Sequenz nach Bedarf.

Ein sehr verwandtes Beispiel finden Sie hier , obwohl ich es nicht vollständig durchgesehen habe , es könnte hilfreich sein.

Ich bin mir der Implementierungsdetails nicht ganz sicher, aber ich vermute, dass sie in den Zeilen meiner Argumentation unten stehen sollten.

Bitte nehmen Sie dies mit einer Prise Salz, dies ist möglicherweise in der Umsetzung ungenau, aber nur als Verständnishilfe.

Haskell wird nichts bewerten, es sei denn, es wird dazu gezwungen, was als Lazy Evaluation bekannt ist, was an sich schon ein schönes Konzept ist.

So können wir nur annehmen , wurde ich gebeten , eine tun take 3 fibsHaskell speichert die fibsListe als 0:1:another_list, da wir gefragt habe , um take 3auch wir davon ausgehen , kann es gespeichert ist, wie fibs = 0:1:x:another_listund (tail fibs) = 1:x:another_listund 0 : 1 : zipWith (+) fibs (tail fibs)wird dann0 : 1 : (0+1) : (1+x) : (x+head another_list) ...

Durch Mustervergleich weiß Haskell, dass x = 0 + 1So uns dazu führt 0:1:1.

Ich bin allerdings sehr interessiert, wenn jemand die richtigen Implementierungsdetails kennt. Ich kann verstehen, dass Lazy Evaluation-Techniken ziemlich kompliziert sein können.

Hoffe das hilft beim Verständnis.

Erneuter obligatorischer Haftungsausschluss: Bitte nehmen Sie dies mit einer Prise Salz, dies ist möglicherweise in der Umsetzung ungenau, aber nur als Verständnishilfe.

Werfen wir einen Blick auf die Definition von zipWith zipWith f (x:xs) (y:ys) = f x y : zipWith xs ys

Unsere Fibs sind: fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Zum take 3 fibsErsetzen der Definition von zipWithund xs = tail (x:xs)wir bekommen 0 : 1 : (0+1) : zipWith (+) (tail fibs) (tail (tail fibs))

Zum take 4 fibserneuten Ersetzen bekommen wir 0 : 1 : 1 : (1+1) : zipWith (+) (tail (tail fibs)) (tail (tail (tail fibs)))

und so weiter.