Come funziona foldr?

Question

Qualcuno può spiegare come funziona foldr?

Prendete questi esempi:

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

Sono confuso su queste esecuzioni. Eventuali suggerimenti?

Answer 1

foldr inizia all'estremità destra dell'elenco e combina ciascuna voce di elenco con il valore dell'accumulatore utilizzando la funzione assegnata. Il risultato è il valore finale dell'accumulatore dopo "piegatura" in tutti gli elementi della lista. Il suo tipo è:

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

e da questo si può vedere che l'elemento della lista (di tipo a) è il primo argomento della funzione data, e l'accumulatore (di tipo b) è la seconda.

Per il vostro primo esempio:

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

     ^Result from the previous line 

^ Next list item 

Quindi la risposta che ottenne fu 53.

Il secondo esempio:

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

Così il risultato è 12.

Edit : Volevo aggiungere, questo è per le liste finite. foldr può funzionare anche su elenchi infiniti, ma penso che sia meglio prima di tutto esaminare il caso finito.

Answer 2

foldr significa piega da destra, quindi foldr (-) 0 [1, 2, 3] produce (1 - (2 - (3 - 0))). Nel confronto foldl produce (((0 - 1) - 2) - 3).

Quando gli operatori non sono commutativefoldl e foldr otterranno risultati diversi.

Nel tuo caso, il primo esempio si espande a (10 - (11 - 54)) che dà 53.

Answer 3

pensare a foldr 's molto definition:

-- 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) 

Così, per esempio foldr (-) 54 [10,11] deve essere uguale (-) 10 (foldr (-) 54 [11]), vale a dire di nuovo in espansione, pari (-) 10 ((-) 11 54). Quindi l'operazione interna è 11 - 54, ovvero -43; e l'operazione esterna è 10 - (-43), ovvero 10 + 43, quindi 53 come si osserva. Passa attraverso passaggi simili per il tuo secondo caso, e di nuovo vedrai come si formano i risultati!

Answer 4

Ho sempre pensato che http://foldr.com fosse un'illustrazione divertente. Vedi il post Lambda the Ultimate.

Answer 5

Il modo più semplice per capire foldr è riscrivere la lista che si sta piegando senza lo zucchero.

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

ora quello foldr f x fa è che esso sostituisce ogni : con f in forma infissa e [] con x e valuta il risultato.

Ad esempio:

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

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

così

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

Answer 6

Un modo semplice per capire foldr è questo: Si sostituisce ogni lista costruttore con un'applicazione della funzione fornita. Il tuo primo esempio potrebbe tradurre in:

10 - (11 - 54)

da:

10 : (11 : [])

Un buon consiglio che ho ricevuto da Haskell Wikibook potrebbe essere di qualche utilità qui:

Come regola, è necessario utilizzare foldr in elenchi che potrebbero essere infiniti o dove la piega sta creando una struttura dati e foldl' se l'elenco è noto per essere finito e si riduce a un singolo valore. foldl (senza il segno di spunta) dovrebbe essere usato raramente.

Answer 7

Aiuta a comprendere la distinzione tra foldr e foldl. Perché è foldr chiamato "piega a destra"?

Inizialmente pensavo fosse perché consumava elementi da destra a sinistra. Eppure sia foldr e foldl consumano la lista da sinistra a destra.

• foldlviene valutata da sinistra a destra (-associativa a sinistra)
• foldrviene valutata da destra a sinistra (destra-associativo)

Possiamo fare questa distinzione chiaro con un esempio che utilizza un operatore per il quale l'associatività è importante. Potremmo usare un esempio umano, come ad esempio l'operatore, "mangia":

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) 

La semantica di questo foldl è: Un essere umano mangia qualche squalo, e poi lo stesso uomo che ha mangiato squalo poi mangia alcuni pesci, ecc. Il mangiatore è l'accumulatore.

Contrasto questo con:

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) 

La semantica di questo foldr è: Un essere umano mangia uno squalo che ha già mangiato un pesce, che ha già mangiato alcune alghe. Il cibo è l'accumulatore.

Entrambe foldl e foldr "sbucciano" i mangiatori da sinistra a destra, quindi non è questo il motivo per cui ci riferiamo a foldl come "left fold". Invece, l'ordine di valutazione è importante.

Answer 8

Ok, consente di guardare gli argomenti:

• una funzione (che prende un elemento di lista e un valore (un risultato possibile parziale) dello stesso tipo del valore restituito);
• una specifica del risultato iniziale per il caso speciale della lista vuota
• un elenco;

valore restituito:

• qualche risultato finale

Si applica prima l'all'ultimo elemento della lista e il risultato lista vuota. Quindi riapplica la funzione con questo risultato e l'elemento precedente, e così via fino a quando non si ottiene un risultato corrente e il primo elemento dell'elenco restituisce il risultato finale.

Piega "piega" un elenco attorno a un risultato iniziale utilizzando una funzione che accetta un elemento e un risultato di piegatura precedente. Ripete questo per ogni elemento. Quindi, foldr lo fa partendo dalla fine fuori dalla lista, o dal lato destro di esso.

folr f emptyresult [1,2,3,4] diventa f(1, f(2, f(3, f(4, emptyresult)))). Ora basta seguire la parentesi nella valutazione e basta.

Una cosa importante da notare è che la funzione fornita f deve gestire il proprio valore di ritorno come secondo argomento che implica che entrambi devono avere lo stesso tipo.

Fonte: my post dove lo guardo da una prospettiva javascript imperturbabile, se pensi che possa essere d'aiuto.

Answer 9

Penso che implementare la mappa, foldl e foldr in modo semplice aiuta a spiegare come funzionano. Anche esempi di lavoro aiutano nella nostra comprensione.

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