Когда я должен использовать reduceLeft, reduceRight, foldLeft, foldRight, scanLeftили scanRight?

Мне нужна интуиция / обзор их различий - возможно, на нескольких простых примерах.

В общем, все 6-кратные функции применяют бинарный оператор к каждому элементу коллекции. Результат каждого шага передается на следующий шаг (в качестве входных данных для одного из двух аргументов бинарного оператора). Таким образом мы можем накапливать результат.

reduceLeftи reduceRightнакапливаем единый результат.

foldLeftи foldRightсуммируйте один результат, используя начальное значение.

scanLeftи scanRightнакапливать набор промежуточных совокупных результатов с использованием начального значения.

Накапливать

СЛЕВА и вперед ...

С помощью набора элементов abcи бинарного оператора addмы можем исследовать, что делают различные функции свертки при переходе от ЛЕВОГО элемента коллекции (от 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

ВПРАВО и обратно ...

Если мы начнем с ПРАВОГО элемента и вернемся назад (от C к A), мы заметим, что теперь второй аргумент нашего бинарного оператора накапливает результат (оператор тот же, мы просто поменяли имена аргументов, чтобы прояснить их роли ):

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)

.

Декумулировать

СЛЕВА и вперед ...

Если вместо этого мы должны были бы декумулировать некоторый результат путем вычитания, начиная с ЛЕВОГО элемента коллекции, мы бы суммировали результат через первый аргумент resнашего бинарного оператора 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)

ВПРАВО и обратно ...

Но теперь обратите внимание на варианты xRight! Помните, что (де-) накопленное значение в вариантах xRight передается второму параметру resнашего бинарного оператора 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) 

Последний список (-2, 3, -1, 4, 0) может оказаться не тем, что вы интуитивно ожидали!

Как видите, вы можете проверить, что делает ваш foldX, просто запустив вместо этого scanX и отладив накопленный результат на каждом шаге.

Нижняя линия

• Суммируйте результат с помощью reduceLeftили reduceRight.
• Суммируйте результат с foldLeftили, foldRightесли у вас есть начальное значение.

• Накопите набор промежуточных результатов с помощью scanLeftили scanRight.

• Используйте вариант xLeft, если вы хотите продвигаться по коллекции.

• Используйте изменение xRight , если вы хотите идти в обратном направлении через коллекцию.

Обычно методы REDUCE, FOLD, SCAN накапливают данные в LEFT и продолжают изменять переменную RIGHT. Основное различие между ними - УМЕНЬШИТЬ, СЛОЖИТЬ это: -

Складывание всегда будет начинаться со seedзначения, т.е. начального значения, определенного пользователем. Reduce выдаст исключение, если коллекция пуста, тогда как fold возвращает начальное значение. Всегда будет иметь одно значение.

Сканирование используется для некоторого порядка обработки элементов слева или справа, тогда мы можем использовать предыдущий результат в последующих вычислениях. Это означает, что мы можем сканировать предметы. Всегда будет приводить сбор.

• Метод LEFT_REDUCE работает аналогично методу REDUCE.

• RIGHT_REDUCE противоположен reduceLeft, т.е. он накапливает значения в RIGHT и продолжает изменять левую переменную.

• reduceLeftOption и reduceRightOption похожи на left_reduce и right_reduce, с той лишь разницей, что они возвращают результаты в объекте OPTION.

Часть вывода для нижеупомянутого кода будет: -

используя scanоперацию над списком чисел (используя seedзначение 0)List(-2,-1,0,1,2)

• {0, -2} => - 2 {-2, -1} => - 3 {-3,0} => - 3 {-3,1} => - 2 {-2,2} => 0 список сканирования (0, -2, -3, -3, -2, 0)

• {0, -2} => - 2 {-2, -1} => - 3 {-3,0} => - 3 {-3,1} => - 2 {-2,2} => 0 scanLeft (a + b) Список (0, -2, -3, -3, -2, 0)

• {0, -2} => - 2 {-2, -1} => - 3 {-3,0} => - 3 {-3,1} => - 2 {-2,2} => 0 scanLeft (b + a) Список (0, -2, -3, -3, -2, 0)

• {2,0} => 2 {1,2} => 3 {0,3} => 3 {-1,3} => 2 {-2,2} => 0 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) Список ( 0, 2, 3, 3, 2, 0)

использование reduce, foldоперации над списком строкList("A","B","C","D","E")

• {A, B} => AB {AB, C} => ABC {ABC, D} => ABCD {ABCD, E} => ABCDE уменьшить (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} => DCBA {DCBA, 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

Код:

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

Для коллекции x с элементами x0, x1, x2, x3 и произвольной функцией f у вас есть следующее:

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

В заключении

• scanпохоже, foldно также испускает все промежуточные значения
• reduce не требует начального значения, которое иногда немного сложнее найти
• fold требуется начальное значение, которое немного сложнее найти:
  • 0 для сумм
  • 1 для продуктов
  • первый элемент для min (некоторые могут предложить Integer.MAX_VALUE)
• не уверен на 100%, но похоже, что есть эти эквивалентные реализации:
  • 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