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
.
1 | def fold[A1 >: A](z: A1)(op: (A1, A1) ⇒ A1): A1 |
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.
1 | val inputList: List[Int] = List(1, 3, 5) |
or, even simpler, by taking advantage of a few Scala’s “type-less” tricks.
1 | inputList.foldLeft(0)(_ + _) |
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.
1 | op(acc = 0, i = 1) // 1 |
The result 1
is passed into acc
as the accumulated value to a subsequent invocation of op
on the next value of the list.
1 | op(acc = 1, i = 3) // 4 |
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.
1 | op(op(op(0, 1), 3), 5) // 9 |
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
.
1 | def len(list: List[Any]): Int = list.foldLeft(0) { (count, _) => count + 1 } |
Last
Write the foldLeft
equivalent of List.last
.
1 | def last[A](list: List[A]): A = list.foldLeft[A](list.head) { (_, cur) => cur } |
Average
Calculate the average of values from a given List[Double]
.
1 | def average(list: List[Double]): Double = list match { |
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.
1 | def foldLeft[B](z: B)(op: (B, A) ⇒ B): B |
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.
1 | def get[A](list: List[A], idx: Int): A = |
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.
1 | def reverse[A](list: List[A]): List[A] = |
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.
1 | val list: List[Int] = List(1, 3, 5, 7, 9) |
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
.
1 | def fold[A1 >: A](z: A1)(op: (A1, A1) ⇒ A1): A1 |
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.
1 | // Option.fold(alt)(foo) |
You can essentially achieve the same result with map
/getOrElse
and there was a discussion on this topic if you are interested.
1 | Option.map(foo).getOrElse(alt) |
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!