foldr und foldl weitere Erläuterungen und Beispiele

Question

Ich habe unter verschiedene Falten und

War es hilfreich?

einreichen

Lösung

Mit

foldr f z []     = z
foldr f z (x:xs) = x `f` foldr f z xs

Und

k y ys = ys ++ [y]

Lassen Sie uns auspacken:

foldr k [] [1,2,3]
= k 1 (foldr k [] [2,3]
= k 1 (k 2 (foldr k [] [3]))
= k 1 (k 2 (k 3 (foldr k [] [])))
= (k 2 (k 3 (foldr k [] []))) ++ [1]
= ((k 3 (foldr k [] [])) ++ [2]) ++ [1]
= (((foldr k [] []) ++ [3]) ++ [2]) ++ [1]
= ((([]) ++ [3]) ++ [2]) ++ [1]
= (([3]) ++ [2]) ++ [1]
= ([3,2]) ++ [1]
= [3,2,1]

Answer 1

Mit

foldr f z []     = z
foldr f z (x:xs) = x `f` foldr f z xs

Und

k y ys = ys ++ [y]

Lassen Sie uns auspacken:

foldr k [] [1,2,3]
= k 1 (foldr k [] [2,3]
= k 1 (k 2 (foldr k [] [3]))
= k 1 (k 2 (k 3 (foldr k [] [])))
= (k 2 (k 3 (foldr k [] []))) ++ [1]
= ((k 3 (foldr k [] [])) ++ [2]) ++ [1]
= (((foldr k [] []) ++ [3]) ++ [2]) ++ [1]
= ((([]) ++ [3]) ++ [2]) ++ [1]
= (([3]) ++ [2]) ++ [1]
= ([3,2]) ++ [1]
= [3,2,1]

Answer 2

foldr ist eine einfache Sache:

foldr :: (a->b->b) -> b -> [a] -> b

Es dauert eine Funktion, die irgendwie ähnlich ist (:)

(:) :: a -> [a] -> [a]

und ein Wert, der auf die leere Liste ähnlich ist [],

[] :: [a]

und ersetzt jeweils: und [] in irgendeiner Liste

.

Es sieht wie folgt aus:

foldr f e (1:2:3:[]) = 1 `f` (2 `f` (3 `f` e))

Sie können als ein State-Maschine-Auswerter vorstellen foldr auch:

f ist der Übergang,

f :: input -> state -> state

und e ist der Startzustand.

e :: state

foldr (foldRIGHT) führt die Zustandsmaschine mit dem Übergang F und dem Startzustand E über die Liste der Eingänge, am rechten Ende beginnen. Stellen Sie sich vor f in Infixschreibweise als Pacman aus Richtung RECHTS.

foldl (foldLEFT) tut dasselbe aus-LEFT, aber die Übergangsfunktion, in Infix-Schreibweise geschrieben, nimmt sein Eingangsargument von rechts. So verbraucht die Maschine die Liste am linken Ende beginnt. Pacman verbraucht die Liste von-LEFT mit offenem Mund nach rechts, weil der Mund (b-> a-> b) anstelle von (a-> b-> b).

foldl :: (b->a->b) -> b -> [a] -> b

Um dies deutlich zu machen, stellen Sie sich die Funktion (-) als Übergang:

foldl (-) 100 [1]         = 99 = ((100)-1)
foldl (-) 100 [1,2]       = 97 = (( 99)-2) = (((100)-1)-2)
foldl (-) 100 [1,2,3]     = 94 = (( 97)-3)
foldl (-) 100 [1,2,3,4]   = 90 = (( 94)-4)
foldl (-) 100 [1,2,3,4,5] = 85 = (( 90)-5)

foldr (-) 100 [1]         = -99 = (1-(100))
foldr (-) 100 [2,1]       = 101 = (2-(-99)) = (2-(1-(100)))
foldr (-) 100 [3,2,1]     = -98 = (3-(101))
foldr (-) 100 [4,3,2,1]   = 102 = (4-(-98))
foldr (-) 100 [5,4,3,2,1] = -97 = (5-(102))

Sie wollen wahrscheinlich in Situationen verwenden foldr, wo die Liste unendlich sein kann, und in dem die Bewertung sollte faul sein:

foldr (either (\l ~(ls,rs)->(l:ls,rs))
              (\r ~(ls,rs)->(ls,r:rs))
      ) ([],[]) :: [Either l r]->([l],[r])

Und Sie wollen wahrscheinlich die strenge Version von foldl verwenden, die foldl ist‘, wenn Sie die ganze Liste verbrauchen seine Ausgabe zu erzeugen. Es könnte ein bessere Leistung und man könnte aus mit Stack-Überlauf oder out-of-memory Ausnahmen verhindern (je nach Compiler) aufgrund extrem langer Listen in Kombination mit lazy evaluation:

foldl' (+) 0 [1..100000000] = 5000000050000000
foldl  (+) 0 [1..100000000] = error "stack overflow or out of memory" -- dont try in ghci
foldr  (+) 0 [1..100000000] = error "stack overflow or out of memory" -- dont try in ghci

Die erste -Schritt für Schritt- erstellt einen Eintrag in der Liste, wertet sie aus und verspeist sie.

Die zweite eine schafft sehr lange Formel ersten, Speicher verschwenden mit ((... ((0 + 1) 2) 3) + ...) und wertet alle es danach.

Der dritte ist wie der zweite, aber mit der anderen Formel.

Answer 3

Die Definition von foldr ist:

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

Also hier ist ein Schritt für Schritt Reduktion Ihres Beispiel:

  foldr (\y ys -> ys ++ [y]) [] [1,2,3]
= (\y ys -> ys ++ [y]) 1 (foldr (\y ys -> ys ++ [y]) [] [2,3])
= (foldr (\y ys -> ys ++ [y]) [] [2,3]) ++ [1]
= (\y ys -> ys ++ [y]) 2 (foldr (\y ys -> ys ++ [y]) [] [3]) ++ [1]
= (foldr (\y ys -> ys ++ [y]) [] [3]) ++ [2] ++ [1]
= (\y ys -> ys ++ [y]) 3 (foldr (\y ys -> ys ++ [y]) [] []) ++ [2] ++ [1]
= (foldr (\y ys -> ys ++ [y]) [] []) ++ [3] ++ [2] ++ [1]
= [] ++ [3] ++ [2] ++ [1]
= [3,2,1]

Answer 4

Infixnotation wird wahrscheinlich hier klarer.

Beginnen wir mit der Definition:

foldr f z []     = z
foldr f z (x:xs) = x `f` (foldr f z xs)

Aus Gründen der Kürze, lassen Sie uns schreiben g statt (\y ys -> ys ++ [y]). Die folgenden Zeilen sind äquivalent:

foldr g [] [1,2,3]
1 `g` (foldr g [] [2,3])
1 `g` (2 `g` (foldr g [] [3]))
1 `g` (2 `g` (3 `g` (foldr g [] [])))
1 `g` (2 `g` (3 `g` []))
(2 `g` (3 `g` [])) ++ [1]
(3 `g` []) ++ [2] ++ [1]
[3] ++ [2] ++ [1]
[3,2,1]