Links und rechts Falten über eine unendliche Liste

72

Ich habe Probleme mit der folgenden Passage aus Learn You A Haskell (Großartiges Buch imo, ohne es zu dissen):

Ein großer Unterschied ist, dass rechte Falten auf unendlichen Listen funktionieren, linke nicht! Um es klar auszudrücken: Wenn Sie irgendwann eine unendliche Liste nehmen und sie von rechts zusammenfalten, erreichen Sie schließlich den Anfang der Liste. Wenn Sie jedoch an einem Punkt eine unendliche Liste nehmen und versuchen, sie von links zusammenzufalten, werden Sie niemals ein Ende erreichen!

Ich verstehe das einfach nicht. Wenn Sie eine unendliche Liste nehmen und versuchen, sie von rechts zusammenzufalten, müssen Sie an der Stelle im Unendlichen beginnen, was einfach nicht geschieht (Wenn jemand eine Sprache kennt, in der Sie dies tun können, sagen Sie: p ). Zumindest müssten Sie dort gemäß der Implementierung von Haskell beginnen, da in Haskell foldr und foldl kein Argument verwenden, das bestimmt, wo in der Liste sie mit dem Falten beginnen sollen.

Ich würde dem Zitat zustimmen, wenn foldr und foldl Argumente verwendet haben, die bestimmt haben, wo in der Liste sie mit dem Falten beginnen sollen, da es sinnvoll ist, wenn Sie eine unendliche Liste nehmen und direkt von einem definierten Index aus falten, wird sie schließlich enden, während dies nicht der Fall ist Es spielt keine Rolle, wo Sie mit einer linken Falte beginnen. Sie werden in Richtung Unendlichkeit falten. Foldr und Foldl nehmen dieses Argument jedoch nicht an, und daher macht das Zitat keinen Sinn. In Haskell wird sowohl eine linke als auch eine rechte Falte über eine unendliche Liste nicht beendet .

Ist mein Verständnis richtig oder fehlt mir etwas?

TheIronKnuckle
quelle
3
Vielleicht sollten Sie sich diese Frage in der entsprechenden Spalte ansehen
gatoatigrado
1
foldlund foldr beide verarbeiten die Liste von links nach rechts. Dies kann Ihnen helfen, Falten besser zu verstehen.
Matthias Braun

Antworten:

88

Der Schlüssel hier ist Faulheit. Wenn die Funktion, die Sie zum Falten der Liste verwenden, streng ist, wird bei einer unendlichen Liste weder eine linke noch eine rechte Falte beendet.

Prelude> foldr (+) 0 [1..]
^CInterrupted.

Wenn Sie jedoch versuchen, eine weniger strenge Funktion zu falten, erhalten Sie ein abschließendes Ergebnis.

Prelude> foldr (\x y -> x) 0 [1..]
1

Sie können sogar ein Ergebnis erhalten, das eine unendliche Datenstruktur darstellt. Obwohl es in gewisser Weise nicht beendet wird, kann es dennoch ein Ergebnis erzeugen, das träge verarbeitet werden kann.

Prelude> take 10 $ foldr (:) [] [1..]
[1,2,3,4,5,6,7,8,9,10]

Dies funktioniert jedoch nicht foldl, da Sie den äußersten Funktionsaufruf niemals auswerten können, ob faul oder nicht.

Prelude> foldl (flip (:)) [] [1..]
^CInterrupted.
Prelude> foldl (\x y -> y) 0 [1..]
^CInterrupted.

Beachten Sie, dass der Hauptunterschied zwischen einer linken und einer rechten Falte nicht in der Reihenfolge liegt, in der die Liste durchlaufen wird, die immer von links nach rechts verläuft, sondern darin, wie die resultierenden Funktionsanwendungen verschachtelt sind.

  • Mit foldrsind sie auf "der Innenseite" verschachtelt

    foldr f y (x:xs) = f x (foldr f y xs)
    

    Hier führt die erste Iteration zur äußersten Anwendung von f. Hat falso die Möglichkeit, faul zu sein, so dass das zweite Argument entweder nicht immer ausgewertet wird oder einen Teil einer Datenstruktur erzeugen kann, ohne das zweite Argument zu erzwingen.

  • Mit foldlsind sie "außen" verschachtelt

    foldl f y (x:xs) = foldl f (f y x) xs
    

    Hier können wir nichts bewerten, bis wir die äußerste Anwendung von erreicht haben f, die wir bei einer unendlichen Liste niemals erreichen werden, unabhängig davon, ob sie fstreng ist oder nicht.

Hammar
quelle
1
Das ist interessant: foldr (\ xy -> x) 0 [1 ..]. Ist es wirklich ein Beispiel für eine faule Bewertung? Oder ist nur der Compiler schlau? Ich sehe nicht, wie es jemals im traditionellen Sinne bewertet werden könnte, aber es ist ziemlich offensichtlich, wie hoch der endgültige Wert sein wird. Also bewertet GHC tatsächlich träge (und wenn ja, wie das *** ?: P) oder ist es gerade klug genug zu erkennen, dass die Antwort immer 1 sein wird?
TheIronKnuckle
2
@ThelronKnuckle Es ist faul Bewertung. Oder besser gesagt, es ist die nicht strenge Semantik von Haskell. Der Compiler darf das nicht ändern, egal wie schlau es ist.
August
@ThelronKnuckle Es ist eine verzögerte Auswertung, es sei denn, der Compiler führt eine Superkompilierung durch.
Fuz
Okay, gute, faule Bewertung mag es sein, aber irgendwann muss es bewertet werden, also was zum Teufel passiert eigentlich? Steckt es "unendlich" in den Akku, faltet es dann nach rechts und wackelt "unendlich - 1" im Akku, dann "unendlich - 2" und so weiter bis auf 1? Oder ist GHC gerade klug genug, um zu sehen, dass das Ergebnis 1 ist, und setzen Sie das stattdessen einfach ein?
TheIronKnuckle
3
@ TheIronKnuckle: So bewertet es:foldr (\x y -> x) 0 [1..] ={definition of foldr} (\x y -> x) 1 (foldr (\x y -> x) 0 [2..]) ={fill in x argument} (\y -> 1) (foldr (\x y -> x) 0 [2..]) ={fill in y argument} 1
Daniel Wagner
17

Der Schlüsselbegriff lautet "irgendwann".

Wenn Sie irgendwann eine unendliche Liste nehmen und sie von rechts zusammenfalten, erreichen Sie schließlich den Anfang der Liste.

Sie haben also Recht, Sie können unmöglich am "letzten" Element einer unendlichen Liste beginnen. Aber der Punkt des Autors ist folgender: Angenommen, Sie könnten. Wählen Sie einfach einen Punkt weit draußen (für Ingenieure ist dies "nah genug" bis unendlich) und fangen Sie an, nach links zu falten. Schließlich landen Sie am Anfang der Liste. Das Gleiche gilt nicht für die linke Falte. Wenn Sie einen Punkt da draußen auswählen (und ihn "nah genug" am Anfang der Liste nennen) und nach rechts falten, haben Sie noch einen unendlichen Weg vor sich.

Der Trick ist also, manchmal muss man nicht ins Unendliche gehen. Möglicherweise müssen Sie nicht einmal da draußen gehen. Möglicherweise wissen Sie jedoch nicht, wie weit Sie vorher gehen müssen. In diesem Fall sind unendliche Listen sehr praktisch.

Die einfache Darstellung ist foldr (:) [] [1..]. Lassen Sie uns die Falte durchführen.

Erinnern Sie sich daran foldr f z (x:xs) = f x (foldr f z xs). Auf einer unendlichen Liste, spielt es keine Rolle eigentlich nicht , was zist so ich behalte es genauso zstatt , []die clutters der Abbildung

foldr (:) z (1:[2..])         ==> (:) 1 (foldr (:) z [2..])
1 : foldr (:) z (2:[3..])     ==> 1 : (:) 2 (foldr (:) z [3..])
1 : 2 : foldr (:) z (3:[4..]) ==> 1 : 2 : (:) 3 (foldr (:) z [4..])
1 : 2 : 3 : ( lazily evaluated thunk - foldr (:) z [4..] )

Sehen Sie, wie in diesem Fall foldr, obwohl es sich theoretisch um eine Falte von rechts handelt , in diesem Fall einzelne Elemente der resultierenden Liste beginnend von links herausgekurbelt werden ? Wenn Sie also take 3aus dieser Liste hervorgehen, können Sie deutlich sehen, dass sie [1,2,3]die Falte produzieren kann und nicht weiter bewerten muss.

Dan Burton
quelle
7
Der Teil "Wählen Sie einen Punkt und arbeiten Sie von rechts zurück" ist hier wirklich der Schlüssel, nicht nur eine Illustration - denn der fragliche "Irgendwann" ist einfach der am weitesten entfernte Punkt, den Sie tatsächlich verwenden. Tatsächlich können wir also "Unendlichkeit" als "mindestens eine mehr definieren, als wir letztendlich brauchten", was meiner Meinung nach eine Definition ist, die sowohl Ingenieure als auch Mathematiker zufriedenstellen würde .
CA McCann
12

Denken Sie daran, dass Sie in Haskell aufgrund der verzögerten Auswertung unendliche Listen verwenden können. Also head [1..]ist nur 1 und head $ map (+1) [1..]ist 2, obwohl `[1 ..] unendlich lang ist. Wenn Sie das nicht bekommen, hören Sie auf und spielen Sie eine Weile damit. Wenn Sie das bekommen, lesen Sie weiter ...

Ich denke, ein Teil Ihrer Verwirrung ist, dass die foldlund foldrimmer auf der einen oder anderen Seite beginnen, daher müssen Sie keine Länge angeben.

foldr hat eine sehr einfache Definition

 foldr _ z [] = z
 foldr f z (x:xs) = f x $ foldr f z xs

Warum könnte dies auf unendlichen Listen enden?

 dumbFunc :: a -> b -> String
 dumbFunc _ _ = "always returns the same string"
 testFold = foldr dumbFunc 0 [1..]

hier gehen wir in foldrein "" (da der Wert keine Rolle spielt) und die unendliche Liste natürlicher Zahlen über. Beendet dies? Ja.

Der Grund dafür ist, dass die Bewertung von Haskell dem Umschreiben von faulen Begriffen entspricht.

Damit

 testFold = foldr dumbFunc "" [1..]

wird (um Mustervergleich zu ermöglichen)

 testFold = foldr dumbFunc "" (1:[2..])

das ist das gleiche wie (aus unserer Definition von Falte)

 testFold = dumbFunc 1 $ foldr dumbFunc "" [2..]

Jetzt dumbFunckönnen wir durch die Definition von schließen

 testFold = "always returns the same string"

Dies ist interessanter, wenn wir Funktionen haben, die etwas tun, aber manchmal faul sind. Zum Beispiel

foldr (||) False 

wird verwendet, um festzustellen, ob eine Liste TrueElemente enthält . Wir können dies verwenden, um die Funktion höherer Ordnung zu definieren, die genau dann anyzurückgibt, Truewenn die übergebene Funktion für ein Element der Liste wahr ist

any :: (a -> Bool) -> [a] -> Bool
any f = (foldr (||) False) . (map f)

Das Schöne an der faulen Bewertung ist, dass dies aufhört, wenn es auf das erste Element trifft , eso dassf e == True

Auf der anderen Seite trifft dies nicht zu foldl. Warum? Nun, ein wirklich einfaches foldlsieht aus wie

foldl f z []     = z                  
foldl f z (x:xs) = foldl f (f z x) xs

Was wäre nun passiert, wenn wir unser Beispiel oben ausprobiert hätten?

testFold' = foldl dumbFunc "" [1..]
testFold' = foldl dumbFunc "" (1:[2..])

das wird jetzt:

testFold' = foldl dumbFunc (dumbFunc "" 1) [2..]

damit

testFold' = foldl dumbFunc (dumbFunc (dumbFunc "" 1) 2) [3..]
testFold' = foldl dumbFunc (dumbFunc (dumbFunc (dumbFunc "" 1) 2) 3) [4..]
testFold' = foldl dumbFunc (dumbFunc (dumbFunc (dumbFunc (dumbFunc "" 1) 2) 3) 4) [5..]

und so weiter und so fort. Wir können niemals irgendwohin gelangen, weil Haskell immer zuerst die äußerste Funktion bewertet (das ist eine träge Bewertung auf den Punkt gebracht).

Eine coole Folge davon ist, dass Sie aus implementieren können foldl, foldraber nicht umgekehrt. Dies bedeutet, dass dies in gewisser Weise foldrdie grundlegendste aller Zeichenfolgenfunktionen höherer Ordnung ist, da es diejenige ist, mit der wir fast alle anderen implementieren. Sie wollen immer noch vielleicht ein verwenden , foldlmanchmal, da Sie können implementieren foldlSchwanz rekursiv, und einige Performance - Gewinn aus , dass bekommen.

Philip JF
quelle
Lesen Sie immer noch Ihren Beitrag und kommentieren Sie dabei: Wird dies auf einer unendlichen Liste von "falschen" Werten enden? foldr (||) False. Ich kann sehen, wie es auf einer unendlichen Liste enden würde, solange irgendwo ein Wahr drin ist, aber wenn die Liste für immer falsch ist, führt dies zu einer Nichtbeendigung, oder?
TheIronKnuckle
Ja, ich habe es gerade durch ghci laufen lassen (hätte es eigentlich erst machen sollen: P). Es wurde nicht beendet
TheIronKnuckle
Ich bin froh, dass mein Code korrekt war. Die Tatsache, dass es nicht endet, macht Sinn. Wenn Sie mir nacheinander eine Liste geben, kann ich nur sagen, ob sie bisher echte Werte hatte, nicht, ob dies in Zukunft der Fall sein wird. Der schnellste Weg, um festzustellen, ob eine Liste echte Elemente enthält, besteht darin, beim ersten anzuhalten, was der foldrCode tut. Offensichtlich wird "beim ersten anhalten" nicht beendet, wenn Sie kein erstes finden können ...
Philip JF
0

Es gibt gute einfache Erklärungen im Haskell-Wiki . Es zeigt eine schrittweise Reduzierung mit verschiedenen Arten von Falz- und Akkumulatorfunktionen.

xuesheng
quelle
-3

Du hast das richtig verstanden. Ich frage mich, ob der Autor versucht, über das faule Bewertungssystem von Haskell zu sprechen (in dem Sie eine unendliche Liste an verschiedene Funktionen ohne Falz übergeben können und die nur bewerten, wie viel für die Rückgabe der Antwort erforderlich ist). aber ich stimme Ihnen zu, dass der Autor keine gute Arbeit leistet, um irgendetwas in diesem Absatz zu beschreiben, und was darin steht, ist falsch.

Alan
quelle
4
Warum nicht falten ? Versuchen Sie dies:foldr (:) [] [1..]
n. 'Pronomen' m.
2
Nein. Der Absatz mag unklar sein , aber nichts, was darin steht, ist falsch . Es handelt sich um eine träge Bewertung, und die Begründung lautet genau, warum foldrtatsächlich an unendlichen Listen gearbeitet werden kann.
CA McCann
Dumm ist, dass ich, wenn ich das Buch nur weiter gelesen hätte, nur wenige Seiten später auf die Erklärung
gestoßen