减少和折叠之间的差异

Question

阅读这篇关于Scala中的reduce vs fold的文章http://josephmoniz.github.io/blog/2013/04/04/scala-reduce-vs-fold/它表示"你正在考虑N的一些价值并执行聚合操作这样最终结果通常是<= N的某个值."

但是这个陈述是错误的,因为对N个值求和产生的值> = N？

更新:我认为<=在这种情况下意味着相同的类型或子类型

Answer 1

我认为这是一个有缺陷的表征.最好像这样考虑折叠:

In:
  initial value
  way to combine stuff with initial value
  collection
Out:
  combined stuff

减少是这样的:

In:
  way to combine stuff
  collection
Out:
  combined stuff

也就是说,区别在于你是否有一个初始值(甚至可能与你在集合中的类型不同!),折叠,或者你是否只是折叠你已经拥有的值,如减少.

如果你有一个自然的零,即可以在不改变它结合的情况下组合的东西,那么你可以实现reduce作为从零开始的折叠.例如,对于乘法,零是1(因为1*x == x),所以

List(1,2,3).fold(1){_ * _}
List(1,2,3).reduce{_ * _}

给出相同的答案.(但是,只有第一个在空列表中给出答案!)

要看一个折叠如何更加通用的例子,请考虑这个 - 这里有一个foldLeft,所以我们知道在操作的左侧传递初始值 -

List(1,2,3).foldLeft(List(0))((ns,n) => ns ++ List.fill(n+1)(n))

这给了List(0, 1, 1, 2, 2, 2, 3, 3, 3, 3).

Answer 2

reduce使用称为“monoid”的概念来获取“零值”作为折叠中累加器的初始值设定项*

Answer 3

折叠需要提供“起始元素”，reduce会自动将序列的第一个元素作为起始，因此它们在某种程度上是等效的：

val L = List(1,2,3,4)
val H = L.head
val T = L.tail

L.reduce(_+_) ~== T.fold(H)(_+_)

减少更紧凑的内容，但是通过折叠，您可以提供不同的开始元素并更改操作结果，因此：

2014 + L.reduce(_+_) ~== L.fold(2014)(_+_) // NB: here we use L, not T for fold

当您从简单的算法转向一些更复杂的二进制运算（例如Set + Int）时，事情将变得更加令人兴奋并且更有利于折叠：

List(1,2,3,3,2,2,1).foldLeft(Set[Int]())(_ + _) // will produce Set(1, 2, 3)

...您可以折叠JDBC更新调用:)。