Scala Saturday – The foldLeft Method

Last week we looked at the reduce operation, and we observed three properties:

• Using reduce on an empty collection yields an exception.
• You can only reduce a collection to a value of the same type as the elements in the collection.
• The order of the items in the collection (usually) matters.

We also noticed that there are several common operations—sum, product, and string concatenation—that are just special cases of reduce.

As it happens, reduce is itself a special case of a more fundamental operation: foldLeft. Furthermore, while order still matters, foldLeft can

• handle empty collections, and
• reduce a collection of one type to a value of a different type.

Why is that? First, foldLeft takes a binary operation just as reduce does, but it also takes a starting value in addition to the collection. That is how foldLeft can handle empty collections. If the collection is empty, you’re just left with the starting value. Second, because you give foldLeft a starting value, that starting value could be of any type; it doesn’t have to match the type of the items in the collection. The reason reduce can only reduce a collection to a value of the same type is because the only starting value it has is the first value in the collection.

Let’s put foldLeft into action.

Our Product Line

We implemented a product operation last week with reduce. Let’s do it this week with foldLeft. This figure illustrates what’s going on:

In multiplication, 1 is the identity value. That is, 1 times x is always x. So then, if you want to calculate the product of a list of integers, make your starting value 1. Here is the code:

val product = List(5,3,6).fold(1)(_*_)
// product: Int = 90

Now what if the list is empty? We cannot handle an empty list with reduce, but what does foldLeft do?

val product = List().fold(1)(_*_)
// product: Int = 1

So then, when foldLeft receives an empty collection, it just returns the starting value—in this case, 1.

Stringing You Along

Last week we also implemented List.mkString with reduce. We can do the same thing with foldLeft but there are some gotchas.

Try a straightforward approach:

val illJoined =
  List("do","mi","sol").foldLeft("")(_ + "-" + _)
// illJoined: String = -do-mi-sol

Eek! What happened? You don’t want the extra hyphen on the front! You just want hyphens in between the elements!

What if you have a list with just one item?

val illJoined =
  List("do").foldLeft("")(_ + "-" + _)
// illJoined: String = -do

No better. The following figure shows you what has happened:

While reduce cannot handle an empty collection, it only starts applying the reduction operation on the first two elements. On the other hand, foldLeft applies the binary operation on the starting value and the first item in the list.

To do mkString right with foldLeft, you have to account for some special cases:

def join(xs: List[String]): String = {
  if (xs.isEmpty) "" 
  else if (xs.length == 1) xs.head
  else xs.tail.foldLeft(xs.head)(_ + "-" + _)
}
val emptyJoined = join(List())
// emptyJoined: String = ""
val singleJoined = join(List("do"))
// singleJoined: String = do
val manyJoined = join(List("do","mi","sol"))
// manyJoined: String = do-mi-sol

From Type to Type

Finally, consider an example of something foldLeft can do that reduce cannot. If reduce receives a list of integers, it can only produce a single integer. If it receives a list of strings, its result is a single string. In contrast, foldLeft can take a list of integers and produce a string. Or it could take a list of strings and produce a list of integers.

For instance, you can use foldLeft to reverse a list:

val reversed =
  (1 to 10).foldLeft(List[Int]()) {
    (xs, x) => x :: xs
  }
// reversed: List[Int] =
//   List(10, 9, 8, 7, 6, 5, 4, 3, 2, 1)

Notice how the starting value is a list, but the type of the elements in the input list Int, not List[Int]. Because the starting value can be a type that is different from the type of the input list elements, the binary operation can transform the elements in the list to match the type of the starting value. In fact, that is the constraint with foldLeft: the type of the result must be type of the starting value. If your starting value is a list, foldLeft must return a list. If your starting value is an integer, foldLeft must return an integer.

Another example is determining the length of the longest string in a list of strings:

val longest =
  List(
    "a","borborygmus","sesquipedalian","small"
  ).foldLeft(0) {
    (n,s) => math.max(n, s.length)
  }
// longest: Int = 14

Here is the documentation on foldLeft in each collection module that defines it:

• Array.foldLeft
• List.foldLeft
• Seq.foldLeft
• Set.foldLeft
• Map.foldLeft

As an exercise, you could try implementing map with foldLeft.