Scala Notes: Fold

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.