# Thing I Learned Today: Foldable

by Brian Shourd on **January 15, 2013**

It’s high time I explored this `Foldable`

typeclass in Haskell. It’s a typeclass for data structures that can be folded up, compressed down to a single value in a meaningful way. Start with a data type constructor `t`

, of kind `* -> *`

. The same kind of constructor required to be a `Functor`

or `Monad`

. Then we have the typeclass `Foldable`

, with methods

```
class Foldable t where
fold :: Monoid m => t m -> m
foldMap :: Monoid m => (a -> m) -> t a -> m
foldr :: (a -> b -> b) -> b -> t a -> b
foldr' :: (a -> b -> b) -> b -> t a -> b
foldl :: (a -> b -> a) -> a -> t b -
foldl' :: (a -> b -> a) -> a -> t b -> a
foldr1 :: (a -> a -> a) -> t a -> a
foldl1 :: (a -> a -> a) -> t a -> a
```

That’s a lot of methods! What do we need to define in order to create a minimum definition?

Only `foldMap`

or `foldr`

.

Really? That seems pretty amazing. In fact, it seems pretty astounding that we can get either of `foldMap`

or `foldr`

from the other. Let’s see how it’s done, then.

```
foldMap :: Monoid m => (a -> m) -> t a -> m
foldMap f = foldr (mappend . f) mempty
```

Ok, so if `foldr`

is defined, then we can use the monoid structure of `m`

to create `foldMap`

. Let’s look at an example: if `t`

is the type `[]`

and `m`

is also `[]`

, then `foldMap`

becomes

`foldMap f = foldr ((++) . f) []`

So

```
foldMap f [1,2,3,4] = foldr ((++) . f) [] [1,2,3,4]
= (f 1) ++ (f 2) ++ (f 3) ++ (f 4)
= concat [f 1, f 2, f 3, f 4]
= concat $ map f $ [1,2,3,4]
= concatMap f [1,2,3,4]
```

Ok, then, I see. But how is `foldr`

defined in terms of `foldMap`

, then?

```
foldr :: (a -> b -> b) -> b -> t a -> b
foldr f z t = appEndo (foldMap (Endo . f) t) z
```

What is this `Endo`

?

```
newtype Endo a = Endo { appEndo :: a -> a }
instance Monoid (Endo a) where
mempty = Endo id
(Endo f) `mappend` (Endo g) = Endo (f . g)
```

It’s just a type encoding the fact that endomorphisms create a monoid under composition of functions. That means that `Endo . f`

is of type `a -> Endo b`

. This actually makes great sense - when we `foldr`

, we use the function `f :: a -> (b -> b)`

to transform all of the objects in `t a`

to endomorphisms, then compose them according to `foldMap`

and apply them to the argument given.

Let’s get a bit more specific. The source for `Data.Foldable`

includes instances for both `Foldable Maybe`

and `Foldable []`

.

```
instance Foldable Maybe where
foldr _ z Nothing = z
foldr f z (Just x) = f x z
foldl _ z Nothing = z
foldl f z (Just x) = f z x
```

This is pretty straightforward. We define `foldr`

so that `Nothing`

always becomes the identity map, and then is applied to `z`

. If we don’t have `Nothing`

, then we have `Just x`

, so we get `f x z`

. We also define `foldl`

, presumably for speed, since it does exactly the same thing, only with a different argument order.

What, then, does `foldMap`

do when our type is `Maybe`

? Let’s try some examples:

```
foldMap :: Monoid m => (a -> m) -> t a -> m
foldMap f = foldr (mappend . f) mempty
foldMap f Nothing = foldr (mappend . f) mempty Nothing
= mempty
foldMap f (Just x) = foldr (mappend . f) mempty (Just x)
= mappend . f x $ mempty
= (f x) `mappend` mempty
= f x
```

With lists, we are familiar with how `foldr`

works, but let’s look at the implementation.

```
Instance Foldable [] where
foldr k z = go
where
go [] = z
go (y:ys) = y `k` go ys
```

This is (apparently) a common idiom in Haskell, using a function called `go`

to encapsulate the recursion.

Then `foldMap`

on lists becomes

```
foldMap f (x:xs) = foldr (mappend . f) mempty (x:xs)
= (mappend . f) x (foldr (mappend . f) mempty xs
= (f x) `mappend` foldMap f xs
```

We apply `f`

to every element of the list, and `mappend`

the results together. We could use this to, e.g. get the nth approximation of the power series of \(e^x = \sum_{i=0}^{\infty} \frac{x^n}{n!}\).

```
import Data.Monoid
import Data.Foldable
pSeries :: Double -> Int -> Double
pSeries x k = getSum $ foldMap f [0..k] where
f n = Sum (x^n / (fromIntegral $ Prelude.product [2..n]))
ghci> pSeries 0.5 10
1.6487212706873655
ghci> exp 0.5
1.6487212707001282
```

We could probably use it for something a lot less superficial, too.

That’s a quick look at the `Foldable`

type for today. I’ll have to take a look at the rest of the functions in `Data.Foldable`

another day.