Deep dive into the working of the "fold" operation in Scala

Table of contents

Reading Time: 3 minutes

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)