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

Question

J'ai voulu tester foldl vs foldr. De ce que j'ai vu que vous devriez utiliser foldl plus de foldr quand jamais vous pouvez en raison de queue reccursion d'optimisation.

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

foldr (prend en 0.057 s lorsque la durée d'utilisation de la commande):

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

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

foldl (prend 0.089 s lorsque la durée d'utilisation de la commande):

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 quant à pourquoi foldr bat foldl. Ne devrait-ce pas être un cas évident où foldl gagne?

Answer 1

Bienvenue dans le monde de l'évaluation différée.

Quand vous pensez à ce sujet en termes d'évaluation stricte, foldl semble "bon" et foldr semble "mauvais" parce que foldl est la queue récursive, mais foldr aurait pour construire une tour dans la pile de façon à pouvoir traiter le dernier élément de la première.

Cependant, l'évaluation différée tourne les tables. Prenez, par exemple, la définition de la fonction map:

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 rigoureuse, car elle aurait pour calculer la queue en premier, puis ajouter l'élément (pour tous les éléments de la liste). La seule façon de le faire de manière efficace serait de construire les éléments dans le sens inverse, il me semble.

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

Il s'avère qu' map peut être décrite en termes de foldr:

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

Il est difficile de dire en le regardant, mais lazy evaluation des coups de pied dans, car foldr peut donner des f son premier argument tout de suite:

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

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

Maintenant, paresseux évaluation ne morsure de retour. Par exemple, essayez d'exécuter la somme [1..1000000]. Il produit un débordement de pile. Pourquoi devrait-il? Il devrait évaluer de gauche à droite, de droite?

Regardons comment Haskell é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]
                   ...

Haskell est trop paresseux pour aller de l'avant et effectuer les ajouts, de sorte que cela donne un débordement de pile. Heureusement, il existe une fonction spéciale dans les Données.Liste appelée foldl' qui opère strictement. foldl' (+) 0 [1..1000000] n'aura pas de débordement de pile.

Note: j'ai essayé de remplacer foldl avec foldl' dans votre test, mais en fait il fait plus lent.

Answer 2

EDIT: en regardant ce problème, je pense que toutes les explications sont un peu insuffisants à ce que j'ai écrit une longue explication.

La différence est dans la façon dont foldl et foldr appliquer leur fonction de réduction. En regardant l' foldr de cas, nous pouvons l'é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, ce qui consomme de la façon suivante:

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

J'ai laissé de côté les détails de la liste de concaténation, mais c'est la manière dont la réduction des produits. L'important, c'est que tout est mis en oeuvre afin de minimiser la liste traversals. L' foldr seulement parcourt la liste une fois, les concaténations ne nécessitent pas de liste continue traversals, et sum enfin consomme de la liste en un seul passage. De façon critique, à la tête de la liste est disponible à partir de foldr immédiatement à l' sum, alors sum pouvez commencer à travailler immédiatement et les valeurs peuvent être gc avais comme ils sont générés. Avec la fusion des cadres tels que vector, même l'intermédiaire des listes sera probablement fusionné loin.

Contraste avec l' foldl fonction de:

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 n'est pas disponible jusqu' foldl a fini. Cela signifie que l'ensemble de la liste doit être construit dans la mémoire avant d' sum pouvez commencer à travailler. C'est beaucoup moins efficace dans son ensemble. L'exécution de ces deux versions, avec des +RTS -s montre misérable de collecte des ordures de la performance de la foldl version.

C'est aussi une affaire où l' foldl' ne va pas aider. L'ajout rigueur d' foldl' ne change pas la façon dont l'intermédiaire est créé. La tête de la liste reste disponible jusqu'à foldl' est fini, alors le résultat sera toujours plus lent qu'avec foldr.

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

• Pour les plis qui sont une réduction, utilisez foldl' (par exemple, ce sera le seul/finale de la traversée)
• Sinon, utilisez foldr.
• Ne pas utiliser foldl.

Dans la plupart des cas foldr est la meilleure fonction fold parce que la traversée de la direction est optimale pour les paresseux de l'évaluation de listes. C'est aussi le seul capable de traitement de l'infini listes. Le supplément de la rigueur de l' foldl' pouvez faire plus rapide dans certains cas, mais cela dépend de comment vous allez l'utiliser que de la structure et comment paresseux qu'il est.

Answer 3

Je ne pense pas que quelqu'un l'a dit en fait la vraie réponse sur ce point encore, à moins que je suis absent quelque chose (ce qui est peut-être vrai et accueilli avec downvotes).

Je pense que la plus grande différent dans ce cas est que l' foldr construit la liste comme ceci:

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

Alors qu' foldl construit la liste comme ceci:

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

La différence subtile, mais notez que l' foldr version ++ a toujours seulement un élément de la liste comme sa gauche argument. Avec l' foldr version, il y a jusqu'à 999999 éléments en ++ gauche argument (en moyenne autour de 500000), mais qu'un seul élément dans le bon argument.

Toutefois, ++ prend du temps proportionnel à la taille de la gauche argument, car il a un look bien que l'ensemble de la gauche de la liste d'arguments de la fin et puis peretochki ce dernier élément pour le premier élément de la droite argument (au mieux, peut-être qu'il a vraiment besoin de faire une copie). Le droit de la liste d'arguments est inchangée, de sorte qu'il n'a pas d'importance comment elle est grande.

C'est pourquoi l' foldr version est beaucoup plus lent. Il n'a rien à voir avec la paresse, à mon avis.

Answer 4

Pour l'un, l' [0.. 100000] liste doit être étendu tout de suite, alors que foldr pouvez commencer avec le dernier élément. Puis, comme il se replie choses ensemble, les résultats intermédiaires sont

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

Parce que personne n'est autorisé à modifier cette valeur de la liste (Haskell est un langage purement fonctionnel), le compilateur est libre de réutiliser la valeur. Les valeurs intermédiaires, comme [99999, 100000] peut-être même tout simplement des pointeurs vers des élargi [0.. 100000] la liste au lieu de séparer les listes.

Pour b, regardez les valeurs intermédiaires:

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

Chacun de ces intermédiaires, les listes ne peuvent pas être réutilisés, parce que si vous changer la fin de la liste, alors vous avez changé toutes les autres valeurs qui pointent vers elle. Si vous êtes en train de créer un groupe supplémentaire de listes de prendre le temps de construire dans la mémoire. Dans ce cas, vous passez beaucoup plus de temps à allouer et de remplissage dans ces listes, qui sont des valeurs intermédiaires.

Puisque vous êtes juste de faire une copie de la liste, un court plus vite car il commence par étendre la liste complète, puis ne cesse de déplacer un curseur à partir de la fin de la liste à l'avant.

Answer 5

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

Mais dans votre cas à l'aide d' ++ avec foldl' n'est pas une bonne idée parce que l'évaluation successive de ++ sera la cause de la traversée de croissance de l'accumulateur, encore et encore.