The last two articles in this series were concerned with introducing the concepts of a Semigroup and a Monoid.

Today we turn to a type class which was inspired by Mad magazines fold-ins. If you prefer not to stray into pop culture and stick with computer science, we could also say, that Foldable gives us the semantics of the Map/Reduce paradigm, though that comparison is a little bit stretched as well.

Here is the type class:

trait Foldable[F[_]] {

  def foldMap[A, B](fa: F[A])(f: A => B)(implicit F: Monoid[B]): B
  def fold[M: Monoid](t: F[M]): M = foldMap[M, M](t)(x => x)
  def foldRight[A,B](fa: F[A], z: => B)(f: (A,B) => B) : B
  ... foldRight and foldLeft...
}

The actual scalaz Foldable has a ton more functions, but I think this stripped down version, conveys the basics very well.

One could say that Foldable works on a type constructor F, which represents 0 to many values and can map these values to a new value B in order to reduce them to a single value. Some of the functions provide default values for B via a Monoid instance as in:

def foldMap[A, B](fa: F[A])(f: A => B)(implicit F: Monoid[B]): B

The other import functions in the trait Foldable are foldLeft and foldRight, as we know them from the standard collection. In scalaz only foldRight is abstract and foldLeft can be constructed in terms of foldRight.

Of course a Foldable has to follow laws again, this time it is required that the outcome of a foldLeft equals the foldMap, and a foldRight equals the foldMap as well.

Practical example

Using Foldable we can abstract away the List container from our previous example and write a sum function like:

    implicit class SumOps2[F[_] : Foldable, A : Monoid](fa : F[A])
    {
      val M = implicitly[Monoid[A]]
      val F = implicitly[Foldable[F]]
      def suml() = F.fold(fa)
    }

Given the frequency of problems were we need to reduce a number of values to a single result (forAll, exists, sum, …) it is evident that having the Foldable type class up one’s sleeves is a worthwhile tool. Combined with a sound Monoid for A we also get a default value for free.

For further articles in this series: TypeClass101