Comment savoir quand utiliser fold-left et quand utiliser fold-right?

Question

Je suis conscient du fait que le repli gauche produit des arbres de gauche et le repli de droite, des arbres inclinés de droite, mais lorsque j'atteins un pli, je me trouve parfois embourbé dans une pensée qui provoque des maux de tête et tente de déterminer lequel type de pli est approprié. Je finis généralement par résoudre le problème dans son intégralité et à travers la mise en œuvre de la fonction de pliage telle qu'elle s'applique à mon problème.

Ce que je veux savoir, c'est:

• Quelles sont les règles à suivre pour déterminer s'il faut plier à gauche ou à droite?
• Comment déterminer rapidement le type de pli à utiliser en fonction du problème auquel je suis confronté?

Il existe un exemple dans Analyse par exemple (PDF) de utiliser 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, un bon pli est le bon choix (compte tenu de la façon dont les listes sont concaténées), mais je devais y réfléchir un peu pour arriver à cette conclusion.

Le pliage étant une action tellement courante dans la programmation (fonctionnelle), j'aimerais pouvoir prendre ce genre de décisions rapidement et en toute confiance. Alors ... des conseils?

Answer 1

Vous pouvez transférer un pli dans une notation d'opérateur infixe (écriture intermédiaire):

Cet exemple de pliage utilisant la fonction d'accumulateur x

fold x [A, B, C, D]

est donc égal à

A x B x C x D

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

Si vous disposez d'un opérateur associatif à gauche , vous définissez les parenthèses comme suit

((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 à droite ( repli à droite ), les parenthèses sont 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 + parenthèses est très utile.

Answer 2

Olin Shivers les a différenciés en disant que " foldl est l'itérateur de liste fondamental " et "foldr est l'opérateur de récursion de liste fondamental." Si vous regardez le fonctionnement de foldl:

((1 + 2) + 3) + 4

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

1 + (2 + (3 + 4))

où vous pouvez voir le parcours jusqu'au cas de base 4 et construire le résultat à partir de là.

Je pose donc une règle de base: si cela ressemble à une itération de liste, une écriture qui serait simple à écrire en forme de queue-récursive, foldl est le chemin à parcourir.

Mais en réalité, ce sera probablement plus évident grâce à l’associativité des opérateurs que vous utilisez. S'ils sont à gauche associative, utilisez foldl. S'ils sont à droite associative, utilisez foldr.

Answer 3

D'autres affiches ont donné de bonnes réponses et je ne répéterai pas ce qu'ils ont déjà dit. Comme vous avez donné un exemple Scala dans votre question, je vais donner un exemple spécifique à Scala. Comme Astuces a déjà été dit, un foldRight doit préserver n-1 cadres de pile, où n est la longueur de votre liste, ce qui peut facilement entraîner un débordement de pile - et même la récursion par la queue ne pourrait vous en épargner.

Une liste (1,2,3) .foldRight (0) (_ + _) serait réduite à:

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)

tandis que la liste (1,2,3) .foldLeft (0) (_ + _) se réduirait à:

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

qui peut être calculé de manière itérative, comme dans implémentation de List .

Dans un langage strictement évalué comme Scala, un foldRight peut facilement faire exploser la pile pour les grandes listes, alors qu'un foldLeft ne le pourra 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 - pour les opérateurs n'ayant pas d'associativité spécifique, utilisez toujours foldLeft , du moins dans Scala. Sinon, suivez les autres conseils donnés dans les réponses;).

Answer 4

Il convient également de noter (et je me rends bien 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 foldl pourrait être le meilleur choix:

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

foldr: (1 + (2 + (3 + 4))) nécessite l’ouverture d’un cadre de pile pour 1 +? et 2 +? avant en calculant 3 + 4 , il doit ensuite revenir en arrière et faire le calcul pour chacun.

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