Simply Scala – foldLeft & foldRight

This requires some basic knowledge about Scala. This time I’ll try to explain a bit about foldLeft and foldRight. These functions are meant to derive a result out of a collection of values. As a start I will give three examples in Java:

  • Summing all the values inside a collection of numbers.
    	int sumIntegers(List list) {
    	  int accumulator = 0;
    	  for (int item: list) {
    	    accumulator = accumulator + item;
    	  }
    	  return accumulator;
    	}
    	
  • Multiplying all the values inside a collection of numbers.
            int productIntegers(List list) {
              int accumulator = 1;
              for (int item: list) {
                accumulator = accumulator * item;
              }
              return accumulator;
            }
            
  • Finding the shortest string inside a collection of strings.
    	// For the sake of simplicity we are assuming that there are no 'null' contents in the list.
    	String findShortestString(List list) {
    	  String accumulator = list.get(0);
    	  for (String item: list) {
    	    accumulator = item.length() < accumulator.length() ? item : accumulator;
    	  }
    	  return accumulator;
    	}
    	

They look very much alike, don’t you think?

Such scenarios of deriving some value out of a collection of values are not unusual. Hence the solutions are also very similar. They are different mainly in two things: The initial accumulator value and How the accumulator is calculated as it is compared to every item. If only we could generalise the three functions above into a generic function where we could pass those 2 things, the code will be much simpler. More or less it will look like this code below. Please note that this code won’t compile since in Java (< version 8) we cannot pass function as a parameter. I’m just trying to convey my point here.

<T> T deriveSomethingOutOfThisList(List list, T accumulator, Function f) {
  for (T item: list) {
    accumulator = f(accumulator, item)
  }
  return accumulator;
}

How do we implement these functions in Scala?

In Scala a built-in feature has been provided to cater for such scenarios, which is by using either foldLeft or foldRight. This is how those three functions are defined in Scala

  // For the sake of simplicity we are assuming that there are no 'null' contents in the list.

  // Initial accumulator value = 0. 
  // The accumulator is recalculated with an addition in every iteration.
  val sumIntegers = list.foldLeft(0)((accumulator, item) => accumulator + item)

  // Initial accumulator value = 1.
  // The accumulator is recalculated with a multiplication in every iteration.
  val productIntegers = list.foldLeft(1)((accumulator, item) => accumulator * item)

  // Initial accumulator value = the first item in the list.
  // The accumulator is compared and updated if the iterated item is shorter.
  val shortestString = list.foldLeft(list(0))((accumulator, item) => {
                         if (item.length<accumulator.length) item
                         else accumulator
                       })

I’m discussing the 1st one. Once you understand how it works for the 1st one, it should be easy enough to understand the other two. Take a look at this line:

  val sumIntegers = list.foldLeft(0)((accumulator, item) => accumulator + item)

Method foldLeft belongs to the collection instance. It takes two parameters:

  • The initial accumulator value, which is 0, and
  • The function to recalculate the accumulator.This function takes two parameters: The accumulator and the list item. In this case we want the accumulator to be the sum of every list item. Hence the addition.

The other two examples follow the same behaviour as the first one. I’m leaving them to you to play around with the values and give it a try.

BTW, the naming is not very strict in the function definition above. I’m just naming them accumulator and item for the sake of readability. If you want, you can name them differently as shown below:

  val sumIntegers = list.foldLeft(0)((a, b) => a + b)

Wait, where is foldRight?

In all the examples stated above we always use foldLeft. What about foldRight? What’s the difference between them? Why am I not using foldRight at all in these examples?

There are a few differences between them:

  • Method foldLeft will trace the list item from the left to the right. While foldRight, right to the left. Shown below:
    • foldLeft: ((((1 + 2) + 3) + 4) + 5)
    • foldRight: (1 + (2 + (3 + (4 + 5))
  • Method foldRightmay throw StackOverflowException if there are too many items in the list. It’s not the case for foldLeft. More detailed explanations below.

Method foldLeft‘s implementation uses the while...do in order to trace every list item while method foldRight will trace every list item recursively. There is a drawback by looping the list recursively: it consumes more memory. Stack memory to be more exact. If the list contains too many items, the system is more likely to throw StackOverflowException. That’s why in most cases foldLeft is always preferred to foldRight.

But why are they different?

The answer lies in the way a List is structured in Scala. Scala’s List is different than Java’s. I’d just briefly say that when Scala defines a list such as List(1, 2, 3), in the back-end it’s actually structured as List(1, List(2, List(3, Nil))). Yes, by its very nature List is nested in Scala. Pretty strange, huh?

This demands another article for more thorough explanation. I have no plan to cover this in the future. I’m sure other people can explain it better than I do.

So basically foldRight is useless?

Yes. Most of the time. I have not yet found a scenario where it is better to use foldRight rather than foldLeft. And I don’t think this behaviour will change in the near future. It’s just the way it is natively structured in Scala.

And now, the not-so-sweetener syntactic sugars.

There is a syntactic sugar for method foldLeft and foldRight. Personally, I don’t like it because the way it’s used is not very common and confusing. Anyway, you can define the sumIntegers method above by using either foldLeft and foldRight like this:

  • foldLeft:
        val sumIntegers = (0 /: list)((accumulator, item) => accumulator + item)
        
  • foldRight:
        val sumIntegers = (list :\ 0)((item, accumulator) => accumulator + item)
        

Please remember not to get yourself mixed-up with the parameters location. Not a very sweet syntactic sugars, aren’t they? 🙂 This concludes my post for today. Please leave feedbacks below if you have any.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s