Commit Logs

Scala fold, foldLeft and foldRight

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
2
3
def fold[A1 >: A](z: A1)(op: (A1, A1) ⇒ A1): A1
def foldLeft[B](z: B)(op: (B, A) ⇒ B): B
def foldRight[B](z: B)(op: (A, B) ⇒ B): B

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
2
3
val inputList: List[Int] = List(1, 3, 5)
inputList.foldLeft(0) { (acc, i) => acc + i }
// res1: Int = 9

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

1
2
inputList.foldLeft(0)(_ + _)
// res1: Int = 9

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
2
3
4
5
6
def average(list: List[Double]): Double = list match {
case head :: tail => tail.foldLeft((head, 1.0)) { (avg, cur) =>
((avg._1 * avg._2 + cur)/(avg._2 + 1.0), avg._2 + 1.0)
}._1
case Nil => NaN
}

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
2
3
4
5
6
7
def get[A](list: List[A], idx: Int): A =
list.tail.foldLeft((list.head, 0)) {
(r, cur) => if (r._2 == idx) r else (c, r._2 + 1)
} match {
case (result, index) if (idx == index) => result
case _ => throw new Exception("Bad index!")
}

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
2
def reverse[A](list: List[A]): List[A] =
list.foldLeft(List[A]()) { (r,c) => c :: r }

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
val list: List[Int] = List(1, 3, 5, 7, 9)

list.foldLeft(0)(_ + _)
// This is the only valid order
0 + 1 = 1
1 + 3 = 4
4 + 5 = 9
9 + 7 = 16
16 + 9 = 25 // done

list.foldRight(0)(_ + _)
// This is the only valid order
0 + 9 = 9
9 + 7 = 16
16 + 5 = 21
21 + 3 = 24
24 + 1 = 25 // done

list.fold(0)(_ + _) // 25
// One of the many valid orders
0 + 1 = 1 0 + 3 = 3 0 + 5 = 5
1 3 + 7 = 10 5 + 9 = 14
1 10 + 14 = 24
1 + 24 = 25 // done

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
2
3
4
5
6
7
8
9
// Option.fold(alt)(foo)

val opt1: Option[Int] = Some(5)
opt1.fold(0)(_ + 1)
// res1: Int = 6

val opt2: Option[Int] = None
opt2.fold(0)(_ + 1)
// res2: Int = 0

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!