In Haskell kann ich eine selbstreferenzielle Sequenz in GHCI schreiben:
%Vor%welches produziert:
%Vor%Allerdings sagt meine Intuition über faule Bewertung, dass dies während der Expansion passieren sollte
%Vor%Das ist offensichtlich nicht das, was passiert. Ich kann das Muster in der richtigen Antwort sehen. Wir bewegen lediglich ein Element in der Liste nach dem anderen in einem unendlichen Strom. Das Muster erkenne ich und ich kann es im Code anwenden. Es passt jedoch nicht zu meinem mentalen Modell der faulen Bewertung. Es fühlt sich ein wenig "magisch" an. Wo ist meine Intuition falsch?
Denken Sie daran, nur etwas mit seiner Definition zu ersetzen. Also, wenn Sie x erweitern, sollten Sie 1 : map (+1) x ersetzen, nicht den "aktuellen Wert" (was auch immer das bedeutet).
Ich werde Jefffreys Idee reproduzieren, aber mit dem gebührenden Respekt für die Faulheit.
%Vor%und so weiter.
Übung beende die Bewertung in diesem Stil selbst (es ist ziemlich informativ).
Beachten Sie, wie wir damit beginnen, eine Kette von map s aufzubauen, wenn die Liste wächst. Wenn Sie nur print x haben, wird die Ausgabe nach einiger Zeit langsamer. Deshalb. Es gibt einen effizienteren Weg, links als Übung (und [1..] betrügt: -).
N.B. das ist noch etwas weniger faul als das, was tatsächlich passieren wird. map (+1) (1 : ...) wird zu (1+1) : map (+1) ... ausgewertet, und die Addition findet nur statt, wenn die Anzahl tatsächlich beobachtet wird, indem sie entweder gedruckt wird oder z.B. Vergleichen Sie es.
Wird Ness in diesem Beitrag einen Fehler erkennen? Siehe die Kommentare und seine Antwort.
Hier passiert was passiert. Faulheit ist Nicht-Strenge + Memoisierung (von Thunks) . Wir können dies zeigen, indem wir alle vorläufigen Daten benennen, die entstehen, wenn der Ausdruck erzwungen wird:
%Vor% Die Elemente im resultierenden Stream a1:a2:a3:a4:... beziehen sich jeweils auf ihren Vorgänger: a1 = 1; a2 = (1+) a1; a3 = (1+) a2; a4 = (1+) a3; ... .
Dies entspricht also x = iterate (1+) 1 . Ohne die gemeinsame Nutzung von Daten und ihre Wiederverwendung durch Rückwärtsreferenz (aktiviert durch die Memoisierung von Speicher) wäre dies äquivalent zu x = [sum $ replicate n 1 | n <- [1..]] , was eine radikal weniger effiziente Berechnung ist ( O (n 2 ) anstelle von O (n) ).
Wir können das Teilen im Vergleich zum Nicht-Teilen mit
erklären %Vor% Wenn Sie versuchen, y bei der Eingabeaufforderung von GHCi auszudrucken, wird eine deutliche Verlangsamung angezeigt, wenn der Fortschritt fortschreitet. Beim Ausdrucken des x -Streams gibt es keine Verlangsamung.
(siehe auch Ссылка für ein ähnliches Beispiel).
Sie ordnen +1 über die gesamte Liste zu, so dass das anfängliche 1 zu n wird, wobei n die Anzahl der wiederholten Wiederholungen angibt, wenn das sinnvoll ist. Anstelle der Ableitung, an die Sie denken, sieht es eher so aus:
A 1 wird einer lazy comprired Liste vorangestellt, deren Elemente bei jedem Rekursionsschritt inkrementiert werden.
Man kann sich also den% code% re Schritt vorstellen, indem man die Liste n in die Liste [1, 2, 3, ..., n ...] einfügt und eine [2, 3, 4, ..., n+1 ...] vorstellt.
Sehen wir uns das etwas mathematischer an. Angenommen, dass
%Vor%Dann
%Vor%so
%Vor%Dies (umgedreht) ist die Gleichung, mit der wir begonnen haben:
%Vor%Was wir gezeigt haben, ist das
%Vor%ist eine Lösung der Gleichung
%Vor% Die nächste Frage ist natürlich, ob es andere Lösungen für Gleichung 1 gibt. Die Antwort ist, wie sich herausstellt, nein. Dies ist wichtig, weil Haskells Bewertungsmodell effektiv die "am wenigsten definierte" Lösung einer solchen Gleichung wählt. Wenn wir zum Beispiel x = 1 : tail x definieren, dann wäre jede Liste, die mit 1 beginnt, eine Lösung, aber wir würden tatsächlich 1 : _|_ bekommen, wo _|_ repräsentiert einen Fehler oder eine Nicht-Beendigung. Gl. 1 führt nicht zu dieser Art von Unordnung:
Sei y eine beliebige Lösung von Gl. 1, also
Beachten Sie, dass wir anhand der Definition feststellen können, dass
%Vor%Nun nehme an
%Vor%Dann
%Vor% Nach Induktion finden wir take n y = take n x für jedes n . Das heißt y = x .
In Ihrer Reihenfolge der Bewertung:
%Vor% Sie machen eine falsche Annahme. Sie nehmen an, dass x ist [1, 2] , denn das ist die Anzahl der Elemente, die Sie dort sehen können. Es ist nicht. Sie haben vergessen zu berücksichtigen, dass das x am Ende rekursiv berechnet werden muss.
Das x am Ende der Sequenz muss durch rekursives Berechnen selbst berechnet werden. Hier ist der tatsächliche Fluss:
Tags und Links haskell lazy-evaluation