Ich wollte foldl vs foldr testen. Nach allem, was ich gesehen habe, sollten Sie aufgrund der Optimierung der Schwanzrekursion Foldl über Foldr verwenden, wann immer Sie können.
Das macht Sinn. Nach dem Ausführen dieses Tests bin ich jedoch verwirrt:
foldr (dauert 0,057 Sekunden, wenn der Zeitbefehl verwendet wird):
a::a -> [a] -> [a]
a x = ([x] ++ )
main = putStrLn(show ( sum (foldr a [] [0.. 100000])))
foldl (dauert bei Verwendung des Zeitbefehls 0,089 Sekunden):
b::[b] -> b -> [b]
b xs = ( ++ xs). (\y->[y])
main = putStrLn(show ( sum (foldl b [] [0.. 100000])))
Es ist klar, dass dieses Beispiel trivial ist, aber ich bin verwirrt darüber, warum Foldr Foldl schlägt. Sollte dies nicht ein klarer Fall sein, in dem Foldl gewinnt?
a
alsa = (:)
b
alsb = flip (:)
.Antworten:
Willkommen in der Welt der faulen Bewertung.
Wenn Sie in Bezug auf eine strenge Bewertung darüber nachdenken, sieht Foldl "gut" und Foldr "schlecht" aus, da Foldl schwanzrekursiv ist, aber Foldr müsste einen Turm im Stapel bauen, damit es das letzte Element zuerst verarbeiten kann.
Eine träge Auswertung dreht jedoch den Spieß um. Nehmen Sie zum Beispiel die Definition der Kartenfunktion:
map :: (a -> b) -> [a] -> [b] map _ [] = [] map f (x:xs) = f x : map f xs
Dies wäre nicht allzu gut, wenn Haskell eine strikte Bewertung verwenden würde, da zuerst der Schwanz berechnet und dann der Artikel vorangestellt werden müsste (für alle Artikel in der Liste). Die einzige Möglichkeit, dies effizient zu tun, besteht anscheinend darin, die Elemente in umgekehrter Reihenfolge zu erstellen.
Dank der verzögerten Auswertung von Haskell ist diese Kartenfunktion jedoch tatsächlich effizient. Listen in Haskell können als Generatoren betrachtet werden, und diese Zuordnungsfunktion generiert ihr erstes Element, indem f auf das erste Element der Eingabeliste angewendet wird. Wenn ein zweites Element benötigt wird, wird das gleiche erneut ausgeführt (ohne zusätzlichen Speicherplatz zu benötigen).
Es stellt sich heraus, dass
map
dies beschrieben werden kann mitfoldr
:map f xs = foldr (\x ys -> f x : ys) [] xs
Es ist schwer zu sagen, wenn man es sich ansieht, aber eine faule Bewertung setzt ein, weil foldr sofort
f
sein erstes Argument vorbringen kann :foldr f z [] = z foldr f z (x:xs) = f x (foldr f z xs)
Da das
f
definierte vonmap
das erste Element der Ergebnisliste nur mit dem ersten Parameter zurückgeben kann, kann die Falte in konstantem Raum träge arbeiten.Jetzt beißt die faule Bewertung zurück. Versuchen Sie beispielsweise, sum [1..1000000] auszuführen. Es ergibt sich ein Stapelüberlauf. Warum sollte es? Es sollte nur von links nach rechts ausgewertet werden, oder?
Schauen wir uns an, wie Haskell es bewertet:
foldl f z [] = z foldl f z (x:xs) = foldl f (f z x) xs sum = foldl (+) 0 sum [1..1000000] = foldl (+) 0 [1..1000000] = foldl (+) ((+) 0 1) [2..1000000] = foldl (+) ((+) ((+) 0 1) 2) [3..1000000] = foldl (+) ((+) ((+) ((+) 0 1) 2) 3) [4..1000000] ... = (+) ((+) ((+) (...) 999999) 1000000)
Haskell ist zu faul, um die Ergänzungen auszuführen. Stattdessen endet es mit einem Turm von nicht bewerteten Thunks, die gezwungen werden müssen, eine Nummer zu bekommen. Der Stapelüberlauf tritt während dieser Auswertung auf, da er tief rekursiv sein muss, um alle Thunks auszuwerten.
Glücklicherweise gibt es in Data.List eine spezielle Funktion
foldl'
, die streng funktioniert.foldl' (+) 0 [1..1000000]
wird nicht überlaufen. (Anmerkung: Ich habe versucht , Ersatzfoldl
mitfoldl'
in den Test, aber es machte es tatsächlich langsamer ausgeführt.)quelle
sum
aufgrund der Strenge-Analyse normalerweise funktioniert.map f (x:xs) = f x : map f xs
der Rekursionmap
wird bewacht von der faulen Liste Konstruktor:
. Wenn:
es streng wäre, gäbe es keine Bewachung, nur eine einfache Rekursion. Ich denke, dort fehlt ein Komma: "... dann funktioniert es wie eine geschützte Rekursion (auch wenn) mit einem strengen Datenkonstruktor" - wenn der TRMCO vorhanden ist.EDIT: Wenn ich dieses Problem noch einmal betrachte, denke ich, dass alle aktuellen Erklärungen etwas unzureichend sind, deshalb habe ich eine längere Erklärung geschrieben.
Der Unterschied besteht darin, wie
foldl
undfoldr
wie ihre Reduktionsfunktion angewendet wird. Wennfoldr
wir uns den Fall ansehen, können wir ihn als erweiternfoldr (\x -> [x] ++ ) [] [0..10000] [0] ++ foldr a [] [1..10000] [0] ++ ([1] ++ foldr a [] [2..10000]) ...
Diese Liste wird von verarbeitet
sum
und wie folgt verwendet:sum = foldl' (+) 0 foldl' (+) 0 ([0] ++ ([1] ++ ... ++ [10000])) foldl' (+) 0 (0 : [1] ++ ... ++ [10000]) -- get head of list from '++' definition foldl' (+) 0 ([1] ++ [2] ++ ... ++ [10000]) -- add accumulator and head of list foldl' (+) 0 (1 : [2] ++ ... ++ [10000]) foldl' (+) 1 ([2] ++ ... ++ [10000]) ...
Ich habe die Details der Listenverkettung weggelassen, aber so geht die Reduzierung weiter. Der wichtige Teil ist, dass alles verarbeitet wird, um Listenüberquerungen zu minimieren. Der
foldr
einzige durchläuft die Liste einmal, die Verkettungen erfordern keine fortlaufenden Listendurchläufe undsum
verbrauchen die Liste schließlich in einem Durchgang. Entscheidend ist, dass der Kopf der Liste vonfoldr
sofort bis verfügbar istsum
, sodasssum
sofort mit der Arbeit begonnen werden kann und die Werte beim Generieren überprüft werden können. Mit Fusions-Frameworks wievector
werden wahrscheinlich sogar die Zwischenlisten weggeschmolzen.Vergleichen Sie dies mit der
foldl
Funktion:b xs = ( ++xs) . (\y->[y]) foldl b [] [0..10000] foldl b ( [0] ++ [] ) [1..10000] foldl b ( [1] ++ ([0] ++ []) ) [2..10000] foldl b ( [2] ++ ([1] ++ ([0] ++ [])) ) [3..10000] ...
Beachten Sie, dass der Kopf der Liste erst verfügbar ist, wenn er
foldl
fertig ist. Dies bedeutet, dass die gesamte Liste im Speicher erstellt werden muss, bevorsum
die Arbeit beginnen kann. Dies ist insgesamt viel weniger effizient. Das Ausführen der beiden Versionen mit+RTS -s
zeigt eine miserable Speicherbereinigungsleistung gegenüber der Foldl-Version.Dies ist auch ein Fall, in dem
foldl'
nicht helfen wird. Die zusätzliche Strenge vonfoldl'
ändert nichts an der Art und Weise, wie die Zwischenliste erstellt wird. Der Kopf der Liste bleibt nicht verfügbar, bis das Falten abgeschlossen ist, sodass das Ergebnis immer noch langsamer ist als mitfoldr
.Ich benutze die folgende Regel, um die beste Wahl zu bestimmen
fold
foldl'
(z. B. ist dies die einzige / letzte Durchquerung).foldr
.foldl
.In den meisten Fällen
foldr
ist dies die beste Falzfunktion, da die Durchlaufrichtung für die verzögerte Auswertung von Listen optimal ist. Es ist auch das einzige, das unendliche Listen verarbeiten kann. Die zusätzliche Strenge vonfoldl'
kann es in einigen Fällen schneller machen, dies hängt jedoch davon ab, wie Sie diese Struktur verwenden und wie faul sie ist.quelle
sum
wird foldl verwendet, nicht foldl '(es sei denn, sie haben dies kürzlich behoben).foldl1' (+) [1..100000000]
Die Ausführung erfolgt nahezu augenblicklich, während alle anderen Falten einige Sekunden dauern oder zu einem Stapelüberlauf führen.Ich glaube, noch hat niemand die wirkliche Antwort auf diese Frage gesagt, es sei denn, ich vermisse etwas (was durchaus wahr sein und mit Abstimmungen begrüßt werden kann).
Ich denke, der größte Unterschied in diesem Fall ist, dass
foldr
die Liste so aufgebaut ist:[0] ++ ([1] ++ ([2] ++ (... ++ [1000000])))
Während
foldl
die Liste wie folgt erstellt:((([0] ++ [1]) ++ [2]) ++ ...) ++ [999888]) ++ [999999]) ++ [1000000]
Der Unterschied ist subtil, aber beachten Sie, dass in der
foldr
Version++
immer nur ein Listenelement als linkes Argument vorhanden ist. Mit derfoldl
Version enthält das++
linke Argument bis zu 999999 Elemente (durchschnittlich etwa 500000), das rechte Argument jedoch nur ein Element.Es
++
braucht jedoch Zeit, die proportional zur Größe des linken Arguments ist, da es die gesamte Liste der linken Argumente bis zum Ende durchsehen und dann das letzte Element auf das erste Element des rechten Arguments setzen muss (im besten Fall muss es dies tatsächlich tun eine Kopie machen). Die richtige Argumentliste bleibt unverändert, es spielt also keine Rolle, wie groß sie ist.Deshalb ist die
foldl
Version viel langsamer. Es hat meiner Meinung nach nichts mit Faulheit zu tun.quelle
foldl
undfoldr
? Für mich hat OP zunächst ein schlechtes Beispiel aufgegriffen, weil sich die beiden Faltfunktionen drastisch unterscheiden.Das Problem ist, dass die Tail-Rekursionsoptimierung eine Speicheroptimierung und keine Ausführungszeitoptimierung ist!
Durch die Optimierung der Schwanzrekursion wird vermieden, dass Werte für jeden rekursiven Aufruf gespeichert werden müssen.
Foldl ist also tatsächlich "gut" und Foldr ist "schlecht".
Zum Beispiel unter Berücksichtigung der Definitionen von foldr und foldl:
foldl f z [] = z foldl f z (x:xs) = foldl f (z `f` x) xs foldr f z [] = z foldr f z (x:xs) = x `f` (foldr f z xs)
So wird der Ausdruck "foldl (+) 0 [1,2,3]" bewertet:
foldl (+) 0 [1, 2, 3] foldl (+) (0+1) [2, 3] foldl (+) ((0+1)+2) [3] foldl (+) (((0+1)+2)+3) [ ] (((0+1)+2)+3) ((1+2)+3) (3+3) 6
Beachten Sie, dass foldl sich nicht an die Werte 0, 1, 2 ... erinnert, sondern den gesamten Ausdruck (((0 + 1) +2) +3) träge als Argument übergibt und ihn erst bei der letzten Auswertung von auswertet foldl, wo es den Basisfall erreicht und den als zweiten Parameter (z) übergebenen Wert zurückgibt, der noch nicht ausgewertet ist.
Auf der anderen Seite funktioniert foldr so:
foldr (+) 0 [1, 2, 3] 1 + (foldr (+) 0 [2, 3]) 1 + (2 + (foldr (+) 0 [3])) 1 + (2 + (3 + (foldr (+) 0 []))) 1 + (2 + (3 + 0))) 1 + (2 + 3) 1 + 5 6
Der wichtige Unterschied besteht darin, dass foldl den gesamten Ausdruck im letzten Aufruf auswertet und nicht zurückkommen muss, um gespeicherte Werte zu erreichen. foldr merkt sich eine Ganzzahl für jeden Aufruf und führt bei jedem Aufruf eine Addition durch.
Es ist wichtig zu bedenken, dass Foldr und Foldl nicht immer gleichwertig sind. Versuchen Sie beispielsweise, diese Ausdrücke in Umarmungen zu berechnen:
foldr (&&) True (False:(repeat True)) foldl (&&) True (False:(repeat True))
foldr und foldl sind nur unter bestimmten hier beschriebenen Bedingungen gleichwertig
(Entschuldigung für mein schlechtes Englisch)
quelle
Für a muss die
[0.. 100000]
Liste sofort erweitert werden, damit foldr mit dem letzten Element beginnen kann. Dann, wenn es die Dinge zusammenfaltet, sind die Zwischenergebnisse[100000] [99999, 100000] [99998, 99999, 100000] ... [0.. 100000] -- i.e., the original list
Da niemand diesen Listenwert ändern darf (Haskell ist eine reine Funktionssprache), kann der Compiler den Wert wiederverwenden. Die Zwischenwerte wie
[99999, 100000]
können sogar einfach Zeiger in die erweiterte[0.. 100000]
Liste anstelle von separaten Listen sein.Schauen Sie sich für b die Zwischenwerte an:
[0] [0, 1] [0, 1, 2] ... [0, 1, ..., 99999] [0.. 100000]
Jede dieser Zwischenlisten kann nicht wiederverwendet werden. Wenn Sie das Ende der Liste ändern, haben Sie alle anderen Werte geändert, die darauf verweisen. Sie erstellen also eine Reihe zusätzlicher Listen, deren Aufbau einige Zeit in Anspruch nimmt. In diesem Fall verbringen Sie viel mehr Zeit damit, diese Listen, die Zwischenwerte sind, zuzuweisen und auszufüllen.
Da Sie nur eine Kopie der Liste erstellen, wird a schneller ausgeführt, da zunächst die vollständige Liste erweitert wird und dann ein Zeiger von der Rückseite der Liste nach vorne verschoben wird.
quelle
Weder
foldl
nochfoldr
ist der Schwanz optimiert. Es ist nurfoldl'
.In Ihrem Fall ist die Verwendung
++
mitfoldl'
jedoch keine gute Idee, da eine sukzessive Auswertung von++
immer wieder zu einem Durchqueren des wachsenden Akkumulators führt.quelle
Lassen Sie mich Ihre Funktionen so umschreiben, dass der Unterschied offensichtlich sein sollte -
a :: a -> [a] -> [a] a = (:) b :: [b] -> b -> [b] b = flip (:)
Sie sehen, dass b komplexer ist als a. Wenn Sie präzise sein möchten,
a
benötigen Sie einen Reduktionsschritt für die Berechnung des Werts, aberb
zwei. Das macht den Zeitunterschied, den Sie messen, aus. Im zweiten Beispiel müssen doppelt so viele Reduzierungen durchgeführt werden.// edit: Aber die zeitliche Komplexität ist die gleiche, also würde ich mich nicht viel darum kümmern.
quelle
a = flip $ flip (:)
und das hat die Ausführungszeit nicht merklich verändert, daher denke ich nicht, dass das Umdrehen der Argumente, um Foldl zu berücksichtigen, das Problem ist.