foldl gegen foldr Verhalten mit unendlichen Listen

Question

Der Code für die myAny Funktion in Diese Frage Verwendungen foldr. Es beendet die Verarbeitung eine unendliche Liste, wenn das Prädikat erfüllt ist.

ich es neu geschrieben foldl mit:

myAny :: (a -> Bool) -> [a] -> Bool
myAny p list = foldl step False list
   where
      step acc item = p item || acc

(Beachten Sie, dass die Argumente für die Sprungfunktion korrekt umgekehrt.)

Es ist jedoch nicht mehr beendet die Verarbeitung unendliche Listen.

Ich habe versucht, die Funktion der Ausführung wie in Apocalisp Antwort :

myAny even [1..]
foldl step False [1..]
step (foldl step False [2..]) 1
even 1 || (foldl step False [2..])
False  || (foldl step False [2..])
foldl step False [2..]
step (foldl step False [3..]) 2
even 2 || (foldl step False [3..])
True   || (foldl step False [3..])
True

Dies ist jedoch nicht die Art und Weise der Funktion verhält. Wie ist das falsch?

Answer 1

Wie folds unterscheiden scheint eine häufige Quelle der Verwirrung zu sein, so ist hier eine allgemeinere Übersicht:

Betrachten Sie eine Liste von n Werten Falten [x1, x2, x3, x4 ... xn ] mit irgendeiner Funktion f und Samen z.

foldl lautet:

• Linke assoziativen : f ( ... (f (f (f (f z x1) x2) x3) x4) ...) xn
• Schwanz rekursive : Es ist die Liste durchläuft, um den Wert der Herstellung danach
• Faule : Nichts ausgewertet wird, bis das Ergebnis benötigt wird,
• rückwärts :. foldl (flip (:)) [] kehrt eine Liste

foldr lautet:

• Recht assoziativ : f x1 (f x2 (f x3 (f x4 ... (f xn z) ... )))
• Recursive in ein Argument . Jede Iteration f auf den nächsten Wert gilt und das Ergebnis der Rest der Liste Klapp
• Faule : Nichts ausgewertet wird, bis das Ergebnis benötigt wird,
• Vorwärts :. foldr (:) [] kehrt eine Liste unverändert

Es ist ein etwas subtiler Punkt hier, dass Reise Menschen manchmal bis: Weil foldl ist zurück jede Anwendung von f auf die außen hinzugefügt wird des Ergebnisses; und weil es faul , wird nichts ausgewertet, bis das Ergebnis erforderlich ist. Dies bedeutet, dass irgendein Teil des Ergebnisses, Haskell erster iteriert zu berechnen durch die gesamte Liste einen Ausdruck von verschachtelten Funktionsanwendungen konstruiert, wertet dann die äußerste Funktion, zu bewerten ihre Argumente als erforderlich. Wenn f immer ihr erstes Argument verwendet, hat dieses Mittel Haskell recurse den ganzen Weg hinunter zum innersten Ausdruck, dann rückwärts arbeiten Berechnung jede Anwendung von f.

Das ist natürlich ein Schrei weit von der effizienten Schwanz-Rekursion funktionellste Programmierer kennen und lieben!

In der Tat, obwohl foldl technisch Schwanz-rekursiv ist, da der gesamte Ergebnisausdruck, bevor die Bewertung etwas gebaut wird, foldl kann einen Stapelüberlauf verursachen!

Auf der anderen Seite betrachtet foldr. Es ist auch faul, sondern weil es läuft vorwärts , jede Anwendung von f ist mit dem innen des Ergebnisses hinzugefügt. Also, um das Ergebnis zu berechnen, erstellt Haskell eine Single Funktionsanwendung, das zweite Argument, von denen der Rest der gefalteten Liste. Wenn f in seinem zweiten Argumente faul ist - ein Datum Konstruktor, zum Beispiel - wird das Ergebnis sein inkrementell faul , mit jedem Schritt der einzigen berechnet falten, wenn ein Teil des Ergebnisses, dass der Bedarf ist bewertet.

So können wir sehen, warum manchmal foldr auf unendliche Listen funktioniert, wenn foldl nicht: Ersteres kann träge eine unendliche Liste in einer anderen faul unendliche Datenstruktur umwandeln, während letztere die gesamte Liste prüfen muss einen Teil des Ergebnisses zu erzeugen . Auf der anderen Seite, foldr mit einer Funktion, die beiden Argumente sofort (nicht funktioniert, oder besser gesagt), wie (+), Arbeiten brauchen viel wie foldl, einen großen Ausdruck bauen, bevor es zu bewerten.

So sind die zwei wichtige Punkte zu beachten sind diese:

• foldr kann man faul rekursive Datenstruktur in eine andere umwandeln.
• Ansonsten faul Falten wird mit einem Stapelüberlauf auf große oder unendliche Listen zum Absturz bringen.

Sie haben vielleicht bemerkt, dass es wie foldr klingt kann alles foldl tun kann, plus mehr. Das ist wahr! In der Tat, foldl ist fast nutzlos!

Aber was ist, wenn wir ein Nicht-faul Ergebnis produzieren wollen, indem über eine große Klapp (aber nicht unendlich) Liste? Dazu haben wir eine strengen Falten wollen , which den Standardbibliotheken thoughfully bieten

foldl' lautet:

• Linke assoziativen : f ( ... (f (f (f (f z x1) x2) x3) x4) ...) xn
• Schwanz rekursive : Es ist die Liste durchläuft, um den Wert der Herstellung danach
• Strenge : Jede Funktion Anwendung wird auf dem Weg ausgewertet
• rückwärts :. foldl' (flip (:)) [] kehrt eine Liste

Da foldl' ist strenge , um das Ergebnis zu berechnen Haskell wird bewerten f bei jedem Schritt, anstatt das linke Argument zu lassen, einen großen, unbewertet Ausdruck akkumulieren. Dies gibt uns die übliche, effiziente Endrekursion wir wollen! Mit anderen Worten:

• foldl' effizient große Listen falten.
• foldl' in einer Endlosschleife hängen (nicht Ursache einen Stapelüberlauf) auf einer unendlichen Liste.

Das Haskell Wiki hat eine Seite dieses diskutieren, wie gut.

Answer 2

myAny even [1..]
foldl step False [1..]
foldl step (step False 1) [2..]
foldl step (step (step False 1) 2) [3..]
foldl step (step (step (step False 1) 2) 3) [4..]

etc.

Intuitiv ist foldl immer auf der „Außenseite“ oder „links“, so dass es zunächst erweitert wird. Ad infinitum.

Answer 3

Sie können in Haskell in der Dokumentation finden Sie unter hier dass foldl ist Schwanz-rekursive und wird nie zu Ende wenn eine unendliche Liste übergeben, da er nennt sich auf den nächsten Parameter, bevor sie einen Wert zurückgibt ...

Answer 4

Ich weiß nicht, Haskell, aber in Schema, fold-right wird immer ‚Handlung‘ auf dem letzten Element einer Liste zuerst. So wird nicht Arbeit für zyklische Liste (die die gleiche wie ein unendliches ist).

Ich bin nicht sicher, ob fold-right kann tail-rekursive geschrieben werden, sondern für jede zyklische Liste sollten Sie einen Stapelüberlauf bekommen. fold-left OTOH wird in der Regel mit Endrekursion durchgeführt werden und nur in einer Endlosschleife hängen bleiben, wenn sie nicht frühzeitig beendet wird.