Scala中foldLeft和reduceLeft的区别

Question

Scala中foldLeft和reduceLeft的区别

scalafunctional-programmingfoldhigher-order-functions

219

我已经学习了foldLeft和reduceLeft之间的基本区别：

foldLeft:

需要传递初始值

reduceLeft:

将集合的第一个元素作为初始值
如果集合为空，则会抛出异常

还有其他区别吗？

为什么要使用两个具有类似功能的方法？

- Rajesh Pitty

1

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

如果您将问题编辑为“Scala中fold和reduce的区别”，那就太好了。 - pedram bashiri

请返回翻译后的文本。 - Dmytro Mitin

8个回答

206

reduceLeft只是一个便利的方法。它等同于：

list.tail.foldLeft(list.head)(_)

- Kim Stebel

14

好的回答。这也突显了为什么 fold 可以处理空列表而 reduce 不能。 - Mansoor Siddiqui

51

foldLeft更加通用，你可以使用它来生成与原始输入完全不同的结果。而reduceLeft只能产生与集合类型相同或超类的最终结果。例如：

List(1,3,5).foldLeft(0) { _ + _ }
List(1,3,5).foldLeft(List[String]()) { (a, b) => b.toString :: a }

foldLeft将使用最后一次折叠的结果（第一次使用初始值）和下一个值应用闭包。

另一方面，reduceLeft首先将列表中的两个值组合起来，然后将其应用于闭包。接下来，它将累积结果与其余值组合。参见：

List(1,3,5).reduceLeft { (a, b) => println("a " + a + ", b " + b); a + b }

如果列表为空，foldLeft可以将初始值表示为合法结果。另一方面，如果reduceLeft在列表中找不到至少一个值，则没有合法值。

- thoredge

6

作为参考，如果应用于空容器，则reduceLeft将出现以下错误。

java.lang.UnsupportedOperationException: empty.reduceLeft

重新编写代码以使用

myList foldLeft(List[String]()) {(a,b) => a+b}

是一种潜在的选择。另一个选项是使用reduceLeftOption变体，它返回一个被包装在Option中的结果。

myList reduceLeftOption {(a,b) => a+b} match {
  case None    => // handle no result as necessary
  case Some(v) => println(v)
}

- Martin Smith

5

他们都在Scala标准库中的基本原因可能是因为它们都在Haskell标准库中（称为foldl和foldl1）。如果没有reduceLeft，它经常会在不同的项目中被定义为方便方法。

- Alexey Romanov

4

来自Scala函数式编程原理（Martin Odersky）：

函数reduceLeft是基于更通用的函数foldLeft定义的。

foldLeft类似于reduceLeft，但它接受一个额外的参数作为累加器z，当在空列表上调用foldLeft时，该参数将被返回：

(List (x1, ..., xn) foldLeft z)(op) = (...(z op x1) op ...) op x

[与reduceLeft不同，当应用到空列表时会抛出异常。]

该课程（参见第5.5讲）提供了这些函数的抽象定义，展示了它们之间的差异，尽管它们在模式匹配和递归使用方面非常相似。

abstract class List[T] { ...
  def reduceLeft(op: (T,T)=>T) : T = this match{
    case Nil     => throw new Error("Nil.reduceLeft")
    case x :: xs => (xs foldLeft x)(op)
  }
  def foldLeft[U](z: U)(op: (U,T)=>U): U = this match{
    case Nil     => z
    case x :: xs => (xs foldLeft op(z, x))(op)
  }
}

请注意，foldLeft返回类型为U的值，该类型不一定与List[T]相同，但reduceLeft返回与列表相同类型的值。

- C8H10N4O2

0

Scala 2.13.3，示例：

val names = List("Foo", "Bar")
println("ReduceLeft: "+ names.reduceLeft(_+_))
println("ReduceRight: "+ names.reduceRight(_+_))
println("Fold: "+ names.fold("Other")(_+_))
println("FoldLeft: "+ names.foldLeft("Other")(_+_))
println("FoldRight: "+ names.foldRight("Other")(_+_))

输出：

ReduceLeft: FooBar
ReduceRight: FooBar
Fold: OtherFooBar
FoldLeft: OtherFooBar
FoldRight: FooBarOther

- Saurav Sahu

0

要真正理解fold/reduce的含义，可以参考这个链接：http://wiki.tcl.tk/17983，里面有非常好的解释。一旦你掌握了fold的概念，reduce就会随着上面的答案一起出现：list.tail.foldLeft(list.head)(_)

- Henry H.

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

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

- agilesteel · Accepted Answer

在给出实际答案之前，有几件事情需要提醒一下：

你的问题与left没有任何关系，它更多的是关于缩减和折叠的区别。
两者的区别根本不在于实现方式，只需要看一下函数签名即可。
这个问题与Scala没有特别的关系，它更多的是关于函数式编程的两个概念。

回到你的问题:

这里是foldLeft的函数签名（对于我将要说明的点，也可以使用foldRight）：

def foldLeft [B] (z: B)(f: (B, A) => B): B

这里是 reduceLeft 的签名（方向在这里并不重要）

def reduceLeft [B >: A] (f: (B, A) => B): B

这两者看起来非常相似，因此导致了混淆。reduceLeft 是 foldLeft 的一个特例（顺便说一下，这意味着你有时候可以使用它们中的任何一个来表示相同的东西）。

当你在 List[Int] 上调用 reduceLeft 时，它会将整个整数列表缩减为一个单一的值，该值将为 Int 类型（或 Int 的超类型，因此是 [B >: A]）。

当你在 List[Int] 上调用 foldLeft 时，它将折叠整个列表（想象一下卷纸）成为一个单一的值，但这个值不必与 Int 相关（因此是 [B]）。

以下是一个示例：

def listWithSum(numbers: List[Int]) = numbers.foldLeft((List.empty[Int], 0)) {
   (resultingTuple, currentInteger) =>
      (currentInteger :: resultingTuple._1, currentInteger + resultingTuple._2)
}

这个方法接受一个List[Int]并返回一个Tuple2[List[Int], Int]或(List[Int], Int)。它计算出列表中所有整数的和，并返回一个由整数列表和其总和组成的元组。需要注意的是，由于使用了foldLeft而不是foldRight，返回的列表是反向的。

观看One Fold to rule them all以获取更深入的解释。