Funktionen definieren mit foldl foldr

Question

Ich verstehe die Definitionen von foldl, foldr, aber ich habe Probleme mit Funktionen durch sie definiert.

Zum Beispiel Karte mit foldr:

map f []  = [] 
map f l = foldr (\x xs -> f x : xs) [] l 

Ich verstehe nicht, die (\x xs -> f x : xs). Es ist die Kartenfunktion, die foldr nimmt? Aber sollte es nicht (\x xs -> f x : f xs) sein, weil map f (x:xs) = f x : map f xs?

Beispiel mit foldl:

concat (x:xs) = x ++ concat xs 

concat' xs = foldl (++) [] xs 
concat'' xs = foldl (\ys y -> ys ++ y) [] xs 

Natürlich ich (++) verstehen, aber was ist die Logik hinter (\ys y -> ys ++ y)? Ist es ys = [] und y = xs? Also die Funktion dauert [] als ys und y ist das erste Element von xs und concases die [] mit der y? Konkretes Beispiel:

concat'' [1,2,3] = foldl (\ys y -> ys ++ y) [] [1,2,3] 
=> foldl (\ys y -> ys ++ y) ((\ys y -> ys ++ y) [] [1]) [2,3] 
=> foldl (\ys y -> ys ++ y) [1] [2,3] 
=> foldl (\ys y -> ys ++ y) ((\ys y -> ys ++ y) [1] [2]) [3] 
=> foldl (\ys y -> ys ++ y) [1,2] [3] 
=> foldl (\ys y -> ys ++ y) ((\ys y -> ys ++ y) [1,2] [3]) [] 
=> foldl (\ys y -> ys ++ y) [1,2,3] [] 
=> [1,2,3] 

Eine andere Sache: concat dauert nur 1 Liste xs, also wenn ich 2 Listen verketten wollen?

concat (x:xs) ys = x ++ concat xs ys 
concat [1,2,3] [4,5,6] with foldl? 

Rückseite:

reverse (x:xs) = reverse xs ++ [x] 

reverse' l = foldl (\xs x -> [x] : xs) [] l 
reverse'' l = foldr (\x xs -> xs ++ [x]) [] l 

Die foldr intuitiv klar ist (mit den Fragen von oben), aber was in foldl (\xs x -> [x] : xs) hinter der umgekehrten Reihenfolge ist? Diese foldl (\x xs -> xs ++ [x]) [] l wäre falsch, oder?

Vielen Dank!

Answer 1

Der Code

foldr (\x xs -> ...) end list 

, grob gelesen werden kann, wie folgt

• die ganzen scannen list
• wenn es leer ist, einfach zurückgeben Ende end
• sonst:
  • lassen x das Element zur Hand
  • lassen xs der Rest der Liste sein, nach
  • verarbeitet worden gelten die ... Betrieb

Der Teil ist entscheidend hervorgehoben. xs ist nicht der Rest der Liste, aber das Ergebnis des "rekursiven Aufrufs" darauf.

Tatsächlich ist xs ein schlechter Name dafür. Im allgemeinen Fall ist es nicht einmal eine Liste! Z.B.man würde nie (dummes Beispiel)

foldr (\x xs -> x + xs) 0 [1..100] -- sum 1..100 

schreiben, sondern eher so etwas wie

foldr (\x partialSum -> x + partialSum) 0 [1..100] -- sum 1..100 

bevorzugen (Eigentlich würde man nicht foldr Summe verwenden, aber lassen wir das beiseite.)

So, lesen Sie es einfach so:

map f l = foldr (\x mappedTail -> f x : mappedTail) [] l