Implications de foldr vs. foldl (ou foldl')

Question

Tout d'abord, Haskell dans le monde réel que je suis en train de lire, dit qu'il ne faut jamais utiliser foldl au lieu de foldl' . Je lui fais donc confiance.

Mais j'ai du mal à savoir quand utiliser foldr vs. foldl' . Bien que je puisse voir la structure de leur fonctionnement différent étalée devant moi, je suis trop stupide pour comprendre quand "lequel est le meilleur". Je suppose qu'il me semble que cela ne devrait pas vraiment avoir d'importance de savoir lequel est utilisé, puisqu'ils produisent tous les deux la même réponse (n'est-ce pas ?). En fait, ma première expérience avec cette construction provient de Ruby's inject et de Clojure reduce qui ne semblent pas avoir de versions "gauche" et "droite". (Question secondaire : quelle version utilisent-ils ?)

Toute information susceptible d'aider une personne aussi peu intelligente que moi serait très appréciée.

Answer 1

La récursion pour foldr f x ys donde ys = [y1,y2,...,yk] ressemble à

f y1 (f y2 (... (f yk x) ...))

alors que la récursion pour foldl f x ys ressemble à

f (... (f (f x y1) y2) ...) yk

Une différence importante ici est que si la valeur de f x y peut être calculée en utilisant uniquement la valeur de x entonces foldr n'a pas besoin d'examiner toute la liste. Par exemple

foldr (&&) False (repeat False)

renvoie à False alors que

foldl (&&) False (repeat False)

ne se termine jamais. (Note : repeat False est une liste infinie où chaque élément est False .)

D'un autre côté, foldl' est récursif et strict. Si vous savez que vous devrez parcourir la liste entière quoi qu'il arrive (par exemple, pour additionner les nombres dans une liste), alors foldl' est plus efficace en terme d'espace (et probablement de temps) que foldr .

Answer 2

foldr ressemble à ça :

foldl ressemble à ça :

Le contexte : Pliage sur le wiki Haskell

Answer 3

Leur sémantique est différente, vous ne pouvez donc pas simplement interchanger foldl y foldr . L'un plie les éléments en partant de la gauche, l'autre de la droite. Ainsi, l'opérateur est appliqué dans un ordre différent. Ceci est important pour toutes les opérations non-commuatives, comme la soustraction.

Haskell.org a une intéressante article sur le sujet.

Answer 4

Brièvement, foldr est meilleur lorsque la fonction accumulatrice est paresseuse sur son deuxième argument. Pour en savoir plus, consultez http://www.haskell.org/haskellwiki/Stack_overflow (jeu de mots).

Answer 5

La raison foldl' est préféré à foldl pour 99% de toutes les utilisations est qu'il peut fonctionner en espace constant pour la plupart des utilisations.

Prenez la fonction sum = foldl['] (+) 0 . Quand foldl' est utilisé, la somme est immédiatement calculée, de sorte que l'application de l'option sum à une liste infinie sera exécuté à l'infini, et très probablement dans un espace constant (si vous utilisez des choses comme Int s, Double s, Float s. Integer utilisera un espace plus que constant si le nombre devient plus grand que maxBound :: Int ).

Avec foldl un thunk est construit (comme une recette pour obtenir la réponse, qui peut être évaluée plus tard, plutôt que de stocker la réponse). Ces thunks peuvent prendre beaucoup de place, et dans ce cas, il est préférable d'évaluer l'expression plutôt que de stocker le thunk (ce qui entraînerait un débordement de la pile et vous conduirait à oh, laissez tomber).

J'espère que cela vous aidera.