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

Question

Je suis conscient que le pli gauche produit gauchisants des arbres et des plier à droite produit droite arbres, mais quand j'arrive pour une fois, je me trouve parfois s'enliser dans des maux de tête induisant la pensée d'essayer de déterminer le type de pli est approprié. Je finissent généralement déroulement de l'ensemble du problème et de marcher à travers la mise en œuvre de la fonction fold car il s'applique à mon problème.

Donc ce que je veux savoir, c'est:

• Quelles sont les règles du pouce pour déterminer si à la fois de gauche ou de plier la droite?
• Comment puis-je déterminer rapidement le type de pli à utiliser compte tenu du problème que je me pose?

Il y a un exemple dans la Scala par Exemple (PDF) de l'utilisation d'un pli à l'écriture d'une fonction appelée aplatir qui concatène une liste d'élément listes en une seule liste. Dans ce cas, un droit de pli est le bon choix (étant donné la manière dont les listes sont concaténés), mais j'ai dû réfléchir un peu pour arriver à cette conclusion.

Depuis pliage est une action commune dans (fonctionnelle) de la programmation, je voudrais être en mesure de prendre ce genre de décisions rapidement et en toute confiance. Alors... des conseils?

Answer 1

Vous pouvez transférer un pli dans un opérateur infixe notation (écriture):

Cet exemple de pli à l'aide de la fonction somme x

fold x [A, B, C, D]

donc est égal à

A x B x C x D

Maintenant, vous avez juste à raison à propos de l'associativité de l'opérateur de votre réseau (en mettant des parenthèses!).

Si vous avez des associatifs gauche de l'opérateur, vous serez mis les parenthèses comme ceci

((A x B) x C) x D

Ici, vous utilisez gauche pli. Exemple (haskell-style pseudo-code)

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

Si votre opérateur est en droit associatif (droit pli), les parenthèses serait définie comme ceci:

A x (B x (C x D))

Exemple: Cons-Opérateur

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, alors foldl est la plus répandue. Mais dans les autres cas, la notation infixe + parenthèses est tout à fait utile.

Answer 2

Olin Frissons différenciées en disant: "foldl est la liste fondamentale itérateur" et "foldr est la liste fondamentale de la récursivité de l'opérateur." Si vous regardez comment foldl œuvres:

((1 + 2) + 3) + 4

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

1 + (2 + (3 + 4))

où vous pouvez voir le parcours de la base de cas 4 et la construction de la suite à partir de là.

Donc je pose une règle de base: si ça ressemble à une liste d'itération, ce qui serait simple à écrire en queue-de-forme récursive, foldl est le chemin à parcourir.

Mais vraiment, ce sera probablement le plus évident de l'associativité des opérateurs que vous utilisez. Si ils sont associatifs gauche, utilisez foldl. S'ils sont de droite associatif, l'utilisation foldr.

Answer 3

D'autres affiches ont donné les bonnes réponses, et je ne vais pas répéter ce qu'ils ont déjà dit. Comme vous l'avez donné un Scala exemple dans votre question, je vais vous donner un Scala exemple précis. Que des Trucs déjà dit, un foldRight des besoins pour préserver n-1 pile d'images, où l' n est la longueur de votre liste, et cela peut facilement conduire à un débordement de pile - et même pas la queue de la récursivité pourrait vous sauver de cette.

Un List(1,2,3).foldRight(0)(_ + _) permettrait de réduire à:

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)

alors qu' List(1,2,3).foldLeft(0)(_ + _) permettrait de réduire à:

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

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

Dans un strictement évalués langue comme Scala, foldRight pouvez facilement sauter la pile en place pour les grandes listes, tandis qu'un foldLeft ne sera 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 d'or est donc - pour les opérateurs qui n'ont pas spécifique de l'associativité, toujours utiliser foldLeft, au moins en Scala. Sinon, rendez-vous avec les autres conseils donnés dans les réponses ;).