One of the functional programming tricks in Scala that I recently learned and enjoyed is folding, namely the `fold`, `foldLeft` and `foldRight` functions. As implied by their names, the three methods share many concepts in common, but there are also subtle differences in their implementations.

As I am a firm believer of learning by examples, I put together some code snippets (many thanks to this post) that hopefully could help you better understand the nitty-gritty of `fold`, `foldLeft` and `foldRight`.

## Common folding concepts

Folding is a very powerful operation on Scala Collections. First thing first, let’s take a look at the signatures of the three implementations of folding, i.e. `fold`, `foldLeft` and `foldRight`.

In essence, these functions process a data structure recursively through use of a pre-defined combining operation `op` and an initial value `z`, then gives a return value. If used correctly, these methods can often do a lot of complicated things with a small amount of code.

To illustrate the common concepts among the three folding functions (we will save the explantion of their differences for the next section), I will take `foldLeft` as an example here for 1) it is relatively easier to understand and 2) it arguably is the most frequently used folding technique at least based on my experiences.

### Get started

Let’s get started with a very simple example - calcuate the summation of a list of integers with `foldLeft`, in case you don’t really have too much experience with this operation.

or, even simpler, by taking advantage of a few Scala’s “type-less” tricks.

Very simple and elegant, isn’t it? But, if you were as curious as I am, you might wonder what is going on under the hood. Well, let’s take a closer look at it.

As specified by its signature, the `foldLeft` function here takes two argument 1) an initial value of `0` and 2) a pre-defined combining operation `op` that, again, takes two arguments, i.e. the accumulated value `acc` and the current value `i`. And you might have already guessed, `foldLeft` processes the list of intergers from left to right.

That is, at the start of execution, the function will invoke the operation `op` on the given intial value and the first item of the list. Note that, if the list was empty, `foldLeft` would terminate and return the initial value.

The result `1` is passed into `acc` as the accumulated value to a subsequent invocation of `op` on the next value of the list.

This process repeats for each item of the list until all items in the list have been iterated over from left to right and the final result will be returned. You can almost visualize the entire process as the following.

Alright, I have probably spent too much time here, but I want to make sure you have the basics ready for the more fun stuff.

### More examples

Here are more examples for `foldLeft` that I think are really interesting. Note that some examples may have better solutions, but, for the sake of learning, we will only use `foldLeft` to solve them here.

Length

Write the `foldLeft` equivalent of `List.length`.

Last

Write the `foldLeft` equivalent of `List.last`.

Average

Calculate the average of values from a given `List[Double]`.

You can probably achieve the same goal by combining the calculation of sum and length of a list, but I would like to show you this more “complicated” approach. One of the reasons is that, if you look at the signature of `foldLeft`, the `op: (B, A) => B` operation doesn’t have to take in parameters of the same type, as long as `B` matches with the type of return value and initial value, and I think this is a quite powerful feature in many cases.

This example takes advantage of it, where `B` here is a `Tuple2` object `(Double, Double)`. Note that we usually use `TupleX` (X < 23, a quite arbitrary limit) to bundle an ordered sequences of values and access it via `._1`, `._2` and etc. Also, if you haven’t noticed already, Scala converts a comma-delimited series of values in parentheses into the appropriate `TupleX` automatically.

Get

Get the value given an integer index of a list and throw an error if out of bound.

Here is another `foldLeft` example with `Tuple2` to help you understand this trick better. The second part of the snippet is what we call pattern matching in Scala. It is also a very powerful technique that probably worths its own post, but hopefully you at least get a taste of how it can be used from this simple example.

Reverse

Reverse the order of a list.

Hopefully you have learnt a thing or two about `foldLeft` (and folding in general) through these examples. As you can see, folding is really a useful technique to process a sequence of values. Next time, when you need to get something out of Scala Collections, you should think if you can achieve the goal via folding.

## Difference in implementations

As I mentioned, `fold`, `foldLeft` and `foldRight` share many concepts in common and we have already gone through some of their applications. Now is the time that we take a look at their subtle differences so that we know how to use them correctly and more efficiently.

### Order of operation

The primary difference among `fold`, `foldLeft` and `foldRight` is the order in which the combining operation `op` iterates through the sequence. As their names implied, `foldLeft` starts from the left side (the first value) and the values are added to the combining operation in left-to-right order; `foldRight`, on the contrary, starts from the right side (the last value) and the values are processed in right-to-left order. THe more interesting operation to me is the `fold`, which goes in no particular order.

There are some advantages and contraints of `fold` because of this implementation and we will talk more about it later, but now let’s revisit our simple summation example.

As you can see, `foldLeft` and `foldRight` are linear operations, while `fold` is allowed to be a tree operation, which is quite nice for parallelization. But, in order for this implemetation to be possible, there are some constraints.

First of all, the starting value must be neutral since it may be introduced multiple times (e.g., `0` appears 3 times in our toy example) and it should not change final results. A few neutral values are `0` for addition, `1` for multiplication and `Nil` for list operation.

Secondly, as specified in its signature, the combining operation `op` must result in the same type as the type of the arguments it takes in and this type `A1` must be a supertype of the object being folding `A`.

### Another use case of `fold`

Somewhat irrelevant, I would like to introduce you another use case of `fold` on `scala.Option`. It maps a function `foo` over the value of an `Option` (if any) or returns an alternative value `alt` if it is absent.

You can essentially achieve the same result with `map`/`getOrElse` and there was a discussion on this topic if you are interested.

I personally prefer the `map`/`getOrElse` way of doing things, since it is more intuitive and less confusing given the two different use cases of `fold`.

## Ending

Functional idioms are really fascinating to me. Depending on the specific use cases, but I find them to be elegant and concise in many situations. You will find me posting more articles on this topic in the coming weeks.

Hope you enjoyed this post and, as always, feel free to leave your comments as they will be very helpful to make this blog better!