Tail Rekursion in Haskell

Question

Ich versuche Tail-Rekursion in Haskell zu verstehen. Ich denke, ich verstehe, was es ist und wie es funktioniert, aber ich möchte sicherstellen, dass ich die Dinge nicht vermassle. Hier

ist die "Standard" faktorielles Definition:

factorial 1 = 1 
factorial k = k * factorial (k-1) 

Beim Laufen, beispielsweise factorial 3, meine Funktion ruft mich 3-mal (geben oder nehmen). Dies könnte ein Problem darstellen, wenn ich Faktor 99999999 berechnen möchte, da ich einen Stapelüberlauf haben könnte. Nachdem ich factorial 1 = 1 erreicht habe, muss ich im Stack "zurückkommen" und alle Werte multiplizieren, also habe ich 6 Operationen (3 für den Aufruf der Funktion selbst und 3 für die Multiplikation der Werte).

Jetzt präsentieren Sie ich eine weitere mögliche Implementierung faktorielles:

factorial 1 c = c 
factorial k c = factorial (k-1) (c*k) 

Dieser rekursiv ist, auch. Es wird sich 3 Mal selbst anrufen. Aber es hat nicht das Problem, dann noch "zurückkommen" zu müssen, um die Multiplikationen aller Ergebnisse zu berechnen, da ich bereits das Ergebnis als Argument der Funktion übergebe.

Dies ist, was ich verstanden habe, was Tail Recursion ist. Jetzt scheint es ein bisschen besser als das erste, aber Sie können Stapelüberläufe immer noch so leicht haben. Ich habe gehört, dass der Haskell-Compiler Tail-Recursive-Funktionen hinter den Kulissen in for-Schleifen umwandelt. Ich denke, das ist der Grund, warum es sich lohnt, tail rekursive Funktionen zu machen?

Wenn das der Grund ist, dann gibt es absolut keine Notwendigkeit, zu versuchen, Funktionen tail rekursiv zu machen, wenn der Compiler diesen klugen Trick nicht macht - habe ich Recht? Zum Beispiel, obwohl der C# -Compiler theoretisch tail rekursive Funktionen in Loops erkennen und konvertieren könnte, weiß ich (zumindest ist das, was ich gehört habe), dass es das derzeit nicht tut. Es macht also absolut keinen Sinn, die Funktionen tail-rekursiv zu machen. Ist es das?

Danke!

Answer 1

Es gibt zwei Probleme hier. Das eine ist die Tail-Rekursion im Allgemeinen, und das andere ist, wie Haskell mit Dingen umgeht.

In Bezug auf Tail-Rekursion scheinen Sie die Definition korrekt zu haben. Der nützliche Teil ist, da nur das Endergebnis jedes rekursiven Aufrufs benötigt wird, müssen frühere Aufrufe nicht auf dem Stapel gehalten werden. Anstatt sich selbst zu "nennen", macht die Funktion etwas, das sich selbst "ersetzt", was letztlich wie eine iterative Schleife aussieht. Dies ist eine ziemlich einfache Optimierung, die anständige Compiler im Allgemeinen bieten wird.

Die zweite Ausgabe ist faul Bewertung. Da Haskell den Ausdruck nur bei Bedarf auswertet, funktioniert die Tail-Rekursion standardmäßig nicht ganz normal. Anstatt jeden Aufruf so zu ersetzen, wie er ist, baut er einen riesigen verschachtelten Stapel von "Thunks" auf, dh Ausdrücke, deren Wert noch nicht angefordert wurde. Wenn dieser Thunk-Haufen groß genug wird, wird es in der Tat einen Stapelüberlauf erzeugen.

Es gibt zwei Lösungen in Haskell, je nachdem, was Sie tun müssen:

• Wenn das Ergebnis der verschachtelten Daten Konstrukteurs besteht - wie eine Liste produzieren - dann möchten Sie vermeiden Schwanzrekursion; Setzen Sie stattdessen die Rekursion in eines der Konstruktorfelder. Dadurch wird das Ergebnis ebenfalls träge und verursacht keine Stapelüberläufe.

• Wenn das Ergebnis aus einem einzigen Wert, wollen Sie es streng, zu bewerten, so dass jeder Schritt der Rekursion so bald gezwungen wird, als der Endwert benötigt wird. Dies ergibt die übliche Pseudo-Iteration, die Sie von der Tail-Rekursion erwarten würden.

auch im Auge behalten, dass GHC verflixt clever ist und, wenn Sie mit Optimierungen kompilieren, wird es oft Orte erkennen, wo Auswertung streng sein sollte, und kümmern sich um sie für Sie. Dies wird jedoch in GHCi nicht funktionieren.

Answer 2

Sie sollten die eingebauten Mechanismen verwenden, dann müssen Sie nicht über die Möglichkeiten denken, dass Ihre Funktion tail-rekursive

fac 0 = 1 
fac n = product [1..n] 

Oder wenn Produkt wurden nicht definiert zu machen:

fac n = foldl' (*) 1 [1..n] 

(siehe http://www.haskell.org/haskellwiki/Foldr_Foldl_Foldl%27 über die Falte ... Version zu verwenden)