Fold and Reduce, both are ways to aggregate the elements of a collection/lists.
Reduce can be thought of as a special implementation of fold.
A fold is a way of getting a single value by operating on a list of values.
In the functional world, folding a list is the only way to “collapse” or “reduce” (or “fold”) a list into a single value. Since the list is transformed into a single value, the fold function is a special type of transformer called a consumer.The abstract reasoning behind list consumers is this:
- If I can do something to the first item in the list and the first item in the rest of the list
- Then I can do something to the whole list.
This is actually a very useful and important concept in computer science. Whenever you have anything that can be viewed as a list (whether or not it actually is a list), you can “consume” it using this principle.As an example, let’s consider summing a list of numbers. To do that, I just take the first item in the list and add it to the first item in the rest of the list. I keep adding-in the first item of the next “rest of the list” until there is no more list left. Let’s see that in action.
(1 2 3 4 5) Here is my list. 1 + (2 3 4 5) I take the first-item-of-the-list and the-rest-of-the-list. 1+2 <-(_ 3 4 5) I add the-first-item-of-the-rest-of-the-list to the initial first item. 3 + (3 4 5) This leaves me with a new rest-of-the-list. 6 + (4 5) I do the same thing again. 10 + (5) And again. 15 + () And again. Now I have no list left. 15 Therefore, the sum is 15. (((1 +2) +3) +4) +5 = 15.
This is the essence of a fold operation.
The type of object in the list is generally considered homogeneous: it is a list of integers, or strings, or booleans, etc. However, the type of thing returned from the fold operation need not be the same type as the list elements.
Fold-left can be considered as operating on the list from the left:
foldl + 0 (1 2 3) ((0 + 1) + 2) + 3 (1 + 2) + 3 3 + 3 6
Fold-right works from the opposite end:
foldr + 0 (1 2 3) ((0 + 3) + 2) + 1 (3 + 2) + 1 5 + 1 6
There are two things to notice here. First, foldl works left-to-right, while foldr works in reverse.
Here is the signature of foldLeft (could also have been foldRight for the point I’m going to make):
def foldLeft [B] (z: B)(f: (B, A) => B): BAnd here is the signature of reduceLeft (again the direction doesn’t matter here)
def reduceLeft [B >: A] (f: (B, A) => B): BThese two look very similar and thus caused the confusion. reduceLeft is a special case of foldLeft (which by the way means that you sometimes can express the same thing by using either of them).
When you call reduceLeft say on a List[Int] it will literally reduce the whole list of integers into a single value, which is going to be of type Int (or a supertype of Int, hence [B >: A]).
When you call foldLeft say on a List[Int] it will fold the whole list (imagine rolling a piece of paper) into a single value, but this value doesn’t have to be even related to Int (hence [B]).
reduceLeft is just a convenience method. It is equivalent to
list.tail.foldLeft(list.head)(_)
- foldLeft has a paramaterized type of
Bwhile reduceLeft has a paramaterized type ofB >: A - foldLeft is a curried function where the first curried group takes the folds initial value and that reduceLeft is non curried and doesn’t take an initial value at all
- In foldLeft the accumulator and the final return type (B) must be related to the item type (A).
So if reduceLeft doesn’t take an initial value as an argument, then what is it’s initial value? The initial value of reduceLeft is the initial value of the collection. So if you have a List[Int] and you reduceLeft over it, you will only ever be able to produce an Int (or a supertype of Int) from that operation. However, foldLeft is capable of producing any type you can pass into the initial value.
References
https://www.coursera.org/learn/progfun1/lecture/UpWlj/lecture-5-5-reduction-of-lists
https://coderwall.com/p/4l73-a/scala-fold-foldleft-and-foldright
http://blog.plasmaconduit.com/reduve-vs-fold-in-scala/
My Developer Journal 