Comment fonctionne foldr?

Quelqu’un peut-il expliquer comment fonctionne foldr ?

Prenez ces exemples:

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

Je suis confus à propos de ces exécutions. Aucune suggestion?

foldr commence à l’extrémité droite de la liste et combine chaque entrée de la liste avec la valeur de l’accumulateur en utilisant la fonction que vous lui donnez. Le résultat est la valeur finale de l’accumulateur après “pliage” dans tous les éléments de la liste. Son type est:

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

et à partir de cela, vous pouvez voir que l’élément de liste (de type a ) est le premier argument de la fonction donnée et que l’accumulateur (de type b ) est le second.

Pour votre premier exemple:

 Starting accumulator = 54 11 - 54 = -43 10 - (-43) = 53 ^ Result from the previous line ^ Next list item 

Donc, la réponse que vous avez eue était 53.

Le deuxième exemple:

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

Donc le résultat est 12.

Edit: je voulais append, c’est pour les listes finies. foldr peut également travailler sur des listes infinies, mais je pense qu’il est préférable de se foldr sur le cas fini.

La manière la plus simple de comprendre foldr est de réécrire la liste que vous repliez sans le sucre.

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

maintenant ce que foldr fx fait, c’est qu’il les remplace : avec f en forme infixe et [] avec x et évalue le résultat.

Par exemple:

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

alors

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

Cela aide à comprendre la distinction entre foldr et foldl . Pourquoi foldr est- foldr appelé “fold right”?

Au départ, je pensais que c’était parce qu’il consommait des éléments de droite à gauche. Pourtant, foldr et foldl consumnt la liste de gauche à droite.

  • foldl évalue de gauche à droite (associatif à gauche)
  • foldr évalue de droite à gauche (associatif de droite)

Nous pouvons clarifier cette distinction avec un exemple utilisant un opérateur pour lequel l’associativité est importante. Nous pourrions utiliser un exemple humain, tel que l’opérateur, “mange”:

 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 sémantique de ce foldl est: Un humain mange du requin, puis le même homme qui a mangé du requin mange du poisson, etc. Le mangeur est l’accumulateur.

Contrastez ceci avec:

 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 sémantique de ce foldr est: Un humain mange un requin qui a déjà mangé un poisson, qui a déjà mangé des algues. La nourriture est l’accumulateur.

Les foldl et les foldr “décollent” les mangeurs de gauche à droite, ce n’est pas la raison pour laquelle nous nous référons à foldl comme “pli gauche”. Au lieu de cela, l’ordre d’évaluation est important.

Pensez à la foldr de foldr :

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

Donc, par exemple, foldr (-) 54 [10,11] doit être égal à (-) 10 (foldr (-) 54 [11]) , c’est-à-dire à nouveau en expansion, égal (-) 10 ((-) 11 54) . Donc, l’opération interne est 11 - 54 , c’est-à-dire -43; et l’opération externe est 10 - (-43) , soit 10 + 43 , donc 53 comme vous observez. Passez par des étapes similaires pour votre deuxième cas, et encore une fois, vous verrez comment le résultat se forme!

foldr signifie pli de la droite, donc foldr (-) 0 [1, 2, 3] produit (1 - (2 - (3 - 0))) . En comparaison, foldl produit (((0 - 1) - 2) - 3) .

Lorsque les opérateurs ne sont pas commutatifs, foldl et foldr obtiendront des résultats différents.

Dans votre cas, le premier exemple se développe en (10 - (11 - 54)) qui donne 53.

Une manière simple de comprendre foldr est la suivante: il remplace chaque constructeur de liste par une application de la fonction fournie. Votre premier exemple se traduirait par:

10 - (11 - 54)

de:

10 : (11 : [])

Un bon conseil du Haskell Wikibook pourrait être utile ici:

En règle générale, vous devez utiliser foldr sur des listes qui pourraient être infinies ou dans lesquelles le fold est en foldl' construire une structure de données, et foldl' si la liste est connue pour être finie et se réduire à une seule valeur. foldl (sans la tique) devrait rarement être utilisé du tout.

J’ai toujours pensé que http://foldr.com était une illustration amusante. Voir le message Lambda the Ultimate .

Je pense que l’implémentation simple de map, foldl et foldr aide à expliquer leur fonctionnement. Les exemples travaillés consortingbuent également à notre compréhension.

  myMap f [] = [] myMap f (x:xs) = fx : myMap f xs myFoldL fi [] = i myFoldL fi (x:xs) = myFoldL f (fix) 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 fz [] = z myFoldR fz (x:xs) = fx (myFoldR fz 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 (\xy -> (x+y)/2) 54 [12, 4, 10, 6] ==> 10.125 > myFoldL (\xy -> (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 (\xy -> (x+y)/2) 54 [12,4,10,6] ==> 12 > myFoldR' (\xy -> (x+y)/2) 54 [12,4,10,6] ==> 12 > myFoldR (\xy -> (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 

Ok, regardons les arguments:

  • une fonction (qui prend un élément de liste et une valeur (résultat partiel possible) du même type que la valeur renvoyée);
  • une spécification du résultat initial pour le cas particulier de la liste vide
  • une liste;

valeur de retour:

  • un résultat final

Il applique d’abord la fonction au dernier élément de la liste et au résultat de la liste vide. Il réapplique ensuite la fonction avec ce résultat et l’élément précédent, et ainsi de suite jusqu’à ce qu’il prenne un résultat courant et le premier élément de la liste pour renvoyer le résultat final.

Plier “plie” une liste autour d’un résultat initial en utilisant une fonction qui prend un élément et un résultat de pliage précédent. Il répète cela pour chaque élément. Donc, foldr le fait à partir de la fin de la liste ou du côté droit.

folr f emptyresult [1,2,3,4] se transforme en f(1, f(2, f(3, f(4, emptyresult) ) ) ) . Maintenant, il suffit de suivre la parenthèse dans l’évaluation et c’est tout.

Une chose importante à noter est que la fonction fournie f doit gérer sa propre valeur de retour comme deuxième argument, ce qui implique que les deux doivent avoir le même type.

Source: mon post où je le regarde depuis une perspective javascript impérative non testée si vous pensez que cela pourrait vous aider.