Links und rechts Falten über eine unendliche Liste

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?

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.

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.

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.

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

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.