Réduire, plier ou scanner (Gauche / Droite)?

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

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

155
demandé sur Marc Grue 2013-07-01 20:04:30

2 réponses

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

reduceLeft et reduceRight cumuler un résultat unique.

foldLeft et foldRight cumulent un seul résultat en utilisant une valeur de départ.

scanLeft et scanRight cumulent une collection de résultats cumulatifs intermédiaires à l'aide d'un start valeur.

Accumuler

De gauche à droite...

Avec une collection d'éléments abc et un opérateur binaire add, nous pouvons explorer ce que font les différentes fonctions de pliage en allant de L'élément gauche 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 droit et retournons en arrière (de C à A), nous remarquerons que maintenant le deuxième argument à notre l'opérateur binaire accumule le résultat (l'opérateur est le même, nous venons de changer 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)

.

Dé-cumuler

De gauche à droite...

Si à la place nous devions dé-cumuler un résultat par soustraction à partir de l'élément gauche d'une collection, nous cumulerions le résultat à travers le premier argument res de 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)


à Partir de DROITE et en arrière...

Mais attention aux variations xRight maintenant! Rappelez-vous que la valeur (dé -) cumulée dans les variations xRight est passée au deuxième paramètre res de 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) est peut-être pas ce que vous attendez 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.

Bas ligne

  • Cumuler un résultat avec reduceLeft ou reduceRight.
  • Cumuler un résultat avec foldLeft ou foldRight si vous avez une valeur de départ.
  • Cumuler une collection de résultats intermédiaires avec scanLeft ou scanRight.

  • Utilisez une variation xLeft si vous voulez aller vers l'avant à travers la collection.

  • utilisez une variation xRight si vous voulez aller en arrière à travers la collection.
324
répondu Marc Grue 2013-07-01 20:03:08

Normalement réduire,plier, méthode de balayage fonctionne en accumulant des données sur la gauche et continuer à changer la variable de droite. La principale différence entre eux est de réduire, plier est: -

Fold commencera toujours par une valeur seed, c'est-à-dire une valeur de départ définie par l'utilisateur. Reduce lancera une exception si la collection est vide où as fold redonne la valeur de départ. entraînera toujours une seule valeur.

Scan est utilisé pour certains traitement ordre de articles de gauche ou côté droit, alors nous pouvons utiliser le résultat précédent dans le calcul ultérieur. Cela signifie que nous pouvons scanner les éléments. entraînera toujours une collection.

  • la méthode LEFT_REDUCE fonctionne de manière similaire à la méthode REDUCE.
  • RIGHT_REDUCE est opposé à reduceLeft, c'est-à-dire qu'il accumule des valeurs dans RIGHT et continue à changer la variable left.

  • ReduceLeftOption et reduceRightOption sont similaires à left_reduce et right_reduce seule différence est qu'ils renvoient des résultats en OPTION objet.

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

Utiliser scan opération sur une liste de nombres (à l'aide de seed valeur 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 liste scanLeft (b+A) (0, -2, -3, -3, -2, 0)

  • {2,0}=>2 {1,2}=>3 {0,3}=>3 {-1,3}=>2 {-2,2}=>0 liste scanRight (A + B) (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,fold opérations sur une liste de Chaînes List("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 reduceLeft (a+b) ABCDE
  • {A, B}=>BA {BA,c}=>CBA {CBA,D}=>DRASA {DRASA, E} = >EDCBA reduceLeft (b+a) EDCB
  • {D, E}= > DE {C, DE}= > CDE {B, CDE}= > BCDE {a, BCDE}=>ABCDE reduceRight (a+b) ABCDE
  • {D, E}= > ED {C, ED}=>EDC {B, EDC}=>EDCB {a, EDCB}=>edcba reduceRight (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}))
}
8
répondu Puneeth Reddy V 2015-07-17 06:36:22