Different Views of Fold and Their Combinations

Published on November 9, 2022

Updated on January 25, 2023

3 minute reading time

Fold is a functional programming pattern that operates over some sequence with a binary operation and a starting value. There are two variants:

FoldLeft: Performs the binary operation from the left of the sequence to the right.

List(1, 2, 3, 4).foldLeft(0)(_ + _)
// ((((0 + 1) + 2) + 3) + 4)
// 10

FoldRight: Performs the binary operation from the right of the sequence to the left.

List(1, 2, 3, 4).foldRight(0)(_ + _)
// (1 + (2 + (3 + (4 + 0))))
// 10

The two fold variants only return the same solution if the function being applied is associative. Which is the case for integer addition above.

Definition and the Two Views

Definition of foldLeft within Scala:

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
  }

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)
  }

Notice that this includes both a recursive and iterative definition within one function! Since most people start off by learning loops, let’s focus on the iterative implementation.

var result = z
while (it.hasNext) {
    result = op(result, it.next())
}

Combining Folds

When building out complex functions we may want to loop multiple times:

While loops next to each other ($n_1 + n_2$ complexity)
While loop within a while loop ($n_1 * n_2$ complexity)

$n_1 + n_2$ Complexity

The following is an example¹ of this class of algorithms.

Given a list of words, title case each word and combine them into a single sentence.

val l1 = List("steve", "is", "doing", "great")
val title = (s: String) => s.substring(0, 1).toUpperCase + s.substring(1)

val it1 = l1.iterator
var id1 = List.empty[String]

while (it1.hasNext) {
    id1 = id1 :+ title(it1.next())
}

val it2 = id1.iterator
var id2 = ""
while (it2.hasNext) {
    id2 = id2 + " " + it2.next()
}

Converting to fold solution:

val l1 = List("steve", "is", "doing", "great")
val title = (s: String) => s.substring(0, 1).toUpperCase + s.substring(1)
val id1 = List.empty[String]
val id2 = ""

l1.foldLeft(id1)((c, n) =>
	c :+ title(n)
).foldLeft(id2)((c, n) =>
	c + " " + n
)

$n_1 * n_2$ Complexity

An example of this class of programs is the Cartesian product $$ (1, 2, 3) \times (4, 5,6) \rightarrow ((1,4), (1,5), (1,6), \dots, (3,4), (3,5), (3,6)) $$ Iterative Implementation:

val listInput1 = List(1,2,3)
val listInput2 = List(4,5,6)

var id_outer = List.empty[(Int, Int)]
val it1 = listInput1.iterator

while (it1.hasNext) {
    var id_inner = List.empty[(Int, Int)]
    val n1 = it1.next()
    val it2 = listInput2.iterator
    while (it2.hasNext) {
        val n2 = it2.next()
        result_inner = result_inner :+ (n1, n2)
    }
    result = result ++ result_inner
}