Introduction to “fold”
“fold” is a common operation in programming languages including Scala where we essentially use it to “reduce” (note that “reduce” is also an operation in programming languages and has a special meaning in Scala as well). In this blog, we will learn how to use the fold function, understand different types of fold operations (including foldLeft and foldRight), and try to understand how it all works. Although fold operation can be applied on Option, Future, Try, etc.. but here we will understand it through List
Definition of “fold”
This is what the Scala docs say about the fold operation:
Folds the elements of this collection using the specified associative binary operator. The default implementation in IterableOnce is equivalent to foldLeft but may be overridden for more efficient traversal orders.
The order in which operations are performed on elements is unspecified and may be nondeterministic.
Here is how it is defined in the Scala Collections library:
// fold
def fold[A1 >: A](z: A1)(op: (A1, A1) => A1): A1 = foldLeft(z)(op)
// foldLeft
def foldLeft[B](z: B)(op: (B, A) => B): B = this match {
case seq: IndexedSeq[A @unchecked] => foldl(seq, 0, z, op)
case _ =>
var result = z
val it = iterator
while (it.hasNext) {
result = op(result, it.next())
}
result
}
private[this] def foldl[B](seq: IndexedSeq[A], start: Int, z: B, op: (B, A) => B): B = {
@tailrec def loop(at: Int, end: Int, acc: B): B =
if (at == end) acc
else loop(at + 1, end, op(acc, seq(at)))
loop(start, seq.length, z)
}
// foldRight
def foldRight[B](z: B)(op: (A, B) => B): B = reversed.foldLeft(z)((b, a) => op(a, b))
// For internal use
protected def reversed: Iterable[A] = {
var xs: immutable.List[A] = immutable.Nil
val it = iterator
while (it.hasNext) xs = it.next() :: xs
xs
}
Looking at the definition itself can teach us a lot about the working of the “fold” operation.
Some of the key takeaways from the above code are:
- fold and foldLeft are in fact synonymous. fold internally uses foldLeft operation
- foldLeft operation distinguishes between an IndexedSeq and other subclasses Seq like LinearSeq.
- IndexedSeq provides faster length operation. If we see the implementation of “foldl” method, we can see that we are leveraging the length operation to iterate over the Seq
- “case _” is highlighting the fact that mutability is something that we cannot avoid completely. We not only use mutability but also “loop” over the Seq
- Looking at foldRight operation, we can see that it is doing a foldLeft operation on the reversed Seq
- Looking at “foldl” method one will intuitively feel a similar “foldr” method for foldRight. But that is not the case. Note that we do have a “foldr” method but Scala standard library uses it in the reduceRight operation
Illustration of fold (foldLeft) & foldRight
@ val list = List(1, 2, 3, 4)
list: List[Int] = List(1, 2, 3, 4)
@ list.foldLeft("a")(_ + _.toString)
res12: String = "a1234"
@ list.foldRight("a")(_ + _.toString)
res13: String = "1234a"

Conclusion
The fold operation is used a lot in production codes. One such common use case in case of an e-commerce website, we would use the fold operation to calculate the sum of all the prices of the items ordered by the customer.
Note that the fold operations are not restricted to Sequences and are applicable to other monads as well as mentioned in the introduction.
I hope the readers gain a better understanding of “folding” works internally in Scala and would urge them to keep exploring it as this will help them a lot in their development journey.
References: AllAboutScala (A detailed example)