Implikationen von foldr vs. foldl (oder foldl ')

155

Erstens sagt Real World Haskell , das ich lese, dass man es niemals benutzen foldlund stattdessen benutzen soll foldl'. Also vertraue ich ihm.

Aber ich bin trüb , wenn die Verwendung foldrvs. foldl'. Obwohl ich die Struktur ihrer Funktionsweise vor mir sehen kann, bin ich zu dumm, um zu verstehen, wann "was besser ist". Ich denke, es scheint mir, dass es eigentlich keine Rolle spielen sollte, welche verwendet wird, da beide die gleiche Antwort liefern (nicht wahr?). Tatsächlich stammen meine früheren Erfahrungen mit diesem Konstrukt aus Rubys injectund Clojures reduce, die keine "linken" und "rechten" Versionen zu haben scheinen. (Nebenfrage: Welche Version verwenden sie?)

Jede Einsicht, die einer klugen Art wie mir helfen kann, wäre sehr dankbar!

J Cooper
quelle

Antworten:

174

Die Rekursion für foldr f x yswo ys = [y1,y2,...,yk]sieht aus

f y1 (f y2 (... (f yk x) ...))

während die Rekursion für foldl f x ysaussieht wie

f (... (f (f x y1) y2) ...) yk

Ein wichtiger Unterschied besteht darin, dass, wenn das Ergebnis von f x ynur mit dem Wert von berechnet werden kann x, foldrnicht die gesamte Liste untersucht werden muss. Beispielsweise

foldr (&&) False (repeat False)

kehrt zurück, Falsewährend

foldl (&&) False (repeat False)

endet nie. (Hinweis: repeat FalseErstellt eine unendliche Liste, in der sich jedes Element befindet False.)

Auf der anderen Seite foldl'ist der Schwanz rekursiv und streng. Wenn Sie wissen, dass Sie die gesamte Liste durchlaufen müssen, egal was passiert (z. B. die Zahlen in einer Liste summieren), foldl'ist dies platz- (und wahrscheinlich zeit-) effizienter als foldr.

Chris Conway
quelle
2
In foldr wird es als f y1 thunk ausgewertet, daher wird False zurückgegeben. In foldl kann f jedoch keinen seiner Parameter kennen. In Haskell können beide, egal ob es sich um eine Schwanzrekursion handelt oder nicht, einen Thunks-Überlauf verursachen, dh thunk ist zu groß. foldl 'kann den Thunk sofort während der Ausführung reduzieren.
Sawyer
25
Um Verwirrung zu vermeiden, beachten Sie, dass die Klammern nicht die tatsächliche Reihenfolge der Auswertung anzeigen. Da Haskell faul ist, werden zuerst die äußersten Ausdrücke ausgewertet.
Lii
Antwort erstellen. Ich möchte hinzufügen, dass Sie foldr verwenden müssen, wenn Sie eine Falte möchten, die auf halbem Weg durch eine Liste anhalten kann. Wenn ich mich nicht irre, können linke Falten nicht gestoppt werden. (Sie deuten dies an, wenn Sie sagen "Wenn Sie wissen ... werden Sie ... die gesamte Liste durchlaufen"). Außerdem sollte der Tippfehler "Nur für den Wert verwenden" in "Nur für den Wert verwenden" geändert werden. Dh das Wort "on" entfernen. (Stackoverflow ließ mich keine 2-Zeichen-Änderung einreichen!).
Lqueryvg
@Lqueryvg zwei Möglichkeiten, um linke Falten zu stoppen: 1. Code mit einer rechten Falte (siehe fodlWhile); 2. Konvertieren Sie es in einen linken Scan ( scanl) und stoppen Sie diesen mit last . takeWhile poder ähnlichem. Äh und 3. verwenden mapAccumL. :)
Will Ness
1
@Desty, weil es bei jedem Schritt einen neuen Teil seines Gesamtergebnisses erzeugt - im Gegensatz dazu foldl, dass es sein Gesamtergebnis sammelt und es erst erzeugt, wenn alle Arbeiten abgeschlossen sind und keine weiteren Schritte mehr ausgeführt werden müssen. Also zB foldl (flip (:)) [] [1..3] == [3,2,1], also scanl (flip(:)) [] [1..] = [[],[1],[2,1],[3,2,1],...]... IOW foldl f z xs = last (scanl f z xs)und unendliche Listen haben kein letztes Element (was im obigen Beispiel selbst eine unendliche Liste von INF bis 1 wäre).
Will Ness
57

foldr sieht aus wie das:

Rechtsfalte Visualisierung

foldl sieht aus wie das:

Visualisierung auf der linken Seite

Kontext: Falten Sie im Haskell-Wiki

Greg Bacon
quelle
33

Ihre Semantik unterscheidet sich, so dass Sie nicht einfach austauschen können foldlund foldr. Der eine faltet die Elemente von links zusammen, der andere von rechts. Auf diese Weise wird der Operator in einer anderen Reihenfolge angewendet. Dies ist für alle nicht assoziativen Operationen wie die Subtraktion von Bedeutung.

Haskell.org hat einen interessanten Artikel zu diesem Thema.

Konrad Rudolph
quelle
Ihre Semantik unterscheidet sich nur in trivialer Weise, was in der Praxis bedeutungslos ist: Die Reihenfolge der Argumente der verwendeten Funktion. In Bezug auf die Benutzeroberfläche gelten sie immer noch als austauschbar. Der wirkliche Unterschied scheint nur die Optimierung / Implementierung zu sein.
Evi1M4chine
2
@ Evi1M4chine Keiner der Unterschiede ist trivial. Im Gegenteil, sie sind substanziell (und in der Praxis sinnvoll). Wenn ich diese Antwort heute schreiben würde, würde dies diesen Unterschied noch mehr betonen.
Konrad Rudolph
23

Kurz gesagt, foldrist besser, wenn die Akkumulatorfunktion beim zweiten Argument faul ist. Lesen Sie mehr im Stack Overflow des Haskell-Wikis (Wortspiel beabsichtigt).

Mattiast
quelle
18

Der Grund, warum 99% aller Verwendungen foldl'bevorzugt werden, foldlist, dass es für die meisten Verwendungen auf konstantem Raum ausgeführt werden kann.

Übernimm die Funktion sum = foldl['] (+) 0. Wenn foldl'verwendet wird, wird die Summe sofort berechnet, so die Anwendung sumauf eine unendliche Liste lief nur für immer, und höchstwahrscheinlich in konstantem Raum (wenn Sie Dinge wie verwenden Ints, Doubles, Floats. IntegerS mehr als konstanter Raum verwendet, wenn die Anzahl wird größer als maxBound :: Int).

Mit foldlwird ein Thunk aufgebaut (wie ein Rezept, wie man die Antwort erhält, das später ausgewertet werden kann, anstatt die Antwort zu speichern). Diese Thunks können viel Platz beanspruchen, und in diesem Fall ist es viel besser, den Ausdruck zu bewerten, als den Thunk zu speichern (was zu einem Stapelüberlauf führt… und Sie zu… oh, egal)

Hoffentlich hilft das.

Axman6
quelle
1
Die große Ausnahme besteht darin, dass die an übergebene Funktion foldlnur Konstruktoren auf eines oder mehrere ihrer Argumente anwendet.
dfeuer
Gibt es ein allgemeines Muster, wann foldltatsächlich die beste Wahl ist? (Wie unendliche Listen, wenn foldrdie falsche Wahl ist, was die Optimierung
betrifft
@ Evi1M4chine nicht sicher, was Sie damit meinen foldr, die falsche Wahl für unendliche Listen zu sein. In der Tat sollten Sie nicht foldloder foldl'für unendliche Listen verwenden. Sehen Sie sich das Haskell-Wiki über Stapelüberläufe an
KevinOrr
14

By the way, Ruby injectund Clojure ist reducesind foldl(oder foldl1, je nachdem , welche Version Sie verwenden). Wenn es in einer Sprache nur eine Form gibt, handelt es sich normalerweise um eine linke Falte, einschließlich Pythons reduce, Perls List::Util::reduce, C ++ accumulate, C # Aggregate, Smalltalks inject:into:, PHPs array_reduce, Mathematica Foldusw. Die reduceStandardeinstellung von Common Lisp ist die linke Falte, es gibt jedoch eine Option für die rechte Falte.

newacct
quelle
2
Dieser Kommentar ist hilfreich, aber ich würde mich über Quellen freuen.
Titandecoy
Common Lisp's reduceist nicht faul, daher sind foldl'viele der Überlegungen hier nicht zutreffend.
MicroVirus
Ich denke du meinst foldl', da es sich um strenge Sprachen handelt, nein? Bedeutet das nicht, dass all diese Versionen Stapelüberläufe verursachen, wie dies der foldlFall ist?
Evi1M4chine
6

Wie Konrad betont, ist ihre Semantik unterschiedlich. Sie haben nicht einmal den gleichen Typ:

ghci> :t foldr
foldr :: (a -> b -> b) -> b -> [a] -> b
ghci> :t foldl
foldl :: (a -> b -> a) -> a -> [b] -> a
ghci> 

Beispielsweise kann der Listenanhangsoperator (++) mit foldras implementiert werden

(++) = flip (foldr (:))

während

(++) = flip (foldl (:))

gibt Ihnen einen Tippfehler.

Jonas
quelle
Ihr Typ ist der gleiche, nur vertauscht, was irrelevant ist. Ihre Schnittstelle und Ergebnisse sind bis auf das böse P / NP-Problem (sprich: unendliche Listen) gleich. ;) Die Optimierung aufgrund der Implementierung ist, soweit ich das beurteilen kann, der einzige Unterschied in der Praxis.
Evi1M4chine
@ Evi1M4chine Dies ist falsch. Sehen Sie sich dieses Beispiel an: foldl subtract 0 [1, 2, 3, 4]ausgewertet nach -10, während foldr subtract 0 [1, 2, 3, 4]ausgewertet nach -2. foldlist eigentlich 0 - 1 - 2 - 3 - 4solange foldrist 4 - 3 - 2 - 1 - 0.
krapht
@krapht, foldr (-) 0 [1, 2, 3, 4]ist -2und foldl (-) 0 [1, 2, 3, 4]ist -10. Auf der anderen Seite subtractist rückwärts von dem, was Sie erwarten könnten ( subtract 10 14ist 4), so foldr subtract 0 [1, 2, 3, 4]ist -10und foldl subtract 0 [1, 2, 3, 4]ist 2(positiv).
PianoJames