Wann soll ich reduceLeft, reduceRight, foldLeft, foldRight, scanLeftoder scanRight?

Ich möchte eine Intuition / einen Überblick über ihre Unterschiede - möglicherweise mit einigen einfachen Beispielen.

Im Allgemeinen wenden alle 6-fach-Funktionen einen binären Operator auf jedes Element einer Sammlung an. Das Ergebnis jedes Schritts wird an den nächsten Schritt weitergegeben (als Eingabe für eines der beiden Argumente des Binäroperators). Auf diese Weise können wir ein Ergebnis kumulieren .

reduceLeftund reduceRightkumulieren ein einzelnes Ergebnis.

foldLeftund foldRightkumulieren Sie ein einzelnes Ergebnis mit einem Startwert.

scanLeftund scanRighteine Sammlung von kumulativen Zwischenergebnissen unter Verwendung eines Startwerts kumulieren.

Akkumulieren

Von LINKS und vorwärts ...

Mit einer Sammlung von Elementen abcund einem binären Operator können addwir untersuchen, was die verschiedenen Faltfunktionen tun, wenn Sie vom linken Element der Sammlung (von A nach C) vorwärts gehen:

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

Von RECHTS und rückwärts ...

Wenn wir mit dem RIGHT-Element beginnen und rückwärts gehen (von C nach A), werden wir feststellen, dass jetzt das zweite Argument für unseren binären Operator das Ergebnis akkumuliert (der Operator ist der gleiche, wir haben nur die Argumentnamen geändert, um ihre Rollen zu verdeutlichen ):

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)

.

Entkumulieren

Von LINKS und vorwärts ...

Wenn stattdessen waren wir de-kumulieren von dem Elemente LEFT einiges Ergebnis durch Subtraktion einer Sammlung beginnen, würden wir das Ergebnis durch das erste Argument kumulieren resunseren Binäroperators 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)

Von RECHTS und rückwärts ...

Aber achten Sie jetzt auf die xRight-Variationen! Denken Sie daran, dass der (de-) kumulierte Wert in den xRight-Variationen an den zweiten Parameter resunseres Binäroperators übergeben wird 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) 

Die letzte Liste (-2, 3, -1, 4, 0) ist vielleicht nicht das, was Sie intuitiv erwarten würden!

Wie Sie sehen, können Sie überprüfen, was Ihr foldX tut, indem Sie stattdessen einfach einen scanX ausführen und das kumulierte Ergebnis bei jedem Schritt debuggen.

Endeffekt

• Kumulieren Sie ein Ergebnis mit reduceLeftoder reduceRight.
• Kumulieren Sie ein Ergebnis mit foldLeftoder foldRightwenn Sie einen Startwert haben.

• Kumulieren Sie eine Sammlung von Zwischenergebnissen mit scanLeftoder scanRight.

• Verwenden Sie eine xLeft-Variante, wenn Sie die Sammlung vorwärts durchgehen möchten .

• Verwenden Sie eine xRight-Variante, wenn Sie die Sammlung rückwärts durchgehen möchten .

Normalerweise funktioniert die Methode REDUCE, FOLD, SCAN, indem Daten auf LEFT gesammelt und die Variable RIGHT weiter geändert werden. Der Hauptunterschied zwischen ihnen ist REDUZIEREN, FALTEN ist: -

Das Falten beginnt immer mit einem seedWert, dh einem benutzerdefinierten Startwert. Reduzieren löst eine Ausnahme aus, wenn die Sammlung leer ist, wobei Falte den Startwert zurückgibt. Wird immer einen einzelnen Wert ergeben.

Der Scan wird für einige Verarbeitungsreihenfolgen von Elementen von links oder rechts verwendet. Anschließend können wir das vorherige Ergebnis für die nachfolgende Berechnung verwenden. Das heißt, wir können Elemente scannen. Wird immer eine Sammlung ergeben.

• Die LEFT_REDUCE-Methode funktioniert ähnlich wie die REDUCE-Methode.

• RIGHT_REDUCE steht im Gegensatz zu reductLeft one, dh es sammelt Werte in RIGHT und ändert die linke Variable weiter.

• reductLeftOption und reduRightOption ähneln left_reduce und right_reduce. Der einzige Unterschied besteht darin, dass sie Ergebnisse im OPTION-Objekt zurückgeben.

Ein Teil der Ausgabe für den unten genannten Code wäre: -

Verwenden der scanOperation über eine Liste von Zahlen (Verwenden des seedWerts 0)List(-2,-1,0,1,2)

• {0, -2} => - 2 {-2, -1} => - 3 {-3,0} => - 3 {-3,1} => - 2 {-2,2} => 0 Scan-Liste (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) List ( 0, 2, 3, 3, 2, 0)

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

Verwendung reduce, foldOperationen über eine Liste von StringsList("A","B","C","D","E")

• {A, B} => AB {AB, C} => ABC {ABC, D} => ABCD {ABCD, E} => ABCDE reduziert (a + b) ABCDE
• {A, B} => AB {AB, C} => ABC {ABC, D} => ABCD {ABCD, E} => ABCDE reductLeft (a + b) ABCDE
• {A, B} => BA {BA, C} => CBA {CBA, D} => DCBA {DCBA, E} => EDCBA reduLeft (b + a) EDCB
• {D, E} => DE {C, DE} => CDE {B, CDE} => BCDE {A, BCDE} => ABCDE reduRight (a + b) ABCDE
• {D, E} => ED {C, ED} => EDC {B, EDC} => EDCB {A, EDCB} => EDCBA reduRight (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}))
}

Für die Sammlung x mit den Elementen x0, x1, x2, x3 und einer beliebigen Funktion f haben Sie Folgendes:

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

Abschließend

• scanist wie fold, gibt aber auch alle Zwischenwerte aus
• reduce benötigt keinen Anfangswert, der manchmal etwas schwieriger zu finden ist
• fold braucht einen Anfangswert, der etwas schwerer zu finden ist:
  • 0 für Summen
  • 1 für Produkte
  • erstes Element für min (einige schlagen möglicherweise Integer.MAX_VALUE vor)
• nicht 100% sicher, aber es sieht so aus, als gäbe es diese äquivalenten Implementierungen:
  • 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