Come funziona Foldr?

Question

Qualcuno può spiegare come funziona foldr lavoro?

Prendi questi esempi:

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

Sono confuso riguardo a queste esecuzioni.Eventuali suggerimenti?

Answer 1

foldr inizia alla fine a destra della lista e combina ogni voce dell'elenco con il valore dell'accumulatore utilizzando la funzione si dà. Il risultato è il valore finale dell'accumulatore dopo "folding" 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 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.

Modifica: Volevo aggiungere, questo è per gli elenchi finiti. foldr può anche lavorare sulle liste infinite ma è meglio per ottenere la vostra testa intorno al caso finito prima, credo.

Answer 2

Il modo più semplice per capire foldr è quello di riscrivere la lista si sta ripiegando senza lo zucchero.

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

Ora che cosa foldr f x fa è che 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 3

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

Inizialmente pensavo che fosse perché consumava elementi da destra a sinistra.Eppure entrambi foldr E foldl consumare l'elenco da sinistra a destra.

• foldl valuta da sinistra a destra (associativo di sinistra)
• foldr valuta da destra a sinistra (associativo destro)

Possiamo chiarire questa distinzione con un esempio che utilizza un operatore per il quale l'associatività è importante.Potremmo usare un esempio umano, come 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 dello squalo, e poi lo stesso essere umano che ha mangiato lo squalo poi mangia del pesce, ecc.Il mangiatore è l'accumulatore.

Confrontalo 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 delle alghe.Il cibo è l'accumulatore.

Entrambi foldl E foldr "stacca" i mangiatori da sinistra a destra, quindi non è questo il motivo per cui ci riferiamo a foldl come "piega sinistra".Conta invece l’ordine di valutazione.

Answer 4

Pensate di foldr molto definizione :

 -- 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]), cioè nuovamente espandendo, (-) 10 ((-) 11 54) uguali. Quindi l'operazione interna è 11 - 54, cioè, -43; e l'operazione esterno è 10 - (-43), cioè 10 + 43, quindi 53 come si osserva. Passare attraverso una procedura simile per il vostro secondo caso, e di nuovo si vedrà come le forme di risultato!

Answer 5

foldr significa piega da destra, in modo foldr (-) 0 [1, 2, 3] produce (1 - (2 - (3 - 0))). In confronto foldl produce (((0 - 1) - 2) - 3).

Quando gli operatori non sono commutativa foldl e foldr otterrà risultati diversi.

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

Answer 6

Un modo semplice per capire foldr è questo: 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 si dovrebbe usare foldr su liste che potrebbero essere infinita o dove il pieghevole è la costruzione di una struttura di dati, e foldl' se la lista è noto per essere finito e si riduce a un singolo valore. foldl (senza il segno di spunta) dovrebbe essere raramente utilizzato a tutti.

Answer 7

Ho sempre pensato http://foldr.com di essere un esempio divertente. Vedere la Lambda Ultimate palo.

Answer 8

Credo che l'attuazione di mappa, foldl e foldr in modo semplice aiuta a spiegare come funzionano. esempi pratici di aiuto anche 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

Answer 9

Ok, consente di guardare gli argomenti:

• una funzione (che prende un elemento dell'elenco e un valore (un possibile risultato parziale) dello stesso tipo del valore restituito);
• una specificazione del risultato iniziale per la lista vuota caso speciale
• una lista;

valore di ritorno:

• qualche risultato finale

Si applica prima l'all'ultimo elemento della lista e il risultato lista vuota. Si riapplica la funzione di questo risultato e l'elemento precedente, e così via fino a portare qualche risultato corrente ed il primo elemento della lista per restituire il risultato finale.

Piegatura "piega" un elenco attorno ad un primo risultato utilizzando una funzione che riceve un elemento e alcuni precedenti risultato piegatura. Si ripete l'operazione per ogni elemento. Così, foldr fa questo a partire dalla fine fuori dalla lista, o il lato destro di esso.

folr f emptyresult [1,2,3,4] si trasforma in f(1, f(2, f(3, f(4, emptyresult) ) ) ) . Ora basta seguire parentesi nella valutazione e il gioco è fatto.

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

Fonte: mio post dove guardo da un punto di vista javascript uncurried indispensabile se si pensa che potrebbe aiutare.