1. Introduction
In this tutorial, we’re going to look at the Fold Left and Fold Right operations for collections. We’ll explore the difference between them and the cases when we should use each.
2. What Is Folding?
In functional programming, folding is a standard operation that can be used to collapse collections down to a single result. It works by going over the collection and applying the same accumulator function to combine the currently accumulated result with the next one in the collection.
A common example is summing a collection of numbers. In this case, the accumulator function that we want to apply to the numbers in the collection is plus. The desired result is:
result <- 1 + 2 + 3;
We can describe this as folding the collection with the plus function:
plus <- (acc, next) => acc + next;
result <- [1, 2, 3].fold(plus);
This equates to the following:
result <- plus(plus(1, 2), 3);
We can clearly see that the outcome is the same as our desired result.
3. Fold vs. Reduce
Notably, we’ll sometimes see the term Reduce used instead of Fold. Depending on the context, this might be nothing more than an alternative word for the same operation. However, in other contexts, it can mean a fold operation with a provided initial value.
Let’s see an example:
result <- [1, 2, 3].reduce(plus, 4);
This is the same as:
result <- plus(plus(plus(4, 1), 2), 3);
The big advantage here is that we no longer need to have the output of the accumulator function be of the same type as the collection entries. In our previous Fold example, the accumulator function is required to have two parameters and a return value that are all the same type. These also need to be of the same type as the entries in the collection we’re working with.
With a Reduce operation, the output of the accumulator function can now be of a different type compared to the collection entries, as long as it’s the same as the provided initial value and the first parameter to our accumulator function:
concat <- (acc, next) => acc + next.toString();
result <- [1, 2, 3].reduce(concat, "");
This equates to the following:
result <- concat(concat(concat("", 1.toString()), 2.toString()), 3.toString());
Here, result will be a string, whereas the collection entries are integers.
4. Fold Left vs. Fold Right
When talking about folding operations, we’ll often see them referred to as Fold Left or Fold Right. This determines whether we should apply our accumulator function starting from the left or right end of our collection.
If no direction is specified, this typically means Fold Left. In this case, we want to start combining values from the left-hand side of our collection.
This is exactly what we’ve already seen:
result <- [1, 2, 3, 4].foldLeft(plus);
result <- plus(plus(plus(1, 2), 3), 4);
Here, we combine the first two entries in the collection with our accumulator function. Next, we combine this result with the next entry in the collection. This continues until we reach the end of the collection.
Fold Right means that we start combining values from the right-hand side of our collection:
result <- [1, 2, 3, 4].foldRight(plus);
result <- plus(1, plus(2, plus(3, 4)));
In this case, we combine the first entry in the collection with the result of folding the rest of the collection. We then repeat this for every step until we reach the end of the collection.
5. Order of Operations
Fold Left and Fold Right seem very similar to each other, so what’s the difference? The most significant difference is the order in which the operations are applied. In some cases, this makes no difference at all. However, in other cases, it can be critical.
If our accumulator function is associative, then Fold Left and Fold Right will produce exactly the same result. We can see this directly from the definition of the associative property:
(x + y) + z = x + (y + z) for all x, y, z in S
The left-hand side of this equation corresponds to how Fold Left works, whereas the right-hand side corresponds to how Fold Right works. Therefore, if the operation is associative, then Fold Left and Fold Right will produce the same result.
However, if the operation isn’t associative, then we’ll get different results. For example, instead of addition, let’s look at the subtract function:
leftResult <- [1, 2, 3].foldLeft(subtract); // (1 - 2) - 3 = -4
rightResult <- [1, 2, 3].foldRight(subtract); // 1 - (2 - 3) = 2
Consequently, if we know that our accumulator function isn’t associative, then it becomes important that we select the correct direction to fold in. However, if our accumulator function is associative, then we’ll need to explore other reasons for selecting between folding left or right.
6. Implementation Efficiency
Another factor to consider is how efficient the implementations are. The traditional definitions of Fold Left and Fold Right are recursive:
algorithm FoldLeft(collection, initial, fn):
if collection.empty:
return initial;
head <- collection[0]
tail <- collection.slice(1)
return FoldLeft(tail, fn(initial, head), fn)
algorithm FoldRight(collection, initial, fn):
if collection.empty:
return initial;
head <- collection[0]
tail <- collection.slice(1)
return fn(head, FoldRight(tail, initial, fn))
Notably, these examples are being provided with an initial value, but this is only to make them easier to follow. It’s equally possible to implement both without using initial values.
The two algorithms are very similar, with the only difference being in how the recursive call is made. However, this difference is important from an efficiency perspective. In particular, Fold Left is tail recursive, whereas Fold Right isn’t. Therefore, this means that we can easily rewrite Fold Left to be iterative instead. This will then be more efficient in both time and memory usage:
algorithm FoldLeft(collection, initial, fn):
result <- initial
for next in collection:
result <- fn(result, next)
return result
Rewriting Fold Right to be iterative is much harder, and in some cases, it may be impossible – it would require the collection to be reverse-iterable, which not all collections are.
This then means that Fold Left is likely to be more efficient than Fold Right for the same collection. However, this assumes that the operation is associative, as we saw earlier. Additionally, the efficiency gain is only likely to matter with very large collections.
7. Conclusion
In this article, we’ve had a look at what folding is in the context of functional programming. We’ve explored some of the differences between Fold Left and Fold Right, and some of the ways to help select between them.