Kiedy należy używać reduceLeft, reduceRight, foldLeft, foldRight, scanLeftlub scanRight?

Chcę intuicji / przeglądu ich różnic - być może z kilkoma prostymi przykładami.

Ogólnie rzecz biorąc, wszystkie 6 funkcji składania stosuje operator binarny do każdego elementu kolekcji. Wynik każdego kroku jest przekazywany do następnego kroku (jako dane wejściowe do jednego z dwóch argumentów operatora binarnego). W ten sposób możemy kumulować wynik.

reduceLefti reduceRightzsumuj pojedynczy wynik.

foldLefti foldRightzsumuj pojedynczy wynik, używając wartości początkowej.

scanLefti scanRightkumuluje kolekcję pośrednich skumulowanych wyników przy użyciu wartości początkowej.

Gromadzić

Od LEWEGO i do przodu ...

Dzięki kolekcji elementów abci operatorowi binarnemu addmożemy zbadać, co robią różne funkcje składania, przechodząc do przodu od elementu LEFT kolekcji (od A do 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

Od PRAWEJ i wstecz ...

Jeśli zaczniemy od elementu PRAWO i przejdziemy wstecz (od C do A), zauważymy, że teraz drugi argument naszego operatora binarnego kumuluje wynik (operator jest taki sam, po prostu zmieniliśmy nazwy argumentów, aby wyjaśnić ich role ):

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)

.

Skumuluj

Od LEWEGO i do przodu ...

Gdybyśmy zamiast tego skumulowali jakiś wynik przez odjęcie, zaczynając od elementu LEFT kolekcji, skumulowalibyśmy wynik za pomocą pierwszego argumentu resnaszego operatora binarnego 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)

Od PRAWEJ i wstecz ...

Ale wypatruj teraz odmian xRight! Pamiętaj, że (nie-) skumulowana wartość w odmianach xRight jest przekazywana do drugiego parametru resnaszego operatora binarnego 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) 

Ostatnia lista (-2, 3, -1, 4, 0) może nie jest tym, czego byś intuicyjnie oczekiwał!

Jak widzisz, możesz sprawdzić, co robi Twój foldX, po prostu uruchamiając scanX zamiast tego i debugować skumulowany wynik na każdym kroku.

Dolna linia

• Skumuluj wynik za pomocą reduceLeftlub reduceRight.
• Skumuluj wynik z foldLeftlub foldRightjeśli masz wartość początkową.

• Zbierz kolekcję wyników pośrednich za pomocą scanLeftlub scanRight.

• Użyj odmiany xLeft, jeśli chcesz przejść do przodu przez kolekcję.

• Użyj wariacji xRight, jeśli chcesz cofnąć się przez kolekcję.

Zwykle metoda REDUCE, FOLD, SCAN polega na gromadzeniu danych na LEWYM i zmienianiu zmiennej PRAWEJ. Główną różnicą między nimi jest REDUKCJA, FOLD to: -

Fold zawsze zaczyna się od seedwartości, tj. Wartości początkowej zdefiniowanej przez użytkownika. Reduce zwróci wyjątek, jeśli kolekcja jest pusta, a gdy fold zwróci wartość nasion. Zawsze będzie skutkować pojedynczą wartością.

Skanowanie jest używane dla pewnego porządku przetwarzania elementów z lewej lub prawej strony, następnie możemy wykorzystać poprzedni wynik w kolejnych obliczeniach. Oznacza to, że możemy skanować przedmioty. Zawsze przyniesie kolekcję.

• Metoda LEFT_REDUCE działa podobnie do metody REDUCE.

• RIGHT_REDUCE jest przeciwny do parametru zmniejszonego Left, tzn. Gromadzi wartości w PRAWYM i ciągle zmienia lewą zmienną.

• ZmniejszLeftOption i zmniejszRightOption są podobne do left_reduce, a right_reduce różni się tylko tym, że zwracają wyniki w obiekcie OPTION.

Część danych wyjściowych dla wymienionego poniżej kodu to:

za pomocą scanoperacji na liście liczb (za pomocą seedwartości 0)List(-2,-1,0,1,2)

• {0, -2} => - 2 {-2, -1} => - 3 {-3,0} => - 3 {-3,1} => - 2 {-2,2} => 0 Lista skanowania (0, -2, -3, -3, -2, 0)

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

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

• {2,0} => 2 {1,2} => 3 {0,3} => 3 {-1,3} => 2 {-2,2} => 0 scanRight (a + b) Lista ( 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)

korzystania reduce, foldoperacje na liście ciągówList("A","B","C","D","E")

• {A, B} => AB {AB, C} => ABC {ABC, D} => ABCD {ABCD, E} => ABCDE zmniejsz (a + b) ABCDE
• {A, B} => AB {AB, C} => ABC {ABC, D} => ABCD {ABCD, E} => ABCDE zmniejsz Lewy (a + b) ABCDE
• {A, B} => BA {BA, C} => CBA {CBA, D} => DCBA {DCBA, E} => EDCBA zmniejsz Lewy (b + a) EDCB
• {D, E} => DE {C, DE} => CDE {B, CDE} => BCDE {A, BCDE} => ABCDE redukcja Prawo (a + b) ABCDE
• {D, E} => ED {C, ED} => EDC {B, EDC} => EDCB {A, EDCB} => EDCBA redukcja Prawo (b + a) EDCBA

Kod :

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}))
}

Dla kolekcji x z elementami x0, x1, x2, x3 i dowolną funkcją f masz:

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

Podsumowując

• scanjest podobny, foldale także emituje wszystkie wartości pośrednie
• reduce nie potrzebuje wartości początkowej, która czasem jest nieco trudniejsza do znalezienia
• fold potrzebuje wartości początkowej, która jest nieco trudniejsza do znalezienia:
  • 0 dla sum
  • 1 dla produktów
  • pierwszy element dla min (niektóre mogą sugerować Integer.MAX_VALUE)
• nie jestem w 100% pewien, ale wygląda na to, że istnieją te równoważne implementacje:
  • 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