Comment foldr ne fonctionne?

StackOverflow https://stackoverflow.com/questions/1757740

  •  20-09-2019
  •  | 
  •  

Question

Quelqu'un peut-il expliquer comment fonctionne foldr travailler?

Prenez ces exemples: 

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

Je suis confus au sujet de ces exécutions. Toutes les suggestions?

Était-ce utile?

La solution

foldr commence à la fin de 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 de cela, vous pouvez voir que l'élément de liste (de type a) est le premier argument de la fonction donnée, et 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 été 53.

Le deuxième exemple: 

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

Le résultat est donc 12.

Edit: Je voulais ajouter, c'est pour les listes finies. foldr peut aussi travailler sur des listes infinies, mais il est préférable d'obtenir votre tête dans le cas fini d'abord, je pense.

Autres conseils

La meilleure façon de comprendre foldr est de réécrire la liste que vous repliant sans sucre. 

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

maintenant ce que foldr f x fait est qu'il remplace chaque : avec f sous 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:[]))


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

Il aide à comprendre la distinction entre foldr et foldl. Pourquoi est-foldr appelé "pli droit"?

Dans un premier temps je pensais que c'était parce qu'il a consommé des éléments de droite à gauche. Pourtant, les deux foldr et foldl consomment la liste de gauche à droite.

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

On peut faire cette distinction claire avec un exemple qui utilise un opérateur pour lequel les questions d'associativité. Nous pourrions utiliser un exemple humain, comme 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 homme mange un peu de requin, puis le même homme qui a mangé le requin mange alors un peu de poisson, etc. Le mangeur est l'accumulateur

.

contraste 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 homme mange un requin qui a déjà mangé un poisson, qui a déjà mangé des algues. La nourriture est l'accumulateur.

Les deux foldl et foldr mangeurs « décollent » de gauche à droite, de sorte que ce n'est pas la raison pour laquelle nous faisons référence à foldl comme « pli gauche ». Au lieu de cela, l'ordre des questions d'évaluation.

Pensez à très définition de foldr: 

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

Ainsi, par exemple foldr (-) 54 [10,11] doit être égale (-) 10 (foldr (-) 54 [11]), à savoir l'élargissement à nouveau, égale (-) 10 ((-) 11 54). Ainsi, l'opération intérieure est 11 - 54, qui est, -43; et l'opération extérieure est 10 - (-43), qui est, 10 + 43 donc 53 que vous observez. Passez par étapes similaires pour votre second cas, et encore, vous verrez comment les formes de résultat!

foldr des moyens de pliage de la droite, de sorte que 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 commutative foldl et foldr obtiendra des résultats différents.

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

Un moyen facile de comprendre foldr est la suivante: Il remplace chaque constructeur de liste avec une application de la fonction fournie. Votre premier exemple se traduirait par:

10 - (11 - 54)

à partir de:

10 : (11 : [])

Un bon conseil que je suis arrivé du Wikibook Haskell pourrait être utile ici:

  

En règle générale, vous devez utiliser foldr sur les listes qui pourraient être infini ou lorsque le pli est la construction d'une structure de données et foldl' si la liste est connue pour être finie et se résume à une seule valeur. foldl (sans la tique) devrait être utilisé que rarement du tout.

J'ai toujours pensé http://foldr.com être une illustration amusante. Voir Lambda le poste final.

Je pense que la mise en œuvre carte, foldl et foldr de façon simple permet d'expliquer comment ils fonctionnent. Exemples concrets aident également à comprendre. 

  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
Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top