缩减、折叠还是扫描（左/右）？

Question

缩减、折叠还是扫描（左/右）？

scalascala-collectionsreducefold

202

何时应该使用reduceLeft、reduceRight、foldLeft、foldRight、scanLeft或scanRight？

我想要一个它们之间差异的直觉/概述-可能包括一些简单的例子。

- Marc Grue

建议您查看https://dev59.com/hV8e5IYBdhLWcg3w_-dM。 - samthebest

1

谢谢你的指针。这有点超出了我的技术知识 :) 你认为我的回答中有什么需要澄清/改变的吗？ - Marc Grue

不，只是指出一点历史和与MPP的相关性。 - samthebest

严格来说，“reduce”和“fold”的区别并不在于是否存在起始值——而是由更深层次的数学原因所导致的。 - samthebest

请提供具体的上下文，以便我可以更准确地进行翻译。 - Dmytro Mitin

3个回答

11

通常 REDUCE、FOLD 和 SCAN 方法都是通过在左侧累积数据并不断更改右侧变量来工作的。它们之间的主要区别是：

FOLD 总是从一个 seed 值开始，即用户定义的起始值。如果集合为空，REDUCE 会抛出异常，而 FOLD 则返回 seed 值。将始终产生单个值。

SCAN 用于对项目进行左或右处理顺序，然后我们可以在后续计算中利用先前的结果。这意味着我们可以扫描项目。将始终产生集合。

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 scan List(0, -2, -3, -3, -2, 0)
{0,-2}=>-2 {-2,-1}=>-3 {-3,0}=>-3 {-3,1}=>-2 {-2,2}=>0 scanLeft (a+b) List(0, -2, -3, -3, -2, 0)
{0,-2}=>-2 {-2,-1}=>-3 {-3,0}=>-3 {-3,1}=>-2 {-2,2}=>0 scanLeft (b+a) List(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)

使用 reduce、fold 操作对字符串列表 List("A","B","C","D","E") 进行操作：

{A,B}=>AB {AB,C}=>ABC {ABC,D}=>ABCD {ABCD,E}=>ABCDE reduce (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}))
}

- Puneeth Reddy V

11

这篇文章几乎无法阅读。请缩短句子，使用真正的关键词（例如 reduceLeft 而不是 LEFT_REDUCE）。在处理代码时，请使用真正的数学箭头和代码标签。最好使用输入/输出示例而不是解释所有内容。中间计算会使阅读变得困难。 - Mikaël Mayer

9

对于集合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
- 最小值时为第一个元素（有些人可能会建议使用 Integer.MAX_VALUE）
不确定但看起来好像有这些等效实现：
- 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

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Marc Grue · Accepted Answer

通常，所有6个fold函数都对集合中的每个元素应用一个二元运算符。每个步骤的结果传递到下一个步骤（作为二元运算符的两个参数之一的输入）。通过这种方式，我们可以累积结果。

reduceLeft和reduceRight会累积单个结果。

foldLeft和foldRight使用起始值累积单个结果。

scanLeft和scanRight使用起始值累积一组中间累积结果。

累积

从左向右...

使用元素集合abc和二元运算符add，我们可以探索不同的fold函数在从集合的左侧元素（从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)

.

去累积

从左侧开始...

如果我们将某个结果通过从集合的左侧元素开始进行减法计算来 去累积，我们将通过二元运算符minus的第一个参数res来实现这一过程：

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变数中（去）累加的值传递到我们的二元运算符minus的第二个参数res中：

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)可能不是你直觉上期望的！

正如您所看到的，您可以通过运行scanX而非foldX来检查您的foldX正在做什么，并在每个步骤中调试累积结果。

底线

使用reduceLeft或reduceRight累加结果。
使用foldLeft或foldRight累加结果，如果您有一个起始值。
使用scanLeft或scanRight累积一系列中间结果。
如果要通过集合向前遍历，请使用xLeft变形。
如果要向后遍历集合，请使用xRight变体。