Implications de foldr vs foldl (ou foldl ')

155

Premièrement, Real World Haskell , que je lis, dit de ne jamais utiliser foldlet d'utiliser à la place foldl'. Alors je lui fais confiance.

Mais je suis brumeux quand utiliser foldrcontre foldl'. Bien que je puisse voir la structure de leur fonctionnement différemment présentée devant moi, je suis trop stupide pour comprendre quand «ce qui est mieux». Je suppose qu'il me semble que peu importe ce qui est utilisé, car ils produisent tous les deux la même réponse (n'est-ce pas?). En fait, mon expérience précédente avec cette construction vient de Ruby injectet Clojure reduce, qui ne semblent pas avoir de versions «gauche» et «droite». (Question secondaire: quelle version utilisent-ils?)

Toute perspicacité qui peut aider une sorte intelligente comme moi serait très appréciée!

J Cooper
la source

Réponses:

174

La récursivité pour foldr f x ysys = [y1,y2,...,yk]ressemble

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

alors que la récursivité pour foldl f x ysressemble à

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

Une différence importante ici est que si le résultat de f x ypeut être calculé en utilisant uniquement la valeur de x, il foldrn'est pas nécessaire d'examiner la liste entière. Par exemple

foldr (&&) False (repeat False)

retourne Falsealors que

foldl (&&) False (repeat False)

ne se termine jamais. (Remarque: repeat Falsecrée une liste infinie où se trouve chaque élément False.)

D'autre part, la foldl'queue est récursive et stricte. Si vous savez que vous devrez parcourir toute la liste quoi qu'il arrive (par exemple, additionner les nombres dans une liste), alors foldl'est plus efficace en termes d'espace (et probablement de temps) que foldr.

Chris Conway
la source
2
Dans foldr, il est évalué comme f y1 thunk, donc il retourne False, cependant dans foldl, f ne peut pas connaître l'un ou l'autre de ses paramètres.Dans Haskell, peu importe qu'il s'agisse d'une récursivité de queue ou non, les deux peuvent provoquer un débordement de thunks, c'est-à-dire que le thunk est trop grand. foldl 'peut réduire le thunk immédiatement le long de l'exécution.
Sawyer
25
Pour éviter toute confusion, notez que les parenthèses n'indiquent pas l'ordre réel d'évaluation. Comme Haskell est paresseux, les expressions les plus externes seront évaluées en premier.
Lii
Bonne réponse. Je voudrais ajouter que si vous voulez un pli qui peut s'arrêter à mi-chemin dans une liste, vous devez utiliser foldr; sauf erreur de ma part, les plis à gauche ne peuvent pas être arrêtés. (Vous faites allusion à cela lorsque vous dites "si vous savez ... vous allez ... parcourir toute la liste"). De plus, la faute de frappe «n'utiliser que sur la valeur» doit être remplacée par «n'utiliser que la valeur». Ie supprimer le mot "on". (Stackoverflow ne me laisserait pas soumettre un changement de 2 caractères!).
Lqueryvg
@Lqueryvg deux façons d'arrêter les plis à gauche: 1. codez-le avec un pli à droite (voir fodlWhile); 2. convertissez-le en un scan gauche ( scanl) et arrêtez-le avec last . takeWhile pou similaire. Euh, et 3. utiliser mapAccumL. :)
Will Ness
1
@Desty car il produit une nouvelle partie de son résultat global à chaque étape - contrairement à foldl, qui collecte son résultat global et ne le produit qu'une fois que tout le travail est terminé et qu'il n'y a plus d'étapes à effectuer. Donc par exemple foldl (flip (:)) [] [1..3] == [3,2,1], donc scanl (flip(:)) [] [1..] = [[],[1],[2,1],[3,2,1],...]... IOW, foldl f z xs = last (scanl f z xs)et les listes infinies n'ont pas de dernier élément (qui, dans l'exemple ci-dessus, serait elle-même une liste infinie, de INF à 1).
Will Ness
57

foldr ressemble à ça:

Visualisation à droite

foldl ressemble à ça:

Visualisation à gauche

Contexte: plier sur le wiki Haskell

Greg Bacon
la source
33

Leur sémantique diffère donc vous ne pouvez pas simplement échanger foldlet foldr. L'un replie les éléments par la gauche, l'autre par la droite. De cette façon, l'opérateur est appliqué dans un ordre différent. Ceci est important pour toutes les opérations non associatives, telles que la soustraction.

Haskell.org a un article intéressant sur le sujet.

Konrad Rudolph
la source
Leur sémantique ne diffère que de manière triviale, qui n'a pas de sens en pratique: l'ordre des arguments de la fonction utilisée. Donc, au niveau de l'interface, ils comptent toujours comme échangeables. La vraie différence n'est, semble-t-il, que l'optimisation / mise en œuvre.
Evi1M4chine
2
@ Evi1M4chine Aucune des différences n'est triviale. Au contraire, ils sont substantiels (et, oui, significatifs dans la pratique). En fait, si je devais écrire cette réponse aujourd'hui, cela accentuerait encore plus cette différence.
Konrad Rudolph
23

En bref, foldrc'est mieux lorsque la fonction d'accumulateur est paresseuse sur son deuxième argument. Pour en savoir plus, consultez Stack Overflow de Haskell wiki (jeu de mots).

mattiast
la source
18

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

Prenez la fonction sum = foldl['] (+) 0. Quand foldl'est utilisé, la somme est immédiatement calculée, donc l'application sumà une liste infinie ne fonctionnera que pour toujours, et très probablement dans un espace constant (si vous utilisez des choses comme Ints, Doubles, Floats. IntegerS utilisera plus qu'un espace constant si le nombre devient supérieur à maxBound :: Int).

Avec foldl, un bruit sourd est construit (comme une recette sur la façon d'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 vaut mieux évaluer l'expression que de stocker le thunk (conduisant à un débordement de pile… et vous conduisant à… oh tant pis)

J'espère que cela pourra aider.

Axman6
la source
1
La grande exception est si la fonction passée à foldlne fait rien d'autre qu'appliquer des constructeurs à un ou plusieurs de ses arguments.
dfeuer
Existe-t-il un schéma général pour déterminer quand foldlest réellement le meilleur choix? (Comme les listes infinies, quand foldrest le mauvais choix, en
termes d'
@ Evi1M4chine ne sais pas ce que vous entendez en foldrétant le mauvais choix pour des listes infinies. En fait, vous ne devriez pas utiliser foldlou foldl'pour des listes infinies. Voir le wiki Haskell sur les débordements de pile
KevinOrr le
14

À propos, Ruby injectet Clojure reducesont foldl(ou foldl1, selon la version que vous utilisez). Habituellement, quand il n'y a qu'une seule forme dans un langage, c'est un pli gauche, y compris celui de Python reduce, Perl List::Util::reduce, C ++ accumulate, C # Aggregate, Smalltalk inject:into:, PHP array_reduce, Mathematica Fold, etc. Common Lisp est par reducedéfaut le pli gauche mais il y a une option pour le pli droit.

newacct
la source
2
Ce commentaire est utile mais j'apprécierais les sources.
titaniumdecoy
Common Lisp reducen'est pas paresseux, donc c'est foldl'et la plupart des considérations ici ne s'appliquent pas.
MicroVirus
Je pense que vous voulez dire foldl', car ce sont des langues strictes, non? Sinon, cela ne signifie-t-il pas que toutes ces versions provoquent des débordements de pile comme le foldlfait?
Evi1M4chine
6

Comme le souligne Konrad , leur sémantique est différente. Ils n'ont même pas le même type:

ghci> :t foldr
foldr :: (a -> b -> b) -> b -> [a] -> b
ghci> :t foldl
foldl :: (a -> b -> a) -> a -> [b] -> a
ghci> 

Par exemple, l'opérateur d'ajout de liste (++) peut être implémenté avec foldras

(++) = flip (foldr (:))

tandis que

(++) = flip (foldl (:))

vous donnera une erreur de type.

Jonas
la source
Leur type est le même, juste inversé, ce qui n'est pas pertinent. Leur interface et leurs résultats sont les mêmes, sauf pour le vilain problème P / NP (lire: listes infinies). ;) L'optimisation due à l'implémentation est la seule différence en pratique, pour autant que je sache.
Evi1M4chine
@ Evi1M4chine Ceci est incorrect, regardez cet exemple: foldl subtract 0 [1, 2, 3, 4]évalue à -10, tandis que foldr subtract 0 [1, 2, 3, 4]évalue à -2. foldlest en fait 0 - 1 - 2 - 3 - 4pendant que foldrest 4 - 3 - 2 - 1 - 0.
krapht
@krapht, foldr (-) 0 [1, 2, 3, 4]est -2et foldl (-) 0 [1, 2, 3, 4]est -10. D'autre part, subtractest à l'envers de ce à quoi vous pourriez vous attendre ( subtract 10 14est 4), foldr subtract 0 [1, 2, 3, 4]est donc -10et foldl subtract 0 [1, 2, 3, 4]est 2(positif).
pianoJames