foldl est la queue récursive, alors pourquoi se plier plus vite que foldl?

Je voulais tester foldl vs foldr. D’après ce que j’ai vu, vous devriez utiliser foldl over foldr quand vous le pouvez grâce à l’optimisation de la rechute de queue.

C’est logique. Cependant, après avoir effectué ce test, je suis confus:

foldr (prend 0,057 s en utilisant la commande time):

a::a -> [a] -> [a] ax = ([x] ++ ) main = putStrLn(show ( sum (foldr a [] [0.. 100000]))) 

foldl (prend 0.089s en utilisant la commande time):

 b::[b] -> b -> [b] b xs = ( ++ xs). (\y->[y]) main = putStrLn(show ( sum (foldl b [] [0.. 100000]))) 

Il est clair que cet exemple est sortingvial, mais je ne comprends pas pourquoi foldr bat son plein. Ne devrait-il pas s’agir d’un cas clair où foldl gagne?

Bienvenue dans le monde de l’évaluation paresseuse.

Quand on y pense en termes d’évaluation ssortingcte, foldl a l’air “bon” et foldr a l’air “mauvais” car foldl est la queue récursive, mais foldr devrait construire une tour dans la stack pour traiter le dernier élément en premier.

Cependant, l’évaluation paresseuse tourne les tables. Prenez, par exemple, la définition de la fonction de carte:

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

Ce ne serait pas bien si Haskell utilisait une évaluation ssortingcte, car il faudrait d’abord calculer la queue, puis append l’élément (pour tous les éléments de la liste). La seule façon de le faire efficacement serait de construire les éléments en sens inverse, semble-t-il.

Cependant, grâce à l’évaluation paresseuse d’Haskell, cette fonction de carte est effectivement efficace. Les listes dans Haskell peuvent être considérées comme des générateurs, et cette fonction de carte génère son premier élément 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 juste la même chose (sans utiliser d’espace supplémentaire).

Il s’avère que la map peut être décrite en termes de foldr :

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

C’est difficile à dire en le regardant, mais l’évaluation paresseuse intervient parce que foldr peut donner son premier argument tout de suite:

 foldr fz [] = z foldr fz (x:xs) = fx (foldr fz 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 paresseusement dans un espace constant.

Maintenant, l’évaluation paresseuse ne ronge pas. Par exemple, essayez d’exécuter sum [1..1000000]. Cela donne un débordement de stack. Pourquoi devrait-il? Il devrait juste évaluer de gauche à droite, non?

Regardons comment Haskell l’évalue:

 foldl fz [] = z foldl fz (x:xs) = foldl f (fzx) 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 au fur et à mesure. Au lieu de cela, il se retrouve avec une tour de thunks non évalués qu’il faut forcer pour obtenir un numéro. Le débordement de stack se produit pendant cette évaluation, car il doit se déclencher profondément pour évaluer tous les thunks.

Heureusement, il existe une fonction spéciale dans Data.List appelée foldl' qui fonctionne ssortingctement. foldl' (+) 0 [1..1000000] pas le débordement. (Remarque: j’ai essayé de remplacer foldl par foldl' dans votre test, mais cela l’a rendu plus lent.)

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

La différence réside dans la manière dont les foldl et les foldr appliquent leur fonction de réduction. En regardant le cas de foldr , nous pouvons le développer 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 consum 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]) ... 

J’ai omis les détails de la concaténation des listes, mais c’est ainsi que se déroule la réduction. L’important est que tout soit traité afin de minimiser les parcours de liste. Le foldr ne parcourt la liste qu’une seule fois, les concaténations ne nécessitent pas de parcours de liste continus et sum consum finalement la liste en un seul passage. De manière critique, la tête de la liste est immédiatement disponible à partir de foldr , donc la sum peut commencer à fonctionner immédiatement et les valeurs peuvent être générées au fur et à mesure qu’elles sont générées. Avec les frameworks de fusion tels que vector , même les listes intermédiaires seront probablement fusionnées.

Contrastez ceci 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 la liste n’est pas disponible jusqu’à foldl que foldl soit terminé. Cela signifie que la liste entière doit être construite en mémoire avant que la sum puisse commencer à fonctionner. C’est beaucoup moins efficace dans l’ensemble. L’exécution des deux versions avec +RTS -s montre des performances de récupération de place de la version foldl.

C’est aussi un cas où foldl' ne va pas aider. La rigueur ajoutée de foldl' ne change pas la façon dont la liste intermédiaire est créée. La tête de la liste rest indisponible jusqu’à ce que foldl ‘soit terminé, donc 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 une réduction , utilisez foldl' (par exemple, ce sera la seule traversée / finale)
  • Sinon, utilisez foldr .
  • Ne pas utiliser foldl .

Dans la plupart des cas, foldr est la meilleure fonction de pliage car la direction de traversée est optimale pour une évaluation différée des listes. C’est aussi le seul capable de traiter des listes infinies. La rigidité supplémentaire de foldl' peut le rendre plus rapide dans certains cas, mais cela dépend de la manière dont vous utiliserez cette structure et de son caractère paresseux.

Je ne pense pas que quiconque ait réellement répondu à la question, à moins que je ne manque quelque chose (ce qui pourrait bien être vrai et bien accueilli avec des votes faibles).

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 de subtilité, mais notez que dans la version foldr , ++ 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 autour de 500000), mais un seul élément dans le bon argument.

Cependant, ++ prend du temps proportionnel à la taille de l’argument de gauche, car il doit examiner la liste d’arguments de gauche jusqu’à la fin, puis joindre ce dernier élément au premier élément de l’argument de droite (au mieux, peut-être a besoin de faire une copie). La bonne liste d’arguments est inchangée, peu importe sa taille.

C’est pourquoi la version foldl est beaucoup plus lente. Cela n’a rien à voir avec la paresse à mon avis.

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 d’avoir à mémoriser des valeurs pour chaque appel récursif.

Donc, foldl est en fait “bon” et foldr est “mauvais”.

Par exemple, en considérant les définitions de foldr et foldl:

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

C’est comme ça que 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 souvient pas des valeurs 0, 1, 2 …, mais passe l’expression entière (((0 + 1) +2) +3) en argument 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 en tant que second paramètre (z) qui n’est pas encore évalué.

D’un autre côté, c’est comme ça que ça fonctionne:

 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 l’expression entière dans le dernier appel, évitant le besoin de revenir pour atteindre des valeurs mémorisées, foldr no. foldr mémorise un entier pour chaque appel et effectue un ajout à chaque appel.

Il est important de garder à l’esprit que foldr et foldl ne sont pas toujours des équivalents. Par exemple, essayez de calculer ces expressions dans les 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)

Pour un, la liste [0.. 100000] doit être étendue immédiatement afin que foldr puisse commencer par le dernier élément. Alors, comme il plie les choses ensemble, les résultats intermédiaires sont

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

Étant donné que personne n’est autorisé à modifier cette valeur de liste (Haskell est un langage purement fonctionnel), 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 [0.. 100000] étendue 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, car si vous modifiez la fin de la liste, vous avez modifié toutes les autres valeurs qui lui sont associées. 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 à atsortingbuer et à remplir ces listes qui sont des valeurs intermédiaires.

Etant donné que vous ne faites qu’une copie de la liste, un fichier s’exécute plus rapidement car il commence par agrandir la liste complète et continue de déplacer un pointeur de l’arrière de la liste vers l’avant.

Ni foldl ni foldr sont optimisés en queue. C’est seulement foldl' .

Mais dans votre cas, utiliser ++ avec foldl' n’est pas une bonne idée, car l’évaluation successive de ++ provoquera la traversée de plus en plus de l’accumulateur.

Eh bien, laissez-moi réécrire vos fonctions de manière à ce que la différence soit é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 étape de réduction est nécessaire pour que la valeur soit calculée, mais b nécessite 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 la complexité du temps est la même, alors je ne m’en soucierais pas beaucoup.