foldr und foldl weitere Erläuterungen und Beispiele

Question

ich bei different folds und folding in general sowie ein paar andere haben gesucht und sie erklären es ziemlich gut.

Ich habe immer noch Probleme auf, wie eine Lambda in diesem Fall funktionieren würde.

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

Könnte jemand Schritt für Schritt durchgehen und versuchen, mir das zu erklären.

Und auch, wie würde auch foldl Arbeit.

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

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 3

Infixnotation wird wahrscheinlich hier klarer.

Start Lassen Sie uns 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] 

Answer 4

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 ist ähnlich der leeren Liste [],

[] :: [a] 

und ersetzt jede: 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 foldr als eine State-Maschine-Auswerter vorstellen, auch:

f der Übergang ist,

f :: input -> state -> state 

und e die 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 f in Infix-Notation vor, wenn der Pacman von RECHTS kommt.

faltl (foldLEFT) macht das gleiche von-LINKS, aber die Übergangsfunktion, geschrieben in Infix-Notation, nimmt ihr Eingabe-Argument von rechts. Die Maschine verbraucht also die Liste beginnend am linken Ende. Pacman konsumiert die Liste von-LINKS mit einem offenen Mund nach rechts, wegen des Mundes (b-> a-> b) anstelle von (a-> b-> b).

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

Um dies deutlich zu machen, um die Funktion minus als Übergang vorstellen:

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 wo die Auswertung faul sein sollte:

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 

Dem ersten -Schritt für Schritt - Erstellt einen Eintrag der Liste, wertet ihn aus und verbraucht ihn.

Die zweite erstellt zuerst eine sehr lange Formel, die Speicher mit ((... ((0 + 1) +2) +3) + ...) verschwendet und anschließend alles auswertet.

Die dritte wie die zweite, aber mit der anderen Formel.