foldr et foldl de plus amples explications et des exemples

J'ai regardé les différents plis et pliage en général ainsi que quelques autres, et ils l'expliquent assez bien.

Je suis toujours avoir des problèmes sur la façon dont un lambda pourrait fonctionner dans ce cas.

foldr (\y ys -> ys ++ [y]) [] [1,2,3]

Quelqu'un pourrait-il passer par cette étape-par-étape et essayer de m'expliquer?

Et aussi comment foldl travail?

OriginalL'auteur Matt | 2010-10-16

À l'aide de

foldr f z []     = z
foldr f z (x:xs) = x `f` foldr f z xs

k y ys = ys ++ [y]

Commençons à déballer:

foldr k [] [1,2,3]
= k 1 (foldr k [] [2,3]
= k 1 (k 2 (foldr k [] [3]))
= k 1 (k 2 (k 3 (foldr k [] [])))
= (k 2 (k 3 (foldr k [] []))) ++ [1]
= ((k 3 (foldr k [] [])) ++ [2]) ++ [1]
= (((foldr k [] []) ++ [3]) ++ [2]) ++ [1]
= ((([]) ++ [3]) ++ [2]) ++ [1]
= (([3]) ++ [2]) ++ [1]
= ([3,2]) ++ [1]
= [3,2,1]

OriginalL'auteur yfeldblum

28

foldr est une chose facile:
```
foldr :: (a->b->b) -> b -> [a] -> b
```
Elle prend une fonction qui est en quelque sorte similaire à (:),
```
(:) :: a -> [a] -> [a]
```
et une valeur qui est similaire à la liste vide [],
```
[] :: [a]
```
et remplace chaque : et [] dans certains liste.

Il ressemble à ceci:
```
foldr f e (1:2:3:[]) = 1 `f` (2 `f` (3 `f` e))
```
Vous pouvez l'imaginer foldr que certains de machine d'état-évaluateur, trop:

f est la transition,
```
f :: input -> state -> state
```
et e est l'état de départ.
```
e :: state
```
foldr (foldRIGHT) exécute la machine d'état avec la transition f et le début de l'état e sur la liste des entrées, en commençant à l'extrémité droite. Imaginez f en notation infixe comme le pacman venant de DROITE.

foldl (foldLEFT) fait de même à partir de la GAUCHE, mais la transition de la fonction, écrit en notation infixe, prend son argument d'entrée à partir de la droite. Donc, la machine consomme de la liste, en commençant à l'extrémité gauche. Pacman consomme la liste de GAUCHE avec la bouche ouverte vers la droite, en raison de la bouche (b->->b) au lieu de (a->b->b).
```
foldl :: (b->a->b) -> b -> [a] -> b
```
Que ce soit clair, imaginez la fonction moins que la transition:
```
foldl (-) 100 [1]         = 99 = ((100)-1)
foldl (-) 100 [1,2]       = 97 = (( 99)-2) = (((100)-1)-2)
foldl (-) 100 [1,2,3]     = 94 = (( 97)-3)
foldl (-) 100 [1,2,3,4]   = 90 = (( 94)-4)
foldl (-) 100 [1,2,3,4,5] = 85 = (( 90)-5)

foldr (-) 100 [1]         = -99 = (1-(100))
foldr (-) 100 [2,1]       = 101 = (2-(-99)) = (2-(1-(100)))
foldr (-) 100 [3,2,1]     = -98 = (3-(101))
foldr (-) 100 [4,3,2,1]   = 102 = (4-(-98))
foldr (-) 100 [5,4,3,2,1] = -97 = (5-(102))
```
Vous voudrez probablement utiliser foldr dans les situations où la liste peut être infini, et où l'évaluation doit être paresseux:
```
foldr (either (\l (ls,rs)->(l:ls,rs))
              (\r (ls,rs)->(ls,r:rs))
      ) ([],[]) :: [Either l r]->([l],[r])
```
Et vous voudrez probablement utiliser la version stricte de foldl, qui est foldl', lorsque vous consommez de l'ensemble de la liste pour produire sa sortie. Il peut mieux jouer et peut vous empêcher d'avoir de la pile de dépassement de capacité ou de capacité de mémoire des exceptions (en fonction du compilateur) en raison de l'extrême longues listes en combinaison avec d'évaluation différée:
```
foldl' (+) 0 [1..100000000] = 5000000050000000
foldl  (+) 0 [1..100000000] = error "stack overflow or out of memory" -- dont try in ghci
foldr  (+) 0 [1..100000000] = error "stack overflow or out of memory" -- dont try in ghci
```
La première étape par étape crée une entrée de la liste, les évalue, et il consomme.

Le second crée une très longue formule d'abord, de perdre la mémoire avec ((...((0+1)+2)+3)+...), et évalue l'ensemble de la suite.

Le troisième est identique à la seconde, mais avec l'autre formule.

+1 pour expliquer la sémantique et de donner une analogie. Les autres réponses ne donnent que réduction formelle, ce qui est important, mais pour la compréhension à un niveau conceptuel est encore plus important à mon humble avis.

OriginalL'auteur comonad

La définition de foldr est:

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

Voici donc étape par étape de réduction de votre exemple:

  foldr (\y ys -> ys ++ [y]) [] [1,2,3]
= (\y ys -> ys ++ [y]) 1 (foldr (\y ys -> ys ++ [y]) [] [2,3])
= (foldr (\y ys -> ys ++ [y]) [] [2,3]) ++ [1]
= (\y ys -> ys ++ [y]) 2 (foldr (\y ys -> ys ++ [y]) [] [3]) ++ [1]
= (foldr (\y ys -> ys ++ [y]) [] [3]) ++ [2] ++ [1]
= (\y ys -> ys ++ [y]) 3 (foldr (\y ys -> ys ++ [y]) [] []) ++ [2] ++ [1]
= (foldr (\y ys -> ys ++ [y]) [] []) ++ [3] ++ [2] ++ [1]
= [] ++ [3] ++ [2] ++ [1]
= [3,2,1]

OriginalL'auteur sepp2k

Notation infixe sera probablement plus clair ici.

Commençons par la définition:

foldr f z []     = z
foldr f z (x:xs) = x `f` (foldr f z xs)

Pour des raisons de concision, nous allons écrire g au lieu de (\y ys -> ys ++ [y]). Les lignes suivantes sont équivalentes:

foldr g [] [1,2,3]
1 `g` (foldr g [] [2,3])
1 `g` (2 `g` (foldr g [] [3]))
1 `g` (2 `g` (3 `g` (foldr g [] [])))
1 `g` (2 `g` (3 `g` []))
(2 `g` (3 `g` [])) ++ [1]
(3 `g` []) ++ [2] ++ [1]
[3] ++ [2] ++ [1]
[3,2,1]

OriginalL'auteur Bolo

Vous devez vous connecter pour publier un commentaire.