# ~/Blog

## Brandon Rozek

PhD Student @ RPI studying Automated Reasoning in AI and Linux Enthusiast.

# Different Views of Fold and Their Combinations

Published on

Updated on

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


Converting to fold solution:

val l1 = List(1,2,3)
val l2 = List(4,5,6)
val id_outer = List.empty[(Int, Int)]
val id_inner = List.empty[(Int, Int)]

l1.foldLeft(id_outer)((c1, n1) =>
c1 ++ l2.foldLeft(id_inner)((c2, n2) =>
c2 :+ (n1, n2)
)
)


1. Thanks Clare for thinking of this example! ↩︎