Understanding reduce and fold operations in scala

Fold and reduce are one of the most important functions that you will use in scala if you are doing any sort development on a collection of data. They are extremely useful in processing a sequence. I am providing a very simple explanation for fold now to make it easier to understand and we will look at the official scala doc definition for fold later in this post.

Theory of Fold and Reduce

Fold and Reduce – There is a sequence or collection of data and you need to go through this data by applying a function that expects two elements that are adjacent to each other in the collection, until the entire sequence is processed. The end result is you output a result after processing the entire sequence comparing two elements of the sequence at a time until all elements are processed.

//Fold Signature
def fold[A1 >: A](z: A1)(op: (A1, A1) => A1): A1

The function definition indicates – the fold operation supplies two elements of the sequence to a function you supply and that function should produce and output of type A1, the same type as the sequence is. Fold also takes and initial value as indicated in ( z: A1). Please note all the types should be same as the type of sequence. If sequence is of Int, the initial input should be int and output also should be int.

//Reduce Signature
def reduce[A1 >: A](op: (A1, A1) => A1): A1

Reduce is exactly same expect it doesn’t take the initial value that fold allows.

The fold and reduce are available as fold, reduce reduceLeft, reduceRight, foldLeft and foldRight. When you invoke just fold or reduce, you won’t get any guarantee on the order of processing as scala doc mentions – “The order in which operations are performed on elements is unspecified and may be nondeterministic.” This is true for both reduce and fold. You want the processing to happen from left to right use reduceLeft or foldLeft and vice versa for processing from right to left. For most of the algorithms it doesn’t matter if you process left to right or right to left. For example, it doesn’t matter for a sum or product of a sequence of numbers. In such cases, which is the majority of the case, you can just use fold or reduce.

These methods helps to walk through the elements in a sequence, applying a function you supply to two neighboring elements in the sequence producing a new result, and that result is compared to the next element in the sequence to produce a new result. Let us understand the above in detail with an example

Example – Fold, FoldLeft

val t = Array(1, 3, 5, 7, 9, 11);
t.foldLeft(0)(_ + _);

t is a sequence of numbers and we applied the foldLeft on it. The function supplied is a simple add function. The (_+_) is the short hand equivalent for writing ((x,y) => x+y). We could have written it as t.foldLeft(0) (((x,y) => x+y), instead. But it is better to use the concise form.

The resulting output is 36: Int

Let us understand how this output got generated. Take a note that we supplied 0 as the initial value. (the initial value feature is not there with reduce and other than that there is no difference between reduce and fold operations). Let us walk through the process of how fold operations works with the above data. (0,1) will be the first two numbers this gets added up and output will be 1. Now the next data set will be (1,3) resulting in 4. So the entire steps are as follows

(0,1) = 1
(1,3) = 4
(4,5) = 9
(9,7) = 16
(16,9) = 25
(25,11) = 36

The same explanation holds good for reduce and fold with an exception that, the fold accepts an initial value that you can supply where as reduce doesn’t have that feature.

Let us apply the reduceLeft to the same sequence t

val t = Array(1, 3, 5,7,9,11);
t.reduceLeft(_ + _);

The output will be 36, same as fold. The result would be different if you supply another initial value to the foldLeft instead of 0. For example ,

t.foldLeft(5)(_ + _);

This will return the output as 41

More Examples

//Product of a sequence of numbers
val t = Array(1, 3, 5,7,9,11);
t.reduce(_ * _);
//Output 10395:Int

Biggest number in a sequence

//Biggest number 
val t = Array(1, 3, 5,7,9,11);
t.reduce((a,b)=>{ if(a > b) a; else b; } );
//Output 11: Int

The official scala doc says – ” Folds the elements of this collection using the specified associative binary operator. The default implementation in IterableOnce is equivalent to foldLeft but may be overridden for more efficient traversal orders. ” You can read the doc here

Leave a Comment