# Type Class 101: Foldable

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