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.

foldLeft

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 —

foldLeft

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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s