Categories

# 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:

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

## One reply on “Scala Saturday – The foldLeft Method”

anonsays:

helpful visualization, thanks! didn’t realize `reduce` could be generalized like this.

This site uses Akismet to reduce spam. Learn how your comment data is processed.