Wie funktioniert der Folder?

Question

Kann mir jemand erklären, wie funktioniert foldr?

Nehmen Sie diese Beispiele:

Prelude> foldr (-) 54 [10, 11] 
53 
Prelude> foldr (\x y -> (x+y)/2) 54 [12, 4, 10, 6] 
12.0 

ich über diese Hinrichtungen verwirrt bin. Irgendwelche Vorschläge?

Answer 1

foldr beginnt am rechten Ende der Liste und kombiniert jeden Listeneintrag mit dem Akkumulatorwert unter Verwendung der Funktion, die Sie ihm geben. Das Ergebnis ist der Endwert des Akkumulators nach dem "Falten" in allen Listenelementen. Seine Art ist:

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

und daraus kann man sehen, dass das Listenelement (vom Typ a) ist das erste Argument für die gegebene Funktion und der Speicher (vom Typ b) ist die zweite.

Für Ihr erstes Beispiel:

Starting accumulator = 54 
(6 + 54)/2 = 30 
(10 + 30)/2 = 20 
(4 + 20)/2 = 12 
(12 + 12)/2 = 12 

So das Ergebnis ist 12.

Edit:

Starting accumulator = 54 
11 - 54 = -43 
10 - (-43) = 53 

     ^Result from the previous line 

^ Next list item 

So ist die Antwort, die Sie 53.

Das zweite Beispiel war bekam : Ich wollte hinzufügen, das ist für endliche Listen. foldr kann auch auf unendlichen Listen arbeiten, aber es ist am besten, zuerst den endlichen Fall zu verstehen, denke ich.

Answer 2

foldr Mittel von rechts falten, so foldr (-) 0 [1, 2, 3](1 - (2 - (3 - 0))) produziert. Im Vergleich foldl produziert (((0 - 1) - 2) - 3).

Wenn die Operatoren nicht commutativefoldl und foldr werden unterschiedliche Ergebnisse erhalten.

In Ihrem Fall ist das erste Beispiel auf (10 - (11 - 54)) erweitert die 53.

Answer 3

über foldr ‚s sehr definition Denken gibt:

-- if the list is empty, the result is the initial value z 
foldr f z []  = z     
-- if not, apply f to the first element and the result of folding the rest 
foldr f z (x:xs) = f x (foldr f z xs) 

So zum Beispiel foldr (-) 54 [10,11](-) 10 (foldr (-) 54 [11]) wieder, dh gleich Ausbau betragen muss (-) 10 ((-) 11 54). Die innere Operation ist also 11 - 54, also -43; und die äußere Operation ist 10 - (-43), das heißt, 10 + 43, also 53 wie Sie beobachten. Gehen Sie ähnliche Schritte für Ihren zweiten Fall durch, und Sie werden wieder sehen, wie das Ergebnis aussieht!

Answer 4

Ich dachte immer http://foldr.com, um eine lustige Illustration zu sein. Siehe die Lambda the Ultimate Post.

Answer 5

Der einfachste Weg, um foldr zu verstehen, ist, die Liste, die Sie umklappen, ohne Zucker umzuschreiben.

[1,2,3,4,5] => 1:(2:(3:(4:(5:[])))) 

jetzt was foldr f x tut, ist, dass es jeden : mit f in Infix Form und [] mit x und wertet das Ergebnis ersetzt.

Zum Beispiel:

sum [1,2,3] = foldr (+) 0 [1,2,3] 

[1,2,3] === 1:(2:(3:[])) 

so

sum [1,2,3] === 1+(2+(3+0)) = 6 

Answer 6

Eine einfache Möglichkeit, foldr zu verstehen, ist dies: Es ersetzt jede Liste Konstruktor mit einer Anwendung der Funktion zur Verfügung gestellt. Ihr erstes Beispiel würde übersetzen:

10 - (11 - 54)

aus:

10 : (11 : [])

Ein guter Ratschlag, den ich aus der Haskell Wikibook bekam hier von Nutzen sein könnte:

In der Regel sollten Sie foldr für Listen verwenden, die unendlich sein können oder wo die Falte eine Datenstruktur erstellt, und foldl' Wenn die Liste als endlich bekannt ist und auf einen einzelnen Wert herunterkommt. foldl (ohne das Häkchen) sollte nur selten verwendet werden.

Answer 7

Es hilft, den Unterschied zwischen foldr und foldl zu verstehen. Warum heißt foldr "fold right"?

Ursprünglich dachte ich, es wäre, weil es Elemente von rechts nach links verbraucht. Aber beide foldr und foldl verbrauchen die Liste von links nach rechts.

• foldlwertet von links nach rechts (links-assoziativ)
• foldrwerten von rechts nach links (rechts-assoziativ)

Wir diese Unterscheidung klar machen können mit einem Beispiel das verwendet einen Operator, für den Assoziativität wichtig ist. Wir könnten ein menschliches Beispiel, wie der Operator „eats“:

foodChain = (human : (shark : (fish : (algae : [])))) 

foldl step [] foodChain 
    where step eater food = eater `eats` food -- note that "eater" is the accumulator and "food" is the element 

foldl `eats` [] (human : (shark : (fish : (algae : [])))) 
    == foldl eats (human `eats` shark)        (fish : (algae : [])) 
    == foldl eats ((human `eats` shark) `eats` fish)    (algae : []) 
    == foldl eats (((human `eats` shark) `eats` fish) `eats` algae) [] 
    ==   (((human `eats` shark) `eats` fish) `eats` algae) 

Die Semantik dieser foldl ist: Ein Mensch etwas Hai frisst, und dann der gleiche Mensch, der Hai gefressen hat frisst dann einige Fische, usw. Der Esser ist der Akkumulator.

Kontrast dies mit:

foldr step [] foodChain 
    where step food eater = eater `eats` food. -- note that "eater" is the element and "food" is the accumulator 

foldr `eats` [] (human : (shark : (fish : (algae : [])))) 
    == foldr eats (human `eats` shark)        (fish : (algae : [])))) 
    == foldr eats (human `eats` (shark `eats` (fish))    (algae : []) 
    == foldr eats (human `eats` (shark `eats` (fish `eats` algae))) [] 
    ==   (human `eats` (shark `eats` (fish `eats` algae) 

Die Semantik dieser foldr ist: Ein Mensch isst ein Hai, der einen Fisch schon gegessen hat, die bereits einige Algen gefressen hat. Das Essen ist der Akkumulator.

Sowohl foldl als auch foldr "peel off" Esser von links nach rechts, so das ist nicht der Grund, warum wir auf Foldl als "linke Falte" beziehen. Stattdessen ist die Reihenfolge der Bewertung wichtig.

Answer 8

Ok, lässt sich die Argumente aus:

• eine Funktion (das dauert ein Listenelement und einen Wert (eine mögliche Teilergebnis) von der gleichen Art des Wertes kehrt);
• eine Spezifikation des Anfangsergebnisses für den Sonderfall der leeren Liste
• eine Liste;

Rückgabewert:

• einige Endergebnisses

Es gilt zunächst die Funktion auf das letzte Element in der Liste und die leere Liste Ergebnis. Anschließend wendet es die Funktion mit diesem Ergebnis und dem vorherigen Element an, bis es ein aktuelles Ergebnis und das erste Element der Liste das endgültige Ergebnis zurückgibt.

Falten "faltet" eine Liste um ein anfängliches Ergebnis mit einer Funktion, die ein Element und ein vorheriges Faltungsergebnis verwendet. Dies wiederholt sich für jedes Element. Foldr beginnt also am Ende der Liste oder auf der rechten Seite.

folr f emptyresult [1,2,3,4] wird zu f(1, f(2, f(3, f(4, emptyresult)))). Jetzt folgt nur die Klammer in der Auswertung und das war's.

Eine wichtige Sache zu beachten ist, dass die mitgelieferte Funktion f ihren eigenen Rückgabewert als zweites Argument behandeln muss, was bedeutet, dass beide den gleichen Typ haben müssen.

Quelle: my post wo ich es von einer imperativ unverdünnten Javascript-Perspektive betrachten, wenn Sie denken, dass es helfen könnte.

Answer 9

Ich denke, dass die Implementierung von map, foldl und foldr auf einfache Weise hilft, zu erklären, wie sie funktionieren. Gearbeitete Beispiele helfen auch bei unserem Verständnis.

myMap f [] = [] 
    myMap f (x:xs) = f x : myMap f xs 

    myFoldL f i [] = i 
    myFoldL f i (x:xs) = myFoldL f (f i x) xs 

    > tail [1,2,3,4] ==> [2,3,4] 
    > last [1,2,3,4] ==> 4 
    > head [1,2,3,4] ==> 1 
    > init [1,2,3,4] ==> [1,2,3] 

    -- where f is a function, 
    -- acc is an accumulator which is given initially 
    -- l is a list. 
    -- 
    myFoldR' f acc [] = acc 
    myFoldR' f acc l = myFoldR' f (f acc (last l)) (init l) 

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

    > map (\x -> x/2) [12,4,10,6] ==> [6.0,2.0,5.0,3.0] 
    > myMap (\x -> x/2) [12,4,10,6] ==> [6.0,2.0,5.0,3.0] 

    > foldl (\x y -> (x+y)/2) 54 [12, 4, 10, 6] ==> 10.125 
    > myFoldL (\x y -> (x+y)/2) 54 [12, 4, 10, 6] ==> 10.125 

    foldl from above: Starting accumulator = 54 
     (12 + 54)/2 = 33 
     (4 + 33)/2 = 18.5 
     (10 + 18.5)/2 = 14.25 
     (6 + 14.25)/2 = 10.125` 

> foldr (++) "5" ["1", "2", "3", "4"] ==> "12345" 

> foldl (++) "5" ["1", "2", "3", "4"] ==> “51234" 

> foldr (\x y -> (x+y)/2) 54 [12,4,10,6] ==> 12 
> myFoldR' (\x y -> (x+y)/2) 54 [12,4,10,6] ==> 12 
> myFoldR (\x y -> (x+y)/2) 54 [12,4,10,6] ==> 12 

    foldr from above: Starting accumulator = 54 
     (6 + 54)/2 = 30 
     (10 + 30)/2 = 20 
     (4 + 20)/2 = 12 
     (12 + 12)/2 = 12