Unfolding foldLeft and foldRight in Scala

The fold method is a Higher Order Function in Scala and it has two variant namely,
i. foldLeft
ii. foldRight
In this blog, we will look into them in detail and try to understand how they work.

Before moving ahead, I want to clarify that the fold method is just a wrapper to foldLeft, i.e. the fold method internally invokes the foldLeft method. So, now let’s get started.

foldLeft

foldLeft performs iteration on the collection elements. In order to understand, let’s look at what the function declaration looks like.

def foldLeft[B](z: B)(op: (B, A) => B): B

Now let’s break it down and try to understand what the declaration means.

(z: B)

The first call argument as mentioned z represents the initial value of type B that should be used.

(z: B)(op: (B, A) => B)

The function has a curried form. It takes two different arguments in two different function calls.

For a collection of type A, it returns a result of type B. Here B may be the same type as A, related to A, or unrelated to A. There is no relationship defined between A and B in the declaration.

(op: (B, A) => B)

Next, the function takes a function op here. This function takes two arguments, applies the binary operator, and computes the result.

One key thing to note here is that the order of the arguments will matter in this function. The first argument should be of type B and the second argument should be of type A. So in essence, foldLeft takes an initial element to start with and a function with two arguments then applies the binary operator iteratively and gets the final result.

You may be thinking why is it called foldLeft?
So, let’s visualize how it works.

Now let’s say we have a collection of some numbers and we want to calculate the sum of these numbers.

The fold in the foldLeft indicates what we want to do. We fold things. And the left represents the direction from which we start folding.

So now we see our collection and z standing on the left side of the collection.

As discussed earlier, we understood that the first argument is of type B. Do you see why?

Because the binary operator takes the value from z first, then picks the item from the collection and applies the operator. The result calculated is used as the value of z in the next iteration. Following up with the same iteration, the new values of z will be created, and when the process completes, the value of z which is of type B is returned as the final value.

Now let’s see it in action.

val numbers = List(2.39, 3.54, 4.50, 3.21, 5.81)

val sumL: Double = numbers.foldLeft(0.0)((b, a) => b + a)
numbers.foldLeft(100.0)((b, a) => b + a)

val minimumL: Double = numbers.foldLeft(numbers.head)((b, a) => b min a)

val maximumL: Double = numbers.foldLeft(numbers.head)((b, a) => b max a)

val productL: Double = numbers.foldLeft(1.0)((b, a) => b * a)

Here we have created a collection of numbers called numbers.
In the first example, we calculate the sum of the numbers collection. Our initial element is 0.0 a Double and then we provide the implementation as the addition of 2 numbers.

Next, we find the minimum in the numbers collection. Initially, we pass the first element of the collection as the value of z, and the implementation body compares that with the rest of the elements, finding the actual minimum element in the collection.

Next, we perform a similar operation to find out the maximum number in the collection.

Finally, we calculate the product and provide 1.0 as the initial element, through which every other member of the collection would apply to and get the final product of all the numbers back.

Motivation towards using foldLeft

1. You might be thinking, calling the sum method on the collection is much easier and simpler, right?

numbers.sum 

But do you know that sum internally calls foldLeft.

def sum[B >: A](implicit num: Numeric[B]): B = foldLeft(num.zero)(num.plus)

This is how, foldLeft is called under the hood if we call sum.

2. Also, you might be thinking, reduceLeft is another option to perform the same operation.

numbers.reduceLeft((b, a) => b + a)

Yes, you are right. But do you know reduceLeft also calls foldLeft internally in case of Collection?

def reduceLeft[B >: A](f: (B, A) => B): B = if(!isEmpty) tail.foldLeft[B](head)(f)

Additionally, the extra benefit you get with foldLeft is that you can change the initial/seed value like:

numbers.foldLeft(100.0)((b, a) => b + a)

Example: Let’s find the maximum and minimum price from a collection of amounts.

Imperative way (working with mutable variables):

  def process(input: Vector[Double]): (Double, Double) = {
    var maxPrice: Double = input(0)   //mutable variable
    var minPrice: Double = input(0)

    for (price <- input) {
      if (price > maxPrice) {
        maxPrice = price
      }
      if (price < minPrice) {
        minPrice = price
      }
    }

    (maxPrice, minPrice)
  }

  process(Vector(10, 5, 15, 20, 18, 36, 13))

Functional way with foldLeft (working with immutable variables)

def processFunc(input: Vector[Double]): (Double, Double) =
    input.foldLeft(input(0), input(0)) { case ((maxPrice, minPrice), price) =>
      val newMaxPrice = if (price > maxPrice) price else maxPrice   
      val newMinPrice = if (price < minPrice) price else minPrice
      (newMaxPrice, newMinPrice)
    }

  processFunc(Vector(10, 5, 15, 20, 18, 36, 13))

foldRight

def foldRight[B](z: B)(op: (A, B) => B): B

foldRight looks very similar to foldLeft, except one difference; the order of arguments passed in op are opposite. Because foldRight starts from the right side of the collection and takes the last element from the collection, then picks the z as the second parameter, applies the operator, and introduces the new value of z for the next iteration. It follows this process until all the elements are used in the computation. At this time, the current value of z becomes the final value.

It is important to note that, foldRight method reverses the Collection internally and applies foldLeft on it.

 override def foldRight[B](z: B)(op: (A, B) => B): B =
    reverse.foldLeft(z)((right, left) => op(left, right))

This is all from this blog. I hope it helped you. 🙂 Keep learning, keep growing!!!