Quand dois - je utiliser reduceLeft, reduceRight, foldLeft, foldRight, scanLeftou scanRight?

Je veux une intuition / un aperçu de leurs différences - éventuellement avec quelques exemples simples.

En général, les 6 fonctions fold appliquent un opérateur binaire à chaque élément d'une collection. Le résultat de chaque étape est passé à l'étape suivante (comme entrée de l'un des deux arguments de l'opérateur binaire). De cette façon, nous pouvons cumuler un résultat.

reduceLeftet reduceRightcumulez un seul résultat.

foldLeftet foldRightcumulez un seul résultat en utilisant une valeur de départ.

scanLeftet scanRightcumulez une collection de résultats cumulatifs intermédiaires en utilisant une valeur de départ.

Accumuler

De GAUCHE et vers l'avant ...

Avec une collection d'éléments abcet un opérateur binaire, addnous pouvons explorer ce que font les différentes fonctions de repli lors du passage de l'élément LEFT de la collection (de A à C):

val abc = List("A", "B", "C")

def add(res: String, x: String) = { 
  println(s"op: $res + $x = ${res + x}")
  res + x
}

abc.reduceLeft(add)
// op: A + B = AB
// op: AB + C = ABC    // accumulates value AB in *first* operator arg `res`
// res: String = ABC

abc.foldLeft("z")(add) // with start value "z"
// op: z + A = zA      // initial extra operation
// op: zA + B = zAB
// op: zAB + C = zABC
// res: String = zABC

abc.scanLeft("z")(add)
// op: z + A = zA      // same operations as foldLeft above...
// op: zA + B = zAB
// op: zAB + C = zABC
// res: List[String] = List(z, zA, zAB, zABC) // maps intermediate results

De DROITE et en arrière ...

Si nous commençons par l'élément RIGHT et revenons en arrière (de C à A), nous remarquerons que maintenant le deuxième argument de notre opérateur binaire accumule le résultat (l'opérateur est le même, nous avons simplement changé les noms des arguments pour clarifier leurs rôles ):

def add(x: String, res: String) = {
  println(s"op: $x + $res = ${x + res}")
  x + res
}

abc.reduceRight(add)
// op: B + C = BC
// op: A + BC = ABC  // accumulates value BC in *second* operator arg `res`
// res: String = ABC

abc.foldRight("z")(add)
// op: C + z = Cz
// op: B + Cz = BCz
// op: A + BCz = ABCz
// res: String = ABCz

abc.scanRight("z")(add)
// op: C + z = Cz
// op: B + Cz = BCz
// op: A + BCz = ABCz
// res: List[String] = List(ABCz, BCz, Cz, z)

.

De-cumuler

De GAUCHE et vers l'avant ...

Si à la place nous devions décumuler un résultat par soustraction à partir de l'élément LEFT d'une collection, nous cumulions le résultat via le premier argument resde notre opérateur binaire minus:

val xs = List(1, 2, 3, 4)

def minus(res: Int, x: Int) = {
  println(s"op: $res - $x = ${res - x}")
  res - x
}

xs.reduceLeft(minus)
// op: 1 - 2 = -1
// op: -1 - 3 = -4  // de-cumulates value -1 in *first* operator arg `res`
// op: -4 - 4 = -8
// res: Int = -8

xs.foldLeft(0)(minus)
// op: 0 - 1 = -1
// op: -1 - 2 = -3
// op: -3 - 3 = -6
// op: -6 - 4 = -10
// res: Int = -10

xs.scanLeft(0)(minus)
// op: 0 - 1 = -1
// op: -1 - 2 = -3
// op: -3 - 3 = -6
// op: -6 - 4 = -10
// res: List[Int] = List(0, -1, -3, -6, -10)

De DROITE et en arrière ...

Mais recherchez les variations xRight maintenant! Rappelez-vous que la valeur (dé-) cumulée dans les variations xRight est passée au deuxième paramètre resde notre opérateur binaire minus:

def minus(x: Int, res: Int) = {
  println(s"op: $x - $res = ${x - res}")
  x - res
}

xs.reduceRight(minus)
// op: 3 - 4 = -1
// op: 2 - -1 = 3  // de-cumulates value -1 in *second* operator arg `res`
// op: 1 - 3 = -2
// res: Int = -2

xs.foldRight(0)(minus)
// op: 4 - 0 = 4
// op: 3 - 4 = -1
// op: 2 - -1 = 3
// op: 1 - 3 = -2
// res: Int = -2

xs.scanRight(0)(minus)
// op: 4 - 0 = 4
// op: 3 - 4 = -1
// op: 2 - -1 = 3
// op: 1 - 3 = -2
// res: List[Int] = List(-2, 3, -1, 4, 0) 

La dernière liste (-2, 3, -1, 4, 0) n'est peut-être pas ce à quoi vous vous attendriez intuitivement!

Comme vous le voyez, vous pouvez vérifier ce que fait votre foldX en exécutant simplement un scanX à la place et déboguer le résultat cumulé à chaque étape.

En bout de ligne

• Cumulez un résultat avec reduceLeftou reduceRight.
• Cumulez un résultat avec foldLeftou foldRightsi vous avez une valeur de départ.

• Cumulez une collection de résultats intermédiaires avec scanLeftou scanRight.

• Utilisez une variation Xgauche si vous voulez aller en avant dans la collection.

• Utilisez une variante xRight si vous souhaitez revenir en arrière dans la collection.

Normalement, la méthode REDUCE, FOLD, SCAN fonctionne en accumulant des données sur LEFT et continuez à changer la variable RIGHT. La principale différence entre eux est REDUCE, FOLD est: -

Le pliage commencera toujours par une seedvaleur, c'est-à-dire la valeur de départ définie par l'utilisateur. Réduire lèvera une exception si la collection est vide où as fold rendra la valeur de départ. Il en résultera toujours une valeur unique.

La numérisation est utilisée pour un certain ordre de traitement des éléments du côté gauche ou droit, puis nous pouvons utiliser le résultat précédent dans le calcul ultérieur. Cela signifie que nous pouvons analyser les éléments. Il en résultera toujours une collection.

• La méthode LEFT_REDUCE fonctionne de la même manière que la méthode REDUCE.

• RIGHT_REDUCE est l'opposé de reductionLeft, c'est-à-dire qu'il accumule les valeurs dans RIGHT et continue de changer la variable de gauche.

• reductionLeftOption et reductionRightOption sont similaires à left_reduce et right_reduce, la seule différence est qu'ils renvoient des résultats dans l'objet OPTION.

Une partie de la sortie pour le code mentionné ci-dessous serait: -

en utilisant l' scanopération sur une liste de nombres (en utilisant la seedvaleur 0)List(-2,-1,0,1,2)

• {0, -2} => - 2 {-2, -1} => - 3 {-3,0} => - 3 {-3,1} => - 2 {-2,2} => 0 Liste de balayage (0, -2, -3, -3, -2, 0)

• {0, -2} => - 2 {-2, -1} => - 3 {-3,0} => - 3 {-3,1} => - 2 {-2,2} => 0 scanLeft (a + b) Liste (0, -2, -3, -3, -2, 0)

• {0, -2} => - 2 {-2, -1} => - 3 {-3,0} => - 3 {-3,1} => - 2 {-2,2} => 0 scanLeft (b + a) Liste (0, -2, -3, -3, -2, 0)

• {2,0} => 2 {1,2} => 3 {0,3} => 3 {-1,3} => 2 {-2,2} => 0 scanRight (a + b) Liste ( 0, 2, 3, 3, 2, 0)

• {2,0} => 2 {1,2} => 3 {0,3} => 3 {-1,3} => 2 {-2,2} => 0 scanRight (b + a) Liste ( 0, 2, 3, 3, 2, 0)

utilisation reduce, foldopérations sur une liste de chaînesList("A","B","C","D","E")

• {A, B} => AB {AB, C} => ABC {ABC, D} => ABCD {ABCD, E} => ABCDE réduire (a + b) ABCDE
• {A, B} => AB {AB, C} => ABC {ABC, D} => ABCD {ABCD, E} => ABCDE réduireLeft (a + b) ABCDE
• {A, B} => BA {BA, C} => CBA {CBA, D} => DCBA {DCBA, E} => EDCBA reductionLeft (b + a) EDCB
• {D, E} => DE {C, DE} => CDE {B, CDE} => BCDE {A, BCDE} => ABCDE réduireDroite (a + b) ABCDE
• {D, E} => ED {C, ED} => EDC {B, EDC} => EDCB {A, EDCB} => EDCBA reductionRight (b + a) EDCBA

Code:

object ScanFoldReduce extends App {

    val list = List("A","B","C","D","E")
            println("reduce (a+b) "+list.reduce((a,b)=>{
                print("{"+a+","+b+"}=>"+ (a+b)+"  ")
                a+b
            }))

            println("reduceLeft (a+b) "+list.reduceLeft((a,b)=>{
                print("{"+a+","+b+"}=>"+ (a+b)+"  ")
                a+b
            }))

            println("reduceLeft (b+a) "+list.reduceLeft((a,b)=>{
                print("{"+a+","+b+"}=>"+ (b+a)+"  " )
                b+a
            }))

            println("reduceRight (a+b) "+list.reduceRight((a,b)=>{
                print("{"+a+","+b+"}=>"+ (a+b)+"  " )
                a+b
            }))

            println("reduceRight (b+a) "+list.reduceRight((a,b)=>{
                print("{"+a+","+b+"}=>"+ (b+a)+"  ")
                b+a
            }))

            println("scan            "+list.scan("[")((a,b)=>{
                print("{"+a+","+b+"}=>"+ (a+b)+"  " )
                a+b
            }))
            println("scanLeft (a+b)  "+list.scanLeft("[")((a,b)=>{
                print("{"+a+","+b+"}=>"+ (a+b)+"  " )
                a+b
            }))
            println("scanLeft (b+a)  "+list.scanLeft("[")((a,b)=>{
                print("{"+a+","+b+"}=>"+ (b+a)+"  " )
                b+a
            }))
            println("scanRight (a+b) "+list.scanRight("[")((a,b)=>{
                print("{"+a+","+b+"}=>"+ (a+b)+"  " )
                a+b
            }))
            println("scanRight (b+a) "+list.scanRight("[")((a,b)=>{
                print("{"+a+","+b+"}=>"+ (b+a)+"  " )
                b+a
            }))
//Using numbers
     val list1 = List(-2,-1,0,1,2)

            println("reduce (a+b) "+list1.reduce((a,b)=>{
                print("{"+a+","+b+"}=>"+ (a+b)+"  ")
                a+b
            }))

            println("reduceLeft (a+b) "+list1.reduceLeft((a,b)=>{
                print("{"+a+","+b+"}=>"+ (a+b)+"  ")
                a+b
            }))

            println("reduceLeft (b+a) "+list1.reduceLeft((a,b)=>{
                print("{"+a+","+b+"}=>"+ (b+a)+"  " )
                b+a
            }))

            println("      reduceRight (a+b) "+list1.reduceRight((a,b)=>{
                print("{"+a+","+b+"}=>"+ (a+b)+"  " )
                a+b
            }))

            println("      reduceRight (b+a) "+list1.reduceRight((a,b)=>{
                print("{"+a+","+b+"}=>"+ (b+a)+"  ")
                b+a
            }))

            println("scan            "+list1.scan(0)((a,b)=>{
                print("{"+a+","+b+"}=>"+ (a+b)+"  " )
                a+b
            }))

            println("scanLeft (a+b)  "+list1.scanLeft(0)((a,b)=>{
                print("{"+a+","+b+"}=>"+ (a+b)+"  " )
                a+b
            }))

            println("scanLeft (b+a)  "+list1.scanLeft(0)((a,b)=>{
                print("{"+a+","+b+"}=>"+ (b+a)+"  " )
                b+a
            }))

            println("scanRight (a+b)         "+list1.scanRight(0)((a,b)=>{
                print("{"+a+","+b+"}=>"+ (a+b)+"  " )
                a+b}))

            println("scanRight (b+a)         "+list1.scanRight(0)((a,b)=>{
                print("{"+a+","+b+"}=>"+ (a+b)+"  " )
                b+a}))
}

Pour la collection x avec les éléments x0, x1, x2, x3 et une fonction arbitraire f, vous avez les éléments suivants:

1. x.reduceLeft    (f) is f(f(f(x0,x1),x2),x3) - notice 3 function calls
2. x.reduceRight   (f) is f(f(f(x3,x2),x1),x0) - notice 3 function calls
3. x.foldLeft (init,f) is f(f(f(f(init,x0),x1),x2),x3) - notice 4 function calls
4. x.foldRight(init,f) is f(f(f(f(init,x3),x2),x1),x0) - notice 4 function calls
5. x.scanLeft (init,f) is f(init,x0)=g0
                          f(f(init,x0),x1) = f(g0,x1) = g1
                          f(f(f(init,x0),x1),x2) = f(g1,x2) = g2
                          f(f(f(f(init,x0),x1),x2),x3) = f(g2,x3) = g3
                          - notice 4 function calls but also 4 emitted values
                          - last element is identical with foldLeft
6. x.scanRight (init,f) is f(init,x3)=h0
                          f(f(init,x3),x2) = f(h0,x2) = h1
                          f(f(f(init,x3),x2),x1) = f(h1,x1) = h2
                          f(f(f(f(init,x3),x2),x1),x0) = f(h2,x0) = h3
                          - notice 4 function calls but also 4 emitted values
                          - last element is identical with foldRight

En conclusion

• scanest comme foldmais émet également toutes les valeurs intermédiaires
• reduce n'a pas besoin d'une valeur initiale qui est parfois un peu plus difficile à trouver
• fold a besoin d'une valeur initiale un peu plus difficile à trouver:
  • 0 pour les sommes
  • 1 pour les produits
  • premier élément pour min (certains pourraient suggérer Integer.MAX_VALUE)
• pas sûr à 100% mais il semble qu'il existe ces implémentations équivalentes:
  • x.reduceLeft(f) === x.drop(1).foldLeft(x.head,f)
  • x.foldRight(init,f) === x.reverse.foldLeft(init,f)
  • x.foldLeft(init,f) === x.scanLeft(init,f).last