# Foldable and Traversable

** 17 min read** • Published: **July 30, 2014**

Before we can get into the more advanced topics on Lenses, it is
important to really understand both `Foldable`

and `Traversable`

, which
is the motivation behind this article.

Let’s begin with `Foldable`

. `Foldable`

represents structures which can
be folded. What does that mean? Here are a few examples:

- Calculating the sum of a list.
- Calculating the product of a list.
- Folding a tree to get a maximum value.

We can describe a *fold* as ** taking a structure and reducing it to a
single result**. That’s also why some languages have a

`reduce`

function instead of a `fold`

, even though they mean the same thing.It is important to really understand the concept behind a fold in
general, not in terms of specific functions like `foldl`

or `foldr`

.
Whenever you see the word `fold`

in a function name, think *reducing a
larger structure to a single result*.

Now comes the time to take a look at the `Foldable`

type class.

```
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 :: (b -> a -> b) -> b -> t a -> b
foldl' :: (b -> a -> b) -> b -> t a -> b
foldr1 :: (a -> a -> a) -> t a -> a
foldl1 :: (a -> a -> a) -> t a -> a
```

We won’t go into detail on all of these, since `foldl`

, `foldr`

,
`foldl'`

, `foldr'`

, `foldl1`

and `foldr1`

work the same as their
counterparts from `Data.List`

.

What is interesting here is that `fold`

and `foldMap`

require the
elements of the `Foldable`

to be `Monoid`

s. Let’s just quickly take a
look at what a `Monoid`

is.

```
class Monoid a where
mempty :: a
mappend :: a -> a -> a
mconcat :: [a] -> a
```

Nothing really special here, `Monoid`

just simply defines a zero element
via `mempty`

and an associative operation `mappend`

for combining two
`Monoid`

s into one. `mconcat`

is just a convenience method which has a
default implementation using `mappend`

.

```
mconcat :: [a] -> a
mconcat = foldr mappend mempty
```

## fold and foldMap

The interesting thing about `fold`

and `foldMap`

is that they use a
`Monoid`

instead of a function to give us the final result. This might
not be obvious at first, but by picking the right `Monoid`

it is
essentialy the same as passing in a function, since it will just use the
`mappend`

defined for that `Monoid`

instance.

One very very very important aspect to understand here is that it is the
`fold`

function that requires the elements of `Foldable`

to have a
`Monoid`

instance, while `Foldable`

itself does not have that
restriction.

The result of this is that we can have something like `[Int]`

, where the
`[]`

is a `Foldable`

, but `Int`

is not a `Monoid`

, though as long as we
don’t use any of the functions from `Foldable`

that require a `Monoid`

we’ll be OK. Here’s an example

```
λ> foldr1 (+) [1,2,3,4]
10
λ> fold ["hello", "world"]
"helloworld" -- Strings are Monoids using concatenation
λ> fold [1,2,3,4]
<interactive>:1:1:
No instance for (Monoid a0) arising from a use of ‘it’
```

See how the problem only arises when we used `fold`

with `Int`

. We could
however wrap those `Int`

s in a `Monoid`

such as `Sum`

or `Product`

and
`fold`

them then.

```
λ> fold [Sum 1, Sum 2, Sum 3, Sum 4]
Sum {getSum = 10}
```

This might seem tedious at first, but remember our `Foldable`

type
class, as it also defines a function that is perfect for this particular
use case: `foldMap :: Monoid m => (a -> m) -> t a -> m`

. We can read
this as *Given a foldable containing things that aren’t Monoids, and a
function that can convert a single thing to a Monoid, I’ll give you back
a Monoid by traversing the foldable, converting everything to Monoids
and folding them together.*

Here’s our previous example, but now using `foldMap`

.

```
λ> foldMap Sum [1,2,3,4]
Sum {getSum = 10}
```

If you think about this for a little while we might even implement
`fold`

in terms of `foldMap`

. Why? When using `foldMap`

we need to
provide a way to convert each item to a `Monoid`

, but if those items
already are `Monoid`

s, we don’t need to do any conversion!

```
fold :: Monoid m => t m -> m
fold xs = foldMap id xs
```

Here’s the same in more steps.

```
λ> :t id
:: a -> a
λ> :t fold
:: (Monoid m, Foldable t) => t m -> m
λ> :t foldMap
:: (Monoid m, Foldable t) => (a -> m) -> t a -> m
λ> :t foldMap id
:: (Monoid m, Foldable t) => t m -> m
```

The actual `Foldable`

type class requires either `foldMap`

or `foldr`

,
but for the sake of this article we won’t be looking into `foldr`

.

## Traversable

Now that we have an understanding of `Foldable`

we can move on to
something more fun, `Traversable`

. `Traversable`

represents data
structures which can be traversed while perserving the shape. This is
why there is no `filter`

or `concatMap`

, since `Traversable`

only
defines a way to move through the data structure, but not a way to
change it.

```
class (Functor t, Foldable t) => Traversable t where
traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
sequenceA :: Applicative f => t (f a) -> f (t a)
```

If you look in the documentation for
`Traversable`

you might note that there is also `mapM`

and `sequence`

, but we won’t be
covering those in this article, since their implementation isn’t
interesting and can be done mechanically.

This might look a little intimidating at first, but don’t worry, we’ll
do this step by step by implementing a `Traversable`

instance for a
list.

```
instance Traversable [] where
traverse f xs = _
```

Since the implementation will be recursive we first need to define the
base case for our recursion, which will be the empty list. The type that
we’re looking for is `f [b]`

, but because the list we’re traversing is
empty, we just need to wrap it in the `Applicative`

context.

```
instance Traversable [] where
traverse _ [] = pure []
traverse f (x:xs) = _
```

Next goes the actual recursive implementaion. We have a function `f :: a -> f b`

and a head of the list which has the type `a`

. The only thing we
can do at this point is apply the function.

```
instance Traversable [] where
traverse _ [] = pure []
traverse f (x:xs) = f x
```

This won’t typecheck of course, because we’re returning `f b`

instead of
`f [b]`

. We could cheat here a little bit and just try to apply a some
function `f b -> f [b]`

to get the result. We can use `(:[])`

which has
a type of `a -> [a]`

and `fmap`

it on what we have.

```
instance Traversable [] where
traverse _ [] = pure []
traverse f (x:xs) = fmap (:[]) (f x)
```

Now we have an implementation that type checks, but it is still wrong,
since it doesn’t satisfy the rule that *a traversal must not change the
shape of the structure it is traversing*, and here we are just dropping
the rest of the list. We need to find a way to use recursion and somehow
combine the results.

By looking at the type of `traverse :: (a -> f b) -> t a -> f (t b)`

, or
in our case specifically `traverse :: (a -> f b) -> [a] -> f [b]`

we can
see that using `traverse`

recursively on the tail of the list would give
us the type we need.

```
instance Traversable [] where
traverse _ [] = pure []
traverse f (x:xs) = (f x) _ traverse f xs
```

Now we have two values, one of type `f b`

and one of type `f [b]`

, which
are basically the head and the tail of the list, both wrapped in an
`Applicative`

context. We also have a function `(:) :: a -> [a] -> [a]`

,
which concatenates a head and a tail together into a single list.

Knowing all of this it just comes down to a basic use of `Applicative`

where we have a function of two arguments and need to apply it to two
values in the `Applicative`

context. We can do this in two different
ways.

```
instance Traversable [] where
traverse _ [] = pure []
traverse f (x:xs) = (:) <$> f x <*> traverse f xs
```

And an alternative definition using `liftA2`

.

```
instance Traversable [] where
traverse _ [] = pure []
traverse f (x:xs) = liftA2 (:) (f x) (traverse f xs)
```

It should be pretty clear now that we need the `Applicative`

to be able
to actually implement `traverse`

. If all we had was a `Functor`

we
wouldn’t be able to combine the `f b`

and `f [b]`

together.

## sequenceA

Now that we have `traverse`

we can move on to define `sequenceA`

. Here’s
a specific type for our list instance.

`sequenceA :: Applicative f => [f a] -> f [a]`

If you’re familiar with `sequence :: Monad m => [m a] -> m [a]`

from
`Control.Monad`

then you can see how these two functions are doing the
same thing. It simply takes the `Applicative`

effects, runs them and
pulls them out of the list.

The implementation is really simple. Starting out with an empty list, we
just need to wrap it in the `Applicative`

context.

`sequenceA [] = pure []`

Next comes the actual recursive implementaiton. If we pattern match on
the head and the tail of the list, we’ll yet again get `f a`

and `[f a]`

.

`sequenceA (x:xs) = _`

We can call `sequenceA`

recursively on the tail to get `f [a]`

.

```
sequenceA [] = pure []
sequenceA (x:xs) = sequenceA xs
```

But of course this isn’t good enough. We need a way to combine the head
and the tail while they’re both wrapped in an `Applicative`

context.
This can be done in the same way as we did previously with `traverse`

,
using `(:)`

and the `Applicative`

functions `<$>`

and `<*>`

.

```
sequenceA [] = pure []
sequenceA (x:xs) = (:) <$> x <*> sequenceA xs
```

Or alternatively using `liftA2`

again.

```
sequenceA [] = pure []
sequenceA (x:xs) = liftA2 (:) x (sequenceA xs)
```

That’s it, we have a working implementation for `sequenceA`

.

## Implementing sequenceA with traverse and vice versa

If we now look at our implementations for `traverse`

and `sequenceA`

we
can definitely see some similarity there.

```
traverse _ [] = pure []
traverse f (x:xs) = (:) <$> f x <*> traverse f xs
sequenceA [] = pure []
sequenceA (x:xs) = (:) <$> x <*> sequenceA xs
```

The only difference is that `traverse`

takes a function and applies it
to the head of the list, while `sequenceA`

simply uses the head as it
is. Knowing this we can actually define `sequenceA`

using `traverse`

and
the `id`

function.

```
sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a)
sequenceA xs = traverse id xs
```

Could we do the same thing the other way around though? Yes! We most
certainly can define `traverse`

by using `sequenceA`

and the fact that
every `Traversable`

is also a `Functor`

. Let’s take this step by step.

```
traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)
traverse f xs = _
```

We only have one way of applying our function `a -> f b`

to the `t a`

and that is using `fmap`

, which would give us `t (f b)`

.

```
traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)
traverse f xs = _ $ fmap f xs
```

Now we’ll get an error saying that we need a function `t (f b) -> f (t b)`

, which is exactly what `sequenceA`

does!

```
traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)
traverse f xs = sequenceA $ fmap f xs
```

## Traversable with default implementations

Given the two implementations we just got we can rewrite our initial
`Traversable`

type class to use those as a default implementation for
both functions.

```
class (Functor t, Foldable t) => Traversable t where
traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
traverse f xs = sequenceA $ fmap f xs
sequenceA :: Applicative f => t (f a) -> f (t a)
sequenceA xs = traverse id xs
```

This is actually how it’s done in the `Data.Traversable`

module, except
that if you look at the source code you’ll see the functions defined in
point free style.

```
class (Functor t, Foldable t) => Traversable t where
traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
traverse f = sequenceA . fmap f
sequenceA :: Applicative f => t (f a) -> f (t a)
sequenceA = traverse id
```

## Default implementation for Functor and Foldable using Traversable

It might not be so obvious at first, but a `Traversable`

is a very
powerful concept. So powerful that it actually allows us to define both
`Functor`

and `Foldable`

if we have just a single function from
`Traversable`

. The `Data.Traversable`

module defines two functions,
`fmapDefault`

and `foldMapDefault`

, which can be used as an
implementation for `fmap`

and `foldMap`

if we so desire.

```
fmapDefault :: Traversable t => (a -> b) -> t a -> t b
foldMapDefault :: (Traversable t, Monoid m) => (a -> m) -> t a -> m
```

The way we’re going to implement these is very similar to what we did in the Lens introduction article. If this section is too hard for you to understand I recommend reading the Lens article first and then come back here. Everything will make a lot more sense.

Let’s first compare the types of `traverse`

and `fmap`

.

```
fmap :: Functor f => (a -> b) -> f a -> f b
traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)
```

The difference is that the function passed to `traverse`

returns a value
wrapped in `Applicative`

context, and the result is also wrapped. If we
could find a way to wrap the value after we apply the function, and then
unwrap it at the end, we would get exactly the same type as `fmap`

.

We can use the `Identity`

functor to do this, which defines a way to
unwrap it using `runIdentity :: Identity a -> a`

.

```
fmapDefault :: Traversable t => (a -> b) -> t a -> t b
fmapDefault f x = _
```

We don’t have that many options here. To be able to give the function
`f`

to a `traverse`

we need to change it’s type from `a -> f a`

. That’s
where `Identity`

comes in.

```
fmapDefault :: Traversable t => (a -> b) -> t a -> t b
fmapDefault f x = traverse (Identity . f) x
```

Now our types don’t align, since we are supposed to return `t b`

but we
are returning `Identity (t b)`

. The solution here is the above mentioned
`runIdentity`

which simply unwraps the value.

```
fmapDefault :: Traversable t => (a -> b) -> t a -> t b
fmapDefault f x = runIdentity $ traverse (Identity . f) x
```

And once more in point free style.

```
fmapDefault :: Traversable t => (a -> b) -> t a -> t b
fmapDefault f = runIdentity . traverse (Identity . f)
```

Compare this to the definition of `over`

and you can see how it *looks
and feels* almost exactly the same.

```
over :: Lens s a -> (a -> a) -> s -> s
over ln f = runIdentity . ln (Identity . f)
```

We’ll explain how this relates to Lenses in more detail in a followup
article, but for now let’s move on to `foldMapDefault`

.

## Implementing foldMapDefault

This part is very hard to understand, so be careful.

If we compare the type of `foldMapDefault`

with `traverse`

we can yet
again see some similarity.

```
foldMapDefault :: (Traversable t, Monoid m) => (a -> m) -> t a -> m
traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)
```

The difference from `fmapDefault`

is that now we need a way to convert
each element of the `Traversable`

to a `Monoid`

.

We will use the `Const`

applicative here, which as it so happens also
defines a `Monoid`

instance.

```
foldMapDefault :: (Traversable t, Monoid m) => (a -> m) -> t a -> m
foldMapDefault f x = _
```

As previously we can only use `traverse`

together with a function `a -> f b`

, but we have `a -> m`

, where by using `Const`

we can do the `m -> f b`

.

```
foldMapDefault :: (Traversable t, Monoid m) => (a -> m) -> t a -> m
foldMapDefault f x = traverse (Const . f) x
```

Again we’re faced with the problem of having `Const m (t b)`

instead of
`m`

, which can be solved using `getConst`

.

```
foldMapDefault :: (Traversable t, Monoid m) => (a -> m) -> t a -> m
foldMapDefault f x = getConst $ traverse (Const . f) x
```

And a point free version.

```
foldMapDefault :: (Traversable t, Monoid m) => (a -> m) -> t a -> m
foldMapDefault f = getConst . traverse (Const . f)
```

This is also very similar to one of the functions Lens provides, in
particular `view`

.

```
view :: Lens s a -> s -> a
view ln = getConst . ln Const
```

## Implementing Functor and Foldable with Traversable

Now that we understand how both `fmapDefault`

and `foldMapDefault`

work,
we can use them to define a `Functor`

and a `Foldable`

instance for any
`Traversable`

we might have.

We can test this out by defining a simple list type.

```
data List a = Nil
| Cons a (List a)
deriving Show
instance Functor List where
fmap = fmapDefault
instance Foldable List where
foldMap = foldMapDefault
instance Traversable List where
traverse _ Nil = pure Nil
traverse f (Cons x xs) = fmap Cons (f x) <*> traverse f xs
```

We used `fmap = fmapDefault`

and `foldMap = foldMapDefault`

to define
our `Functor`

and `Foldable`

instances, which is all made possible by
also having a `Traversable`

instance. Let’s test this out to make sure
it works!

```
λ> traverse (\x -> Just (x + 1)) (Cons 1 (Cons 2 (Cons 3 Nil)))
Just (Cons 2 (Cons 3 (Cons 4 Nil)))
λ> fold (Cons "hello" (Cons "world" Nil))
"helloworld"
λ> fmap (+1) (Cons 1 (Cons 2 (Cons 3 Nil)))
Cons 2 (Cons 3 (Cons 4 Nil))
```

It might be a surprising, but everything works as it is supposed to.

### Share on Twitter and Facebook

### Discussion of "Foldable and Traversable"

If you have any questions, feedback, or suggestions, please do share them in the comments! I'll try to answer each and every one. If something in the article wasn't clear don't be afraid to mention it. The goal of these articles is to be as informative as possible.

If you'd prefer to reach out to me via email, my address is loading ..