foldl est récursive, alors pourquoi foldr court plus vite que foldl?

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

la différence réside dans la façon dont foldl et foldr appliquent leur fonction de réduction. En regardant le cas foldr , 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 , qui la 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 suis parti les détails de la concaténation de la liste, mais c'est la façon dont la réduction se déroule. La partie importante est que tout est traité afin de minimiser les traversées de liste. Le foldr ne traverse la liste qu'une seule fois, les concaténations ne nécessitent pas de traversée continue de la liste, et le sum consomme finalement la liste en une seule passe. De manière critique, la tête de liste est disponible de foldr immédiatement à sum , de sorte que sum peut commencer à travailler immédiatement et les valeurs peut être gc avais comme ils sont générés. Avec des cadres de fusion tels que vector , même les listes intermédiaires seront probablement fusionnées.

contraste avec 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 la tête de liste n'est pas disponible avant que foldl ne soit terminé. Cela signifie que la liste entière doit être construite en mémoire avant que sum puisse commencer à fonctionner. C'est beaucoup moins efficace dans son ensemble. L'exécution de la deux les versions avec +RTS -s montrent des performances Misérables de collecte des ordures de la version foldl.

C'est aussi un cas où foldl' n'aidera pas. La rigueur ajoutée de foldl' ne change pas la façon dont la liste intermédiaire est créée. La tête de liste reste indisponible jusqu'à ce que foldl' ait terminé, donc le résultat sera encore plus lent qu'avec foldr .

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

• pour les plis qui sont une réduction , utiliser foldl' (e.g. ce sera le seul/final traversée)
• sinon utiliser foldr .
• N'utilisez pas foldl .

dans la plupart des cas foldr est la meilleure fonction de plissement parce que la direction transversale est optimale pour l'évaluation paresseuse des listes. C'est aussi le seul capable de traitement de 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 à quel point elle est paresseuse.

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

L'optimisation de la récursion de la queue évite le besoin de mémoriser des valeurs pour chaque appel récursif.

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

C'est comme ça que l'expression "foldl (+) 0 [1,2,3]" est de l'évaluation:

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 souvient pas des valeurs 0, 1, 2..., but pass the whole expression (((0+1)+2)+3) comme argument paresse et ne l'évalue pas avant la dernière évaluation de foldl, où il atteint le cas de base et renvoie la valeur passée comme deuxième paramètre (z) qui n'est pas encore évalué.

d'un autre côté, c'est comme ça que 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 ici est que lorsque foldl évalue la totalité de l'expression dans le dernier appel, en évitant la nécessité de revenir pour atteindre les valeurs mémorisées, foldr no. foldr se souvenir d'un entier pour chaque appel et effectue une addition dans 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 hugs:

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

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

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

(désolé pour mon mauvais anglais)

Je ne pense pas que quelqu'un a vraiment dit la vraie réponse sur celui-ci encore, à moins que je manque quelque chose (qui peut bien être vrai et accueilli avec des notes négatives).

je pense que la plus grande différence 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 en subtil, mais notez que dans la foldr version ++ a toujours un seul élément de liste comme argument de gauche. Avec la version foldl , il y a jusqu'à 999999 éléments dans l'argument de gauche de ++ (en moyenne environ 500000), mais seulement un élément dans l'argument de droite.

Toutefois, ++ prend du temps proportionnel à la taille de la gauche argument, comme il l'a regarder bien que tout l'argument de gauche liste à la fin et puis repoint ce dernier élément au premier élément de l'argument de droite (au mieux, peut-être qu'il a réellement besoin de faire une copie). La bonne liste d'arguments est inchangée, donc peu importe sa taille.

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

pour a, la liste [0.. 100000] doit être étendue immédiatement afin que foldr puisse commencer avec le dernier élément. Puis, au fur et à mesure que les choses se replient, 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é à changer cette valeur de liste (Haskell est un langage purement fonctionnel), le compilateur est libre de réutiliser cette valeur. Les valeurs intermédiaires ,comme [99999, 100000] peuvent même être simplement des pointeurs dans la liste étendue [0.. 100000] 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 pas être réutilisée, parce que si vous changez la fin de la liste alors vous avez changé toutes les autres valeurs qui pointent vers elle. Donc vous créez un tas de listes supplémentaires qui prennent du temps à 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 venez de faire un copie de la liste, a court plus vite parce qu'il commence par étendre la liste complète et puis continue de déplacer un pointeur de l'arrière de la liste à l'avant.

ni foldl ni foldr ne sont optimisés en fonction de la queue. C'est seulement foldl' .

mais dans votre cas utiliser ++ avec foldl' n'est pas une bonne idée parce que l'évaluation successive de ++ causera la traversée de l'accumulateur croissant encore et encore.

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 que A. Si vous voulez être précis a a besoin d'une étape de réduction pour la valeur à calculer, mais b a besoin de deux. Cela fait la différence de temps que vous mesurez, dans le deuxième exemple deux fois plus de réductions doivent être effectuées.

//edit: Mais le temps de la complexité est la même chose, donc je ne serais pas la peine beaucoup d'attention.