Comment savez-vous quand utiliser fold-left et quand utiliser fold-right?

Je suis conscient que le pli gauche produit des arbres orientés vers la gauche et que le pli droit produit des arbres inclinés vers la droite, mais lorsque j’atteins un pli, je me trouve parfois enlisé dans une pensée qui induit des maux de tête. est approprié. Je finis généralement par résoudre tout le problème et passer en revue l’implémentation de la fonction de pliage telle qu’elle s’applique à mon problème.

Donc, ce que je veux savoir, c’est:

  • Quelles sont les règles de base pour déterminer s’il faut plier à gauche ou à droite?
  • Comment puis-je rapidement décider quel type de pli utiliser en fonction du problème auquel je suis confronté?

Il y a un exemple dans Scala by Example (PDF) d’utilisation d’un pli pour écrire une fonction appelée flatten qui concatène une liste de listes d’éléments en une seule liste. Dans ce cas, le bon choix est le bon choix (compte tenu de la manière dont les listes sont concaténées), mais je devais y réfléchir un peu pour arriver à cette conclusion.

Étant donné que le pliage est une action si commune dans la programmation (fonctionnelle), j’aimerais pouvoir prendre ce genre de décisions rapidement et en toute confiance. Alors … des conseils?

Vous pouvez transférer un pli dans une notation opérateur infixe (en écrivant entre):

Cet exemple se plie en utilisant la fonction accumulateur x

 fold x [A, B, C, D] 

donc égale

 A x B x C x D 

Il ne vous rest plus qu’à raisonner sur l’associativité de votre opérateur (en mettant des parenthèses!).

Si vous avez un opérateur associatif de gauche , vous allez définir les parenthèses comme ceci

 ((A x B) x C) x D 

Ici, vous utilisez un pli gauche . Exemple (pseudocode de style haskell)

 foldl (-) [1, 2, 3] == (1 - 2) - 3 == 1 - 2 - 3 // - is left-associative 

Si votre opérateur est associatif à droitedroite ), les parenthèses seront définies comme suit:

 A x (B x (C x D)) 

Exemple: Cons-Operator

 foldr (:) [] [1, 2, 3] == 1 : (2 : (3 : [])) == 1 : 2 : 3 : [] == [1, 2, 3] 

En général, les opérateurs arithmétiques (la plupart des opérateurs) sont associatifs à gauche, de sorte que foldl est plus répandu. Mais dans les autres cas, la notation infixe + les parenthèses est très utile.

Olin Shivers les a différenciés en disant “foldl est l’iterator de liste fondamental” et “foldr est l’opérateur de récurrence de liste fondamentale”. Si vous regardez comment ça marche:

 ((1 + 2) + 3) + 4 

vous pouvez voir l’accumulateur (comme dans une itération récursive) en cours de construction. En revanche, foldr procède:

 1 + (2 + (3 + 4)) 

où vous pouvez voir la traversée vers le cas de base 4 et construire le résultat à partir de là.

Donc, je pose une règle de base: si cela ressemble à une itération de liste, qui serait simple à écrire sous une forme récursive, foldl est la voie à suivre.

Mais en réalité, l’associativité des opérateurs que vous utilisez sera la plus évidente. S’ils sont associatifs, utilisez foldl. S’ils sont associatifs, utilisez foldr.

D’autres affiches ont donné de bonnes réponses et je ne répéterai pas ce qu’elles ont déjà dit. Comme vous avez donné un exemple Scala dans votre question, je vais donner un exemple spécifique Scala. Comme Tricks a déjà dit, un foldRight doit conserver n-1 frames de stack, où n est la longueur de votre liste et cela peut facilement conduire à un débordement de stack – et même la récursion de queue ne vous en sauvera pas.

Une List(1,2,3).foldRight(0)(_ + _) se réduirait à:

 1 + List(2,3).foldRight(0)(_ + _) // first stack frame 2 + List(3).foldRight(0)(_ + _) // second stack frame 3 + 0 // third stack frame // (I don't remember if the JVM allocates space // on the stack for the third frame as well) 

while List(1,2,3).foldLeft(0)(_ + _) réduirait à:

 (((0 + 1) + 2) + 3) 

qui peut être calculé de manière itérative, comme cela est fait dans la mise en œuvre de List .

Dans un langage ssortingctement évalué comme Scala, un foldRight peut facilement faire exploser la stack pour les grandes listes, alors qu’un foldLeft ne le fera pas.

Exemple:

 scala> List.range(1, 10000).foldLeft(0)(_ + _) res1: Int = 49995000 scala> List.range(1, 10000).foldRight(0)(_ + _) java.lang.StackOverflowError at scala.List.foldRight(List.scala:1081) at scala.List.foldRight(List.scala:1081) at scala.List.foldRight(List.scala:1081) at scala.List.foldRight(List.scala:1081) at scala.List.foldRight(List.scala:1081) at scala.List.foldRight(List.scala:1081) at scala.List.foldRight(List.scala:1081) at scala.List.foldRight(List.scala:1081) at scala.List.foldRig... 

Ma règle générale est donc la suivante: pour les opérateurs qui n’ont pas d’associativité spécifique, utilisez toujours foldLeft , au moins dans Scala. Sinon, suivez les autres conseils donnés dans les réponses;).

Cela vaut également la peine de le noter (et je me rends compte que c’est un peu évident), dans le cas d’un opérateur commutatif, les deux sont à peu près équivalents. Dans cette situation, un pli pourrait être le meilleur choix:

foldl: (((1 + 2) + 3) + 4) peut calculer chaque opération et transmettre la valeur accumulée en avant

foldr: (1 + (2 + (3 + 4))) besoin d’un cadre de stack pour être ouvert pour 1 + ? et 2 + ? avant de calculer 3 + 4 , il faut revenir en arrière et faire le calcul pour chacun.

Je ne suis pas un expert des langages fonctionnels ou des optimisations de compilateur pour dire si cela va réellement faire la différence, mais il semble certainement plus propre d’utiliser un foldl avec des opérateurs commutatifs.