24

Reading this article about reduce vs fold in Scala http://josephmoniz.github.io/blog/2013/04/04/scala-reduce-vs-fold/ it states "you are taking some value of N and performing aggregation operations on it such that the end result is typically some value of <= N."

But is this statement false since summing over N values produces a value >= N ?

Update : I think <= in this case means same type or sub-type

blue-sky
  • 51,962
  • 152
  • 427
  • 752

4 Answers4

51

I think it's a flawed characterization. It's better to think of fold like this:

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

And reduce is like this:

In:
  way to combine stuff
  collection
Out:
  combined stuff

That is, the difference is whether you have an initial value (which might not even be of the same type as what you've got in the collection!), as fold does, or whether you just collapse the values you already have, as reduce does.

If you have a natural zero, that is, something that can be combined without changing what it combines with, then you can implement reduce as a fold starting with a zero. For example, for multiplication the zero is 1 (because 1*x == x), so

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

give the same answer. (Only the first gives an answer on an empty list, however!)

To see an example of how fold is entirely more general, consider this one--here with a foldLeft so we know to pass the initial value in on the left-hand side of the operation--

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

which gives List(0, 1, 1, 2, 2, 2, 3, 3, 3, 3).

Rex Kerr
  • 166,841
  • 26
  • 322
  • 407
7

Fold needs "starting element" be provided, reduce will automatically take 1st element of sequence as starting, so they are kind of equivalent for some degree:

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

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

Reduce more compact, but with fold you have ability to provide different start element and change result of the operation, so:

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

Things will be more exciting and more favorable for fold when you will step out of simple arithmetics to some more complex binary operations like Set + Int:

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

... you can fold an JDBC update call :).

ya_pulser
  • 2,620
  • 2
  • 16
  • 21
  • 2
    Example with 2014 is misleading. Fold can use the initial value multiple times, therefore it should be a neutral element. – Suma Oct 18 '17 at 10:52
  • 3
    No, fold doesn't use the initial value multiple times, and it only needs to be a neutral element if you want to equate fold and reduce on the same operation on the same collection, like so: `L.reduce(_ + _) == L.fold(0)(_ + _)`. So the example, `2014 + L.reduce(_ + _) ~== L.fold(2014)(_ + _)` isn't really misleading – ThePretendProgrammer Nov 09 '17 at 03:54
5

reduce uses conception called "monoid" to get "zero value" as initializer for accumulator in fold*

wedens
  • 1,782
  • 14
  • 18
0

see answer here:

difference between foldLeft and reduceLeft in Scala

reduce and fold are shortcuts for reduceLeft and foldLeft

Community
  • 1
  • 1
Sergey
  • 376
  • 1
  • 2
  • 4
  • 2
    "reduce and fold are shortcuts for reduceLeft and foldLeft": not so. `reduceLeft` and `foldLeft` apply the operator from left to right (head to tail). `reduceRight` and `foldRight` apply it from right to left. As for `reduce` and `fold`, the order is **unspecified**, which is what allows to have parallel implementations for it (see `ParIterableLike`). As a consequence, you'd better be sure that your operator is associative when calling `reduce`, otherwise the result will not be deterministic. – Régis Jean-Gilles Aug 06 '14 at 07:48