foldl est récursive queue, alors comment se foldr fonctionne plus vite que foldl?

Question

Je voulais tester foldl vs foldr. D'après ce que je l'ai vu, vous devez utiliser foldl sur foldr chaque fois que vous pouvez grâce à l'optimisation de reccursion de queue.

Cela est logique. Cependant, après l'exécution de ce test, je suis confus:

foldr (0.057s prend l'utilisation de la commande dans le temps):

a::a -> [a] -> [a]
a x = ([x] ++ )

main = putStrLn(show ( sum (foldr a [] [0.. 100000])))

foldl (0.089s prend l'utilisation de la commande dans le temps):

b::[b] -> b -> [b]
b xs = ( ++ xs). (\y->[y])

main = putStrLn(show ( sum (foldl b [] [0.. 100000])))

Il est clair que cet exemple est trivial, mais je suis confus pour expliquer pourquoi foldr bat foldl. Ne devrait pas être ce un cas évident où gagne foldl?

Answer 1

Bienvenue dans le monde de l'évaluation paresseuse.

Quand vous pensez en termes d'évaluation stricte, ressemble foldl « bon » et ressemble FOLDR « mauvais » parce que foldl est récursive queue, mais foldr devrait construire une tour dans la pile de sorte qu'il peut traiter le dernier élément premier .

Cependant, l'évaluation paresseuse fait tourner les tables. Prenons, par exemple, la définition de la fonction carte:

map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs

Ce ne serait pas trop bon si Haskell utilisé une évaluation stricte, car il faudrait calculer la première queue, préfixer alors l'élément (pour tous les éléments de la liste). La seule façon de le faire serait efficace de construire les éléments en sens inverse, il semble.

Cependant, grâce à l'évaluation paresseuse de Haskell, cette fonction de carte est en fait efficace. Les listes de Haskell peuvent être considérés comme des générateurs, et cette fonction de carte génère son premier point en appliquant f au premier élément de la liste d'entrée. Quand il a besoin d'un deuxième élément, il fait exactement la même chose à nouveau (sans utiliser d'espace).

Il se peut que map être décrit en termes de foldr:

map f xs = foldr (\x ys -> f x : ys) [] xs

Il est difficile de dire en regardant, mais des coups de pied d'évaluation paresseux à cause foldr peut donner f son premier argument tout de suite:

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

Parce que le f défini par map peut renvoyer le premier élément de la liste de résultats en utilisant uniquement le premier paramètre, le pli peut fonctionner mollement dans l'espace constant.

Maintenant, l'évaluation paresseuse ne mord en arrière. Par exemple, essayez d'exécuter la somme [1..1000000]. Il donne un débordement de pile. Pourquoi faut-il? Il devrait juste évaluer de gauche à droite, à droite?

Regardons comment Haskell l'évalue:

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

sum = foldl (+) 0

sum [1..1000000] = foldl (+) 0 [1..1000000]
                 = foldl (+) ((+) 0 1) [2..1000000]
                 = foldl (+) ((+) ((+) 0 1) 2) [3..1000000]
                 = foldl (+) ((+) ((+) ((+) 0 1) 2) 3) [4..1000000]
                   ...
                 = (+) ((+) ((+) (...) 999999) 1000000)

Haskell est trop paresseux pour effectuer les ajouts comme il va. Au lieu de cela, il se retrouve avec une tour de thunks non évalués qui doivent être forcé d'obtenir un numéro. Le débordement de la pile se produit au cours de cette évaluation, car il doit récursif profondément pour évaluer toutes les thunks.

Heureusement, il existe une fonction spéciale appelée Data.List foldl' qui fonctionne strictement. foldl' (+) 0 [1..1000000] ne sera pas le débordement de pile. (Note: J'ai essayé de remplacer foldl avec foldl' dans votre test, mais il en fait fonctionner plus lentement.)

Answer 2

EDIT:. En regardant à nouveau ce problème, je pense que toutes les explications actuelles sont un peu insuffisants pour que j'ai écrit une explication plus

La différence est dans la façon dont foldl et foldr appliquent leur fonction de réduction. En regardant le cas de foldr, nous pouvons étendre comme

foldr (\x -> [x] ++ ) [] [0..10000]
[0] ++ foldr a [] [1..10000]
[0] ++ ([1] ++ foldr a [] [2..10000])
...

Cette liste est traitée par sum, qui consomme comme suit:

sum = foldl' (+) 0
foldl' (+) 0 ([0] ++ ([1] ++ ... ++ [10000]))
foldl' (+) 0 (0 : [1] ++ ... ++ [10000])     -- get head of list from '++' definition
foldl' (+) 0 ([1] ++ [2] ++ ... ++ [10000])  -- add accumulator and head of list
foldl' (+) 0 (1 : [2] ++ ... ++ [10000])
foldl' (+) 1 ([2] ++ ... ++ [10000])
...

Je l'ai laissé les détails de la concaténation de liste, mais voici comment la réduction se déroule. L'important est que tout est traité afin de minimiser les balayages des listes. Le foldr traverse seulement la liste une fois, les concaténations ne nécessitent pas la liste continue traversals et sum consomme enfin la liste en une seule passe. Critique, la tête de la liste est disponible à partir foldr immédiatement à sum, donc sum peut commencer à travailler immédiatement et les valeurs peuvent être gc'd car ils sont générés. Avec des cadres de fusion telles que vector, seront probablement fusionnées même les listes intermédiaires de distance.

Cela contraste à la fonction foldl:

b xs = ( ++xs) . (\y->[y])
foldl b [] [0..10000]
foldl b ( [0] ++ [] ) [1..10000]
foldl b ( [1] ++ ([0] ++ []) ) [2..10000]
foldl b ( [2] ++ ([1] ++ ([0] ++ [])) ) [3..10000]
...

Notez que maintenant la tête de la liste ne sont pas disponibles jusqu'à ce que foldl ait fini. Cela signifie que la liste entière doit être construite en mémoire avant sum peuvent commencer à travailler. Cela est beaucoup moins efficace globale. Exécution des deux versions avec +RTS -s spectacles misérables performances de collecte des ordures de la version foldl.

Il est également un cas où foldl' ne sera pas utile. La rigueur supplémentaire de foldl' ne change pas la façon dont la liste intermédiaire est créée. La tête de la liste reste indisponible jusqu'à ce que foldl » a terminé, le résultat sera toujours plus lent qu'avec foldr.

J'utilise la règle suivante pour déterminer le meilleur choix de fold

• Pour les plis qui sont réduction , l'utilisation foldl' (par exemple ce sera le seul / traversal final)
• Sinon, utilisez foldr.
• Ne pas utiliser foldl.

Dans la plupart des cas foldr est la meilleure fonction fois parce que la direction de traversal est optimal pour l'évaluation paresseuse des listes. Il est aussi le seul capable de traiter des listes infinies. La rigueur supplémentaire de foldl' peut le rendre plus rapide dans certains cas, mais cela dépend de la façon dont vous allez utiliser cette structure et la façon dont il est paresseux.

Answer 3

Je ne pense pas que quelqu'un est réellement dit la vraie réponse à ce pas encore, à moins que je me manque quelque chose (ce qui pourrait bien être vrai et accueilli avec downvotes).

Je pense que le plus grand différent dans ce cas est que foldr construit la liste comme ceci:

[0] ++ ([1] ++ ([2] ++ (++ ... [1000000])))

Alors que foldl construit la liste comme ceci:

((([0] ++ [1]) ++ [2]) ++ ...) ++ [999888]) ++ [999999]) ++ [1000000]

La différence subtile, mais avis que dans la version foldr ++ a toujours un seul élément de la liste comme argument gauche. Avec la version foldl, il y a jusqu'à 999999 éléments dans l'argument gauche de ++ (sur 500000 en moyenne), mais seulement un élément dans l'argument droit.

Cependant, ++ prend un temps proportionnel à la taille de l'argument gauche, car il doit regarder bien la liste complète des arguments de gauche à la fin et rejointoyer alors que le dernier élément au premier élément de l'argument droit (au mieux, peut-être il a réellement besoin de faire une copie). La liste des arguments droit ne change pas, il ne dépend pas de sa taille.

Voilà pourquoi la version foldl est beaucoup plus lente. Cela n'a rien à voir avec la paresse, à mon avis.

Answer 4

Le problème est que l'optimisation de la récursivité queue est une optimisation de la mémoire, pas une optimisation du temps d'exécution!

Optimisation de récursion Tail évite la nécessité de se rappeler des valeurs pour chaque appel récursif.

Alors, foldl est en fait "bon" et foldr est "mauvais".

Par exemple, compte tenu des définitions de foldr et foldl:

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

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

Voilà comment l'expression "foldl (+) 0 [1,2,3]" est évaluée:

foldl (+) 0 [1, 2, 3]
foldl (+) (0+1) [2, 3]
foldl (+) ((0+1)+2) [3]
foldl (+) (((0+1)+2)+3) [ ]
(((0+1)+2)+3)
((1+2)+3)
(3+3)
6

Notez que foldl ne se rappelle pas les valeurs 0, 1, 2 ..., mais passer toute l'expression (((0 + 1) 2) 3) comme argument paresseusement et ne l'évalue jusqu'à la dernière évaluation de foldl, où il atteint le cas de base et renvoie la valeur transmise en tant que second paramètre (z) wich n'a pas encore été évaluée.

D'autre part, voilà comment fonctionne foldr:

foldr (+) 0 [1, 2, 3]
1 + (foldr (+) 0 [2, 3])
1 + (2 + (foldr (+) 0 [3]))
1 + (2 + (3 + (foldr (+) 0 [])))
1 + (2 + (3 + 0)))
1 + (2 + 3)
1 + 5
6

La différence importante est que lorsque foldl évalue l'expression entière dans le dernier appel, ce qui évite la nécessité de revenir pour atteindre des valeurs souvenaient, FOLDR pas. foldr retenir un nombre entier pour chaque appel et exécute une addition à chaque appel.

est important de garder à l'esprit que foldr et foldl ne sont pas toujours équivalents. Par exemple, essayez de calculer ces expressions dans des câlins:

foldr (&&) True (False:(repeat True))

foldl (&&) True (False:(repeat True))

foldr et foldl sont équivalents que dans certaines conditions décrites ici

(désolé pour mon mauvais anglais)

Answer 5

Pour une, la liste des [0.. 100000] doit être élargi tout de suite afin que foldr peut commencer par le dernier élément. Puis, comme il se replie les choses ensemble, les résultats intermédiaires sont

[100000]
[99999, 100000]
[99998, 99999, 100000]
...
[0.. 100000] -- i.e., the original list

Parce que personne ne peut changer cette valeur de liste (Haskell est un langage fonctionnel pur), le compilateur est libre de réutiliser la valeur. Les valeurs intermédiaires, comme [99999, 100000] peuvent même être simplement des pointeurs dans la liste de [0.. 100000] élargi au lieu de listes séparées.

Pour b, regardez les valeurs intermédiaires:

[0]
[0, 1]
[0, 1, 2]
...
[0, 1, ..., 99999]
[0.. 100000]

Chacune de ces listes intermédiaires ne peut être réutilisé, parce que si vous changez la fin de la liste, vous avez changé d'autres valeurs qui l'indiquent. Donc, vous créez un tas de listes supplémentaires qui prennent le temps de construire en mémoire. Donc, dans ce cas, vous passez beaucoup plus de temps allouer et remplir ces listes qui sont des valeurs intermédiaires.

Puisque vous êtes juste faire une copie de la liste, un tourne plus vite, car il commence en élargissant la liste complète et ne cesse déplacer un pointeur à l'arrière de la liste à l'avant.

Answer 6

Ni foldl ni foldr est optimisé queue. Il est seulement foldl'.

Mais dans votre cas en utilisant ++ avec foldl' n'est pas une bonne idée parce que l'évaluation successive de ++ provoquera traverser encore et encore accumulateur de plus en plus.

Answer 7

Eh bien, permettez-moi de réécrire vos fonctions d'une manière que la différence devrait être évidente -

a :: a -> [a] -> [a]
a = (:)

b :: [b] -> b -> [b]
b = flip (:)

Vous voyez que b est plus complexe qu'un. Si vous voulez être précis a a besoin d'une étape de réduction de la valeur à calculer, mais il a besoin b deux. Cela fait la différence de temps que l'on mesure, dans le deuxième exemple deux fois plus des réductions beaucoup doivent être effectuées.

// edit:. Mais la complexité du temps est le même, donc je ne se soucier beaucoup