Stapelüberlauf in GHCI beim Versuch, eine Nummer anzuzeigen

Question

Beim Versuch, Haskell zu lernen, habe ich eine Pi-Berechnung implementiert, um Funktionen und Rekursion richtig zu verstehen.

die Leibniz Formula Verwendung für pi Berechnung kam ich mit der Follow-up, das pi auf die Toleranz des gegebenen Parameters druckt, und die Anzahl der rekursiven Funktion aufruft, um diesen Wert zu erhalten:

reverseSign :: (Fractional a, Ord a) => a -> a 
reverseSign num = ((if num > 0 
         then -1 
         else 1) * (abs(num) + 2)) 

piCalc :: (Fractional a, Integral b, Ord a) => a -> (a, b) 
piCalc tolerance = piCalc' 1 0.0 tolerance 0 

piCalc' :: (Ord a, Fractional a, Integral b) => a -> a -> a -> b -> (a, b) 
piCalc' denom prevPi tolerance count = if abs(newPi - prevPi) < tolerance 
             then (newPi, count) 
             else piCalc' (reverseSign denom) newPi tolerance (count + 1) 
             where newPi = prevPi + (4/denom) 

Also, wenn ich dies in GHCI laufen, so scheint es wie erwartet zu funktionieren:

*Main> piCalc 0.001 
(3.1420924036835256,2000) 

Aber wenn ich meine Toleranz zu fein eingestellt, dies geschieht:

*Main> piCalc 0.0000001 
(3.1415927035898146,*** Exception: stack overflow 

Dies scheint mir völlig kontraintuitiv zu sein; die tatsächliche Berechnung funktioniert gut, aber nur versuchen, wie viele rekursive Aufrufe zu drucken?

Warum ist das so?

Answer 1

Dies ist eine Variante des traditionellen foldl (+) 0 [1..1000000] Stapelü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 nutzt die BangPatterns Erweiterung, den Beginn der piCalc' zu

Ändern

piCalc' denom prevPi tolerance !count = ... 

Dieser Wert von count zwingt ausgewertet werden, wenn das Muster übereinstimmt, was bedeutet, dass es ein nie wachsen riesige Kette von Thunks.

Gleichwertig und ohne die Verwendung einer Erweiterung, können Sie es als

piCalc' denom prevPi tolerance count = count `seq` ... 

schreiben Dies entspricht genau semantisch zu der obigen Lösung, aber es nutzt seq explizit statt implizit über eine Spracherweiterung. Dies macht es tragbarer, aber ein wenig ausführlicher.

Als Grund für die Annäherung des PIS ist nicht eine lange Folge von verschachtelten Thunk, aber Zaehler ist: piCalc' Zweige auf dem Ergebnis einer Berechnung, die die Werte von newPi, prevPi und tolerance erfordert.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 Auswertung durchgeführt wird (wenn die Funktion Anwendung ausgeführt wird, was üblicherweise bedeutet, dass Muster am Ergebnis der Funktion angepasst ist.) Andererseits hängt nichts in der Berechnung von von dem Wert von ab count, so wird es während der Berechnung nicht ausgewertet.

Answer 2

Die Zählung wird während der Berechnung nicht ausgewertet, so dass sie bis zum Ende als eine riesige Menge von Thunks (Überlauf des Stapels) übrig bleibt.

Sie können ihre Bewertung während der Berechnung erzwingen, indem Sie ermöglicht die Erweiterung BangPatterns und Schreiben piCalc' denom prevPi tolerance !count = ...

Warum brauchen wir nur noch die Bewertung der count zu zwingen? Nun, alle anderen Argumente werden in der if ausgewertet. Wir müssen sie alle überprüfen, bevor wir wieder piCalc' anrufen, damit sich die Thunks nicht aufbauen; wir brauchen die tatsächlichen Werte, nicht nur "verspricht, dass sie berechnet werden können"! count wird andererseits während der Berechnung nie benötigt und kann bis zum Ende als eine Reihe von Thunks verbleiben.