Когда мне следует использовать reduceLeft
, reduceRight
, foldLeft
, foldRight
, scanLeft
или scanRight
?
Мне нужна интуиция / обзор их различий - возможно, на нескольких простых примерах.
Когда мне следует использовать 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, если вы хотите перейти вперед по коллекции.
List
, чтобы затем применить foldLeft
. Другие коллекции могут реализовывать другие стратегии. В общем, если foldLeft
и foldRight
могут использоваться взаимозаменяемо (ассоциативное свойство применяемого оператора), то foldLeft
более эффективен и предпочтителен.
- person Trylks; 21.04.2016
Обычно метод REDUCE, FOLD, SCAN работает, накапливая данные в LEFT и продолжая изменять переменную RIGHT. Основное различие между ними - УМЕНЬШЕНИЕ, СЛОЖЕНИЕ: -
Складывание всегда будет начинаться со значения seed
, т.е. начального значения, определяемого пользователем. Reduce выдаст исключение, если коллекция пуста, тогда как fold возвращает начальное значение. Всегда приводит к одному значению.
Сканирование используется для некоторого порядка обработки элементов слева или справа, тогда мы можем использовать предыдущий результат в последующих вычислениях. Это означает, что мы можем сканировать предметы. Всегда приводит к сбору.
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)
с использованием _6 _, _ 7_ операций над списком строк List("A","B","C","D","E")
Код:
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
needs an initial value that is a little harder to find:
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
reduce
иfold
НЕ в существовании начального значения - скорее, это следствие более глубокой математической причины. - person samthebest   schedule 06.08.2014