Zmniejszyć, złożyć lub zeskanować (w lewo / w prawo)?

187

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.

Marc Grue
źródło
Polecam zobaczyć stackoverflow.com/questions/25158780/…
samthebest
1
Dzięki za wskaźnik. To trochę powyżej mojej wiedzy technicznej :) Czy w mojej odpowiedzi jest coś, co Twoim zdaniem powinno zostać wyjaśnione / zmienione?
Marc Grue,
Nie, wystarczy wskazać trochę historii i znaczenie dla MPP.
samthebest,
Cóż, ściśle mówiąc, rozróżnienie pomiędzy reducei foldNIE jest istnieniem wartości początkowej - raczej jest to konsekwencja głębszego leżącego u podstaw matematycznego powodu.
samthebest,

Odpowiedzi:

370

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ę.
Marc Grue
źródło
14
Jeśli się nie mylę, lewa wersja może korzystać z optymalizacji wywołania ogona, co oznacza, że ​​jest znacznie bardziej wydajna.
Trylks,
3
@Marc, podoba mi się przykłady z literami, wszystko stało się jasne
Muhammad Farag
@Trylks foldRight można również zaimplementować za pomocą tailrec
Timothy Kim
@TimothyKim może, przy zoptymalizowanych do tego celu niełatwych implementacjach. Np. W szczególnym przypadku list Scala ten sposób polega na odwróceniu, Listaby zastosować foldLeft. Inne kolekcje mogą wdrażać różne strategie. Ogólnie rzecz biorąc, jeśli foldLefti foldRightmożna go stosować zamiennie (właściwość asocjacyjna zastosowanego operatora), wówczas foldLeftjest on bardziej wydajny i preferowany.
Trylks,
9

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}))
}
Puneeth Reddy V.
źródło
9
Ten post jest ledwo czytelny. Skracaj zdania, używaj prawdziwych słów kluczowych (np. ReplaceLeft zamiast LEFT_REDUCE). Używaj prawdziwych matematycznych strzałek, znaczników kodu, gdy masz do czynienia z kodem. Preferuj przykłady wejścia / wyjścia zamiast wyjaśniać wszystko. Obliczenia pośrednie utrudniają czytanie.
Mikaël Mayer,
4

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
raisercostin
źródło