Fold is a general purpose operation on list (e.g., `List[A]`

), which involves iterating (over each element) and applying a binary function–

f: A -> B -> B

to reduce the list to a single result, i.e., `B`

. The initial value of `B`

is provided as an argument and then at each stage of the operation, `f`

is applied to the successive elements of `List[A]`

, with `B`

that has been accumulated so far.

In this post, we implement and explain key characteristics of `foldRight`

and `foldLeft`

.

## Fold Left

Following diagram illustrates generic `foldLeft`

, where the initial value is given by `a`

.

As the name suggests, the iteration starts from the left. Evidently, the signature of the function follows–

foldLeft: A List -> B -> (A -> B -> B) -> B

Tail-recursive implementation of `foldLeft`

is outlined next.

def foldLeft[A, B](l: List[A], z: B)(f: (B, A) => B): B = l match { case Nil => z // contains result case x :: xs => foldLeft(xs, f(z, x))(f) }

The above `length`

can be implemented using `foldLeft`

as follows:

def lengthTR[A](l: List[A]) = foldLeft(l, 0)((acc, _) => acc + 1)

## Fold Right

`foldRight`

is quite similar to `foldLeft`

, yet there are some subtle differences. To begin with, the unwinding phase starts from the end of the list. In effect, iteration direction is from the right to left. As a result, `foldRight`

is not a tail-recursive function. Following illustrates `foldRight`

function —

We can implement `foldRight`

as follows.

def foldRight[A,B](l:List[A], z:B)(f: (A,B) => B): B = l match{ case Nil => z case x::xs => f(x, foldRight(xs, z)(f)) }

To show how it works, let’s apply it in implementing `length`

of a `List`

.

def length[A](l: List[A]) = foldRight(l, 0)((x,y)=> y+1)

As noted earlier, we can see that the unwinding phase start after reaching at the end of the `List`

and thus, `foldRight`

is not a tail-recursive function.

During the execution of `foldRight`

, `Nil`

gets replaced by the value of `z`

, the second argument of `foldRight`

, whereas every `Con`

gets replaced by an invocation of `f`

.

## References

The images used to explain `foldLeft`

and `foldRight`

are taken from “Elements of Functional Programming” by Chris Reade.