I’m really starting to see the difficulties in completing the #100DaysOfCode challenge. After a whole day of working and slacking around, it’s really hard to get down to doing something or studying something. I feel like I need to make a few more adjustments to my schedule to make sure I have more time for it.

On the bright side, I got a Dragonite with 3050 CP in Pokemon Go.

But today’s post is about Foldables and Traversables.

## Foldables

If you’ve done any amount of Haskell or any FP language, or maybe even Javascript
and Python, you’ve probably heard about folding lists. In JS and Python, they
are also called `reduce`

. Folding a list basically involves applying a function
sequentially to a list’s items and accumulating the results, leaving us with a
single value in the end of it, which is the result of that fold.

In Haskell, folding a list looks like this:

The example above basically adds all the numbers in the list, leaving us with a single value, which is the sum of all the numbers in the list.

To break it down, folding a list basically reduces the list to a summary value
using the function provided to it. Now, if you think about this function, it has
to be a binary function taking two arguments. The `(+)`

function in the
example above is binary. Literally any function that’s passed to a fold has to
be binary, because after all it’s taking one accumulated value of previous results,
and an element of the list.

That’s similar to what monoids do. And in fact, we’ll see that as we generalize folds
to other structures, the folding operation is done with a function which is based
on the values’ `Monoid`

instance.

The typeclass that generalizes folding for all structures, not just lists, is `Foldable`

.
It’s definition is something like this:

The `MINIMAL`

annotation tells us that a minimal working instance of `Foldable`

must
define either `foldr`

or `foldMap`

in it.

For our purpose, we’ll only dwell upon `fold`

and `foldMap`

, since the other
functions work exactly like their counterparts from `Data.List`

.

Let’s first look at the type definitions of these two functions.

The `t`

in both the functions is our `Foldable`

structure. The `m`

in
the type definition has the constraint of being a `Monoid`

. In other words,
the value inside the foldable structure `t`

, has to be a monoid.

Let’s look at `fold`

. It takes a `t m`

, which we can break down as a structure
with monoidal value(s) inside it. It returns `m`

.

What `fold`

does is, it combines the monoidal values inside the `t`

structure
using that value’s `Monoid`

instance, more specifically, the `mappend`

function
for that value. Using `mappend`

, all the values are combined and we are left with
a single resulting value, which appears in our type definition as the last `m`

.

Let’s look at an example to see it better.

In the example above, the outer list is our `t`

structure. The strings in the list,
which themselves are basically `[Char]`

or lists themselves, are the `m`

values.

Now, list is a monoid. What’s the `mappend`

for lists? `concat`

. And that’s
exactly how the strings got joined in the output, by `concat`

enation.

As with the previous example, the list is our `t`

structure. This time our monoidal `m`

values are the `Sum`

values, for which the `mappend`

is addition. The result
therefore, is the addition of those values wrapped in `Sum`

.

One thing to note with this is that we can’t write `fold [1, 2, 3]`

, because
it’s not clear from it which `Monoid`

instance to use to fold the values, since
integers have more than one possible `Monoid`

instance. So we have to specify
the instance by using `Sum`

or `Product`

.

Let’s move on to `foldMap`

now, and if you’ve understood `fold`

, `foldMap`

is just one step further from it.

The first argument to `foldMap`

is a function that takes a value of any type `a`

and returns a monoid `m`

. The second is a structure `t`

that contains `a`

values
in it and the final result is a monoid `m`

.

The name and type definition of `foldMap`

pretty much gives everything away about
what it does. It applies a function that maps `a`

values to monoidal values, to
the values inside the `t`

structure, and then uses that monoid instance’s `mappend`

function to combine the values, leaving us with a single resulting `m`

.

Basically, if you have a `t`

structure with values inside it that are NOT monoids,
the `a -> m`

function, turns them into monoids, so at this point your `t a`

has become `t m`

. After that, the values are combined using that monoid’s `mappend`

,
which is what `fold`

does.

A perfect example here is something like:

It’s related to the last example for `fold`

. We want to fold a list of integers.
We can’t use `fold`

directly, because we know that integers can have more than
one possible monoid instance, so our fold wouldn’t know which one to use.

Now, what does `Sum`

do? Takes a value `a`

and returns it as the monoid `Sum a`

.

That is our `a -> m`

function from the type definition of `foldMap`

.

So in our example, the `Sum`

function is being applied to all the integer values
inside the list. This essentially gives us a list that looks like this: `[Sum 1, Sum 2, Sum 3]`

.
Now, that is a result that can be `fold`

ed, and using the `mappend`

for `Sum`

,
that list is folded and we get the result `Sum {getSum = 6}`

.

Similarly,

In this example, we’ve used the `Product`

monoid instead of `Sum`

, for which
the `mappend`

function is multiplication. So it uses multiplication to combine the
values inside the list.

## Traversables

Well, to be completely honest, I have a hard time explaining Traversables. In my mind,
I can say something like: A `Traversable`

allows us to apply a function inside a structure,
much like a `Functor`

does, but this function creates `Applicative`

structure
itself (so it has the type `a -> f b`

), and then lifts the resulting `Applicative`

structure(s) outside the `Traversable`

structure.

And I literally expect no one to understand that. That’s a definition that quite possibly, only I understand in my head. I will attempt of course, to explain it.

But first, let’s look at how the typeclass for `Traversable`

is defined in Haskell:

This was just a little bit intimidating to me when I first read it. Just a little bit. Like with most things Haskell, once you sit down and slowly break it apart, it usually tends to get clearer.

So, `Traversable`

has a class constraint of both `Functor`

and `Foldable`

.
So any `Traversable`

structure, must also be `Functor`

and `Foldable`

.

The `MINIMAL`

annotation here tells us that a minimum, working instance of `Traversable`

requires either the `traverse`

function or the `sequenceA`

function to be
defined for that instance. And as you can see, that’s because the default implementations
in the class for those two functions are in terms of each other. So defining one of
them gives us the other for free.

Now, let’s talk about the functions in `Traversable`

, starting with the easier to
understand, `sequenceA`

.

### sequenceA

Right off the bat, we can see that this function has a constraint, the `f`

in
the definition must be an `Applicative`

.

The rest of the type is fairly easy to resolve. The `t`

is obviously our `Traversable`

structure.

So, `t (f a)`

represents an `Applicative`

value, `f a`

, which is inside
our `t`

structure. Easy enough.

The result of `sequenceA`

is `f (t a)`

. To re-iterate, we give `sequenceA`

a value of `t (f a)`

and it returns us `f (t a)`

.

See what’s going on? It doesn’t do anything except for *switching* the two layers of `t`

and `f`

around `a`

. It doesn’t play with the value of `a`

either, it just
exchanges the two layers of `f`

and `t`

, pulling the `Applicative`

structure
outside the `Traversable`

structure. That’s literally all it does.

Now, for our example, you’re just going to have to accept for once what I say here.
And what I say is that, Lists have an instance of `Traversable`

. The implementation is
not important right now. Just know that Lists have a `Traversable`

instance, so
for our examples, lists are the `Traversable`

structure.

As explained above, you can see how the `Applicative`

structure, which is `Just`

in the example, has switched places with the list.

What happens if there’s a `Nothing`

value? Before we type out an example, let’s
just think about it for a bit. If we have a bunch of `Just`

values mixed with `Nothing`

in a list and we try to apply `sequenceA`

to it, the first thing that happens is
obviously the switching of structures, the `Applicative`

structures are pulled out.
But in this case, we’ll have two data constructors, `Just`

and `Nothing`

.
We’ll need to combine them, just like how `Applicative`

structures are combined,
which means combining `Just`

and `Nothing`

values will leave us with `Nothing`

.

And similarly, for `Either`

values:

### traverse

Now, let’s talk about `traverse`

, which has the following type:

Let’s start with a straight-forward explanation. The `f`

above has to be an `Applicative`

.
Our `traverse`

function takes two parameters, a function `a -> f b`

and a `Traversable`

structure `t a`

.

Now, the function `a -> f b`

creates more structure upon application. And obviously,
we are going to apply it over `t a`

, because that’s literally what we’ve been doing for
the last couple of blog posts. In other words, we are going to `fmap`

that function
over `t a`

(remember, `fmap`

is used to apply a function over a structure, doesn’t
matter if the function itself creates more structure).

So, if we apply `a -> f b`

to the `a`

inside `t a`

, what do we get?

We get `t (f b)`

. Check the type of the result now. It’s `f (t b)`

. What are
we missing from our current type after just applying `a -> f b`

inside our structure?
The structures haven’t been switched yet, the `Applicative`

structure needs to be
pulled out of the `Traversable`

structure. And once we do that, which we already
know how to (`sequenceA`

), we’ll get our result of `f (t a)`

.

I can already sense the gears turning on this one if you’ve read this far. But let’s
recap for once what `traverse`

does, in a very non-exciting way.

The function `traverse`

takes a function `a -> f b`

that creates more `Applicative`

structure on application. It also takes a `Traversable`

, `t a`

as its second argument.
The `a -> f b`

function is applied inside the `Traversable`

structure, giving us `t (f b)`

.
And finally, the `Applicative`

structure(s) inside the `Traversable`

is pulled
out of it, giving us `f (t b)`

. Example:

Above, `Just`

and `Right`

are the functions of type `a -> f b`

. They are
applied over the list to get `[Just 1, Just 2, Just 3]`

and `[Right 1, Right 2, Right 3]`

respectively. And then, if we pull the `Applicative`

structure out, which is `Just`

and `Right`

here, we get `Just [1, 2, 3]`

and `Right [1, 2, 3]`

.

We, of course, need to be careful about the `Applicative`

effects when pulling
out the structure. Such as the case with `Left`

, where due to how it’s combined
we have:

### The default implementations of traverse and sequenceA

If you see the `Traversable`

typeclass again, you’ll see that the typeclass has default
implementations for both `traverse`

and `sequenceA`

. They are both defined in
terms of the other and we’ll see how that’s so in this section.

Let’s start with `traverse`

. The default implementation for `traverse`

goes like
this:

Now, if you’ve read the last section, this probably already makes too much sense, but in case it doesn’t, let’s break it down.

What does `traverse`

do? It first applies a function `a -> f b`

over `t a`

.
Wait, that’s `fmap`

isn’t it? `fmap`

takes a function and applies it over a
structure, and that’s exactly what we are doing for the first part of `traverse`

.
So if we `fmap`

the function `a -> f b`

over `t a`

, we get `t (f b)`

.
After that, we need to pull the `Applicative`

layer out. How do we do that?
By using `sequenceA`

.

So, essentially, `traverse`

is just `fmap`

combined with `sequenceA`

.

Next, let’s come to the default implementation of `sequenceA`

. What does `sequenceA`

do? It takes a `Traversable`

structure with an `Applicative`

inside it, `t (f a)`

,
and pulls out the `Applicative`

layer out of it, effectively switching the structures
around, to give us `f (t a)`

.

Now, we know that we have to define `sequenceA`

using `traverse`

. How do we do
that? As we saw above, `traverse`

is `sequenceA`

composed with `fmap`

.
Well, if we could just make sure that the `fmap`

part of `traverse`

didn’t make any change to the structure inside the `Traversable`

, then we are
just left with `sequenceA`

, where the `Applicative`

structure is pulled out.

Well, what function, when used with `fmap`

doesn’t make any changes? `id`

of course!
If we reason about it this way, if we `fmap`

the `id`

function over `t (f a)`

,
we get just `t (f a)`

, and the rest of `traverse`

is just switching structures,
which is `sequenceA`

. This gives us the following implementation of `sequenceA`

in terms of `traverse`

:

That is the default implementation for `sequenceA`

in the `Traversable`

typeclass
in terms of `traverse`

.

## Conclusion

I guess I should wrap up here. We looked over the `Traversable`

typeclass,
explored lightly the functions inside it, namely `sequenceA`

and `traverse`

,
and dug out their default implementations. There’s a lot more that can be covered
regarding these topics, such as implementations of different instances and such,
however, this blog post will not be covering it.

The Haskell Book that I’ve been reading covers quite a lot of those topics and you should definitely buy it if you plan to start on Haskell.

I’d like to end the blog post by referring to another blog post on Foldables and Traversables, which was referenced in the mentioned book above, and which gave me a lot of valuable insights into this topic. I HIGHLY recommend readers to go through that post for better understanding of these typeclasses. CLICK HERE FOR POST

As always, good luck to everyone on their #100DaysOfCode and happy coding!

comments powered by Disqus