# Days 15 and 16 - Foldables and Traversables

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!