Beim Versuch, Haskell zu lernen, habe ich eine Pi-Berechnung implementiert, um Funktionen und Rekursion richtig zu verstehen.
Mit der Leibniz-Formel für die Pi-Berechnung habe ich folgendes herausgefunden, welches pi ausgibt die Toleranz des angegebenen Parameters und die Anzahl der rekursiven Funktionsaufrufe, um diesen Wert zu erhalten:
%Vor%Wenn ich das in GHCI ausführe, scheint es wie erwartet zu funktionieren:
%Vor%Aber wenn ich meine Toleranz zu fein einstelle, passiert das:
%Vor%Das scheint mir völlig kontraintuitiv zu sein; die eigentliche Berechnung funktioniert gut, aber nur versuchen, zu drucken, wie viele rekursive Aufrufe fehlschlagen?
Warum ist das so?
Dies ist eine Variante des traditionellen foldl (+) 0 [1..1000000] Stack-Überlaufs. Das Problem ist, dass der Zählwert niemals während der Auswertung von piCalc' ausgewertet wird. Dies bedeutet, dass es nur eine ständig wachsende Menge von Thunks enthält, die den erforderlichen Zusatz darstellen. Wenn es benötigt wird, verursacht die Tatsache, dass die Auswertung eine Stapeltiefe erfordert, die proportional zur Anzahl der Thunks ist, den Überlauf.
Die einfachste Lösung verwendet die Erweiterung BangPatterns und ändert den Start von piCalc' in
Dies zwingt den Wert von count , ausgewertet zu werden, wenn das Muster übereinstimmt, was bedeutet, dass es niemals eine riesige Kette von Thunks wachsen wird.
Äquivalent und ohne die Verwendung einer Erweiterung könnten Sie es als
schreiben %Vor% Dies ist semantisch exakt äquivalent zur obigen Lösung, verwendet aber explizit seq statt implizit über eine Spracherweiterung. Dies macht es tragbarer, aber ein wenig ausführlicher.
Warum ist die Approximation von pi keine lange Sequenz von verschachtelten Thunks, sondern count: piCalc' verzweigt sich auf das Ergebnis einer Berechnung, die die Werte von newPi , prevPi und tolerance benötigt . Es muss diese Werte überprüfen, bevor es entscheidet, ob es getan wird oder ob es eine weitere Iteration ausführen muss. Es ist dieser Zweig, der bewirkt, dass die Bewertung durchgeführt wird (wenn die Funktion Anwendung ausgeführt wird, was üblicherweise bedeutet, dass Muster auf das Ergebnis der Funktion abgestimmt ist.) Andererseits hängt nichts in der Berechnung von piCalc' von der ab Wert von count , daher wird es während der Berechnung nicht ausgewertet.
Der Zählwert wird während der Berechnung nicht ausgewertet, so dass er bis zum Ende als eine riesige Menge von Thunks übrig bleibt (über den Stack hinaus).
Sie können seine Auswertung während der Berechnung erzwingen, indem Sie die Erweiterung BangPatterns aktivieren und piCalc' denom prevPi tolerance !count = ...
Warum müssen wir nur die Auswertung von count erzwingen? Nun, alle anderen Argumente werden in if ausgewertet. Wir müssen sie alle überprüfen, bevor wir piCalc' erneut aufrufen, damit sich die Thunks nicht aufbauen. wir brauchen die tatsächlichen Werte, nicht nur "verspricht, dass sie berechnet werden können"! Andererseits wird count während der Berechnung niemals benötigt und kann bis zum Ende als eine Reihe von Thunks verbleiben.