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
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).
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 :).
L.reduce(_ + _) == L.fold(0)(_ + _). So the example, 2014 + L.reduce(_ + _) ~== L.fold(2014)(_ + _) isn't really misleadingreduce uses conception called "monoid" to get "zero value" as initializer for accumulator in fold*
see answer here:
difference between foldLeft and reduceLeft in Scala
reduce and fold are shortcuts for reduceLeft and foldLeft
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.