Difference between reduce and fold

Question

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

Answer 1

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).

Answer 2

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 :).