Die kanonische Implementierung von length :: [a] -> Int ist:
Das ist sehr schön, leidet aber unter einem Stapelüberlauf, da es linearen Platz verwendet.
Die tailrekursive Version:
%Vor%leidet nicht an diesem Problem, aber ich verstehe nicht, wie dies in einer faulen Sprache in konstantem Raum laufen kann.
Akkumuliert die Laufzeit nicht zahlreiche (n + 1) -Thunks, während sie sich durch die Liste bewegt? Sollte diese Funktion Haskell nicht dazu bringen, O (n) Speicherplatz zu verbrauchen und zu einem Stack-Überlauf zu führen?
(wenn es darauf ankommt, verwende ich GHC)
Ja, Sie haben einen häufigen Fallstrick mit häufigen Parametern bekommen. Die übliche Heilung besteht darin, eine strenge Bewertung des akkumulierenden Parameters zu erzwingen; zu diesem Zweck mag ich den strikten Anwendungsoperator $! . Wenn Sie die Strenge nicht erzwingen, könnte das Optimierungssystem von GHC entscheiden, dass diese Funktion streng ist, aber möglicherweise nicht. Definitiv ist es keine Sache, auf die man sich verlassen kann - manchmal möchte man, dass ein Akkumulationsparameter träge ausgewertet wird und O (N) Raum ist in Ordnung, danke.
Wie schreibe ich eine Konstante-Raum-Länge-Funktion in Haskell?
Wie oben erwähnt, verwenden Sie den strikten Anwendungsoperator, um die Berechnung des akkumulierenden Parameters zu erzwingen:
%Vor% Der Typ von $! ist (a -> b) -> a -> b und erzwingt die Auswertung von a , bevor die Funktion angewendet wird.
Ausführen Ihrer zweiten Version in GHCi:
%Vor%Also, um Ihre Frage zu beantworten: Ja, es leidet unter diesem Problem, genau wie Sie es erwarten.
Allerdings ist GHC schlauer als der durchschnittliche Compiler; Wenn Sie mit optimierten Kompilierungen kompilieren, wird der Code für Sie korrigiert und es wird in konstantem Speicherplatz arbeiten.
Allgemein gibt es Möglichkeiten, Striktheit an bestimmten Stellen im Haskell-Code zu erzwingen, wodurch das Erstellen von tief verschachtelten Thunks verhindert wird. Ein übliches Beispiel ist foldl vs. foldl' :
Bei beiden Funktionen handelt es sich um linke Falten, die die gleiche Funktion haben, außer dass foldl faul ist, während foldl' streng ist. Das Ergebnis ist, dass len1 mit einem Stapelüberlauf in GHCi endet, während len2 korrekt funktioniert.
Eine tailrekursive Funktion muss keinen Stapel verwalten, da der von der Funktion zurückgegebene Wert einfach der vom Tail-Aufruf zurückgegebene Wert ist. Anstatt einen neuen Stack-Frame zu erstellen, wird der aktuelle Stack wiederverwendet, wobei die Locals von den neuen Werten überschrieben werden, die an den Tail-Call übergeben werden. Also wird jedes n+1 an die Stelle geschrieben, an der sich das alte n befand, und Sie haben konstanten Speicherplatz.
Bearbeiten - Wie du schon geschrieben hast, hast du recht, es wird das (n+1) s erahnen und einen Überlauf verursachen. Einfach zu testen, probiere einfach length [1..1000000] aus. Du kannst das beheben, indem du es zwingst, es zuerst auszuwerten: length xs $! (n+1) , was dann funktioniert, wie ich oben sagte.
Tags und Links haskell lazy-evaluation