Mastering Fold Operations in Scala: fold, foldLeft, and foldRight

When working with collections in Scala, it’s common to come across fold, foldLeft, and foldRight. Each has its own purpose and unique way of accumulating elements, which can lead to confusion if you're new to functional programming. In this post, we’ll dive into the specifics of these operations to help you master them.

What is fold?

The fold operation in Scala allows you to combine elements of a collection using an initial value and a binary operation. It’s a high-level abstraction that can be utilized in a variety of scenarios. The syntax for fold is:

collection.fold(initialValue)(binaryOperation)

This operation doesn’t specify the direction in which elements are processed. It leaves it to the underlying collection’s implementation to decide whether to fold from left or right.

For instance:

val nums = List(1, 2, 3, 4, 5)
val sum = nums.fold(0)(_ + _)
println(sum) // Output: 15

In this example, fold sums up the elements of nums, starting with an initial value of 0.

What is foldLeft?

foldLeft processes elements from the leftmost (head) to the rightmost (tail). The syntax is:

collection.foldLeft(initialValue)(operation)

It’s more explicit than fold and always traverses the collection in a left-to-right manner. Here’s an example:

val nums = List(1, 2, 3, 4, 5)
val leftFoldedSum = nums.foldLeft(0)(_ + _)
println(leftFoldedSum) // Output: 15

foldLeft is particularly useful when the operation must be applied sequentially, or when dealing with immutable data structures since each step accumulates the result in the specified order.

When to use foldLeft?

• Processing elements sequentially from left to right.
• Avoiding stack overflows due to tail recursion optimization.
• Operations where order matters.

What is foldRight?

As the name suggests, foldRight starts processing elements from the rightmost (tail) to the leftmost (head). The syntax is:

collection.foldRight(initialValue)(operation)

This operation works differently from foldLeft, as it begins with the last element and works towards the head of the collection:

val nums = List(1, 2, 3, 4, 5)
val rightFoldedSum = nums.foldRight(0)(_ + _)
println(rightFoldedSum) // Output: 15

When to use foldRight?

• Processing elements right-to-left.
• When building structures that benefit from the right-to-left order, like building lists or trees.

A Deep Dive into Their Differences

Order of Processing:

• foldLeft processes elements left-to-right.
• foldRight processes elements right-to-left.
• fold can choose the order based on implementation (default behavior is similar to foldLeft in most collections).

Performance Considerations:

• foldLeft is generally more efficient and stack-safe due to its tail-recursive implementation.
• foldRight can cause a stack overflow on large collections if not handled properly since it’s not tail-recursive.

Use Cases:

• Use foldLeft when you need a predictable left-to-right accumulation order, such as summing values or building results incrementally.
• Use foldRight for operations like reversing a list or constructing recursive data structures.

Example Comparison

Let’s look at an example to understand the difference:

val words = List("Scala", "is", "awesome")

val sentenceFoldLeft = words.foldLeft("")((acc, word) => acc + word + " ")
println(sentenceFoldLeft) // Output: "Scala is awesome "
val sentenceFoldRight = words.foldRight("")((word, acc) => word + " " + acc)
println(sentenceFoldRight) // Output: "Scala is awesome "

Both foldLeft and foldRight yield the same result here, but the way they traverse the list is different. In foldLeft, the accumulator (acc) starts on the left, while in foldRight, the accumulator is on the right.

Originally Published : https://allaroundscala.com/2024/10/20/mastering-fold-operations-in-scala-fold-foldleft-and-foldright