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 `foldRight`may 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.