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:

foldr (+) 0 [1..10] -- Output: 55  |  adds all the numbers in the list

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:

class Foldable t where
    {-# MINIMAL foldMap | foldr #-}
    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

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.

fold :: Monoid m => t m -> m
foldMap :: Monoid m => (a -> m) -> t a -> m

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.

fold ["omg", "wtf", "lol"] -- "omgwtflol"

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 concatenation.

fold [Sum 1, Sum 2, Sum 3] -- Sum {getSum = 6}

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.

foldMap :: Monoid m => (a -> m) -> t a -> m

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:

foldMap Sum [1, 2, 3] -- Sum {getSum = 6}

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.

Sum :: a -> 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 folded, and using the mappend for Sum, that list is folded and we get the result Sum {getSum = 6}.

Similarly,

foldMap Product [1, 2, 3, 4] -- Product {getProduct = 24}

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:

class (Functor t, Foldable t) => Traversable t where
    {-# MINIMAL traverse | sequenceA #-}
    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

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

sequenceA :: Applicative f => t (f a) -> f (t a)

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.

sequenceA [Just 1, Just 2, Just 3] -- Just [1, 2, 3]

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.

sequenceA [Just 1, Just 2, Just 3, Nothing] -- Nothing

And similarly, for Either values:

sequenceA [Right 1, Right 2, Right 3] -- Right [1, 2, 3]
sequenceA [Right 1, Right 2, Left 3] -- Left 3

traverse

Now, let’s talk about traverse, which has the following type:

traverse :: Applicative f => (a -> f b) -> t a -> f (t b)

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:

traverse Just [1, 2, 3] -- Just [1, 2, 3]
traverse Right [1, 2, 3] -- Right [1, 2, 3]

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:

traverse Left [1, 2, 3] -- Left 1

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:

traverse f = sequenceA . fmap f

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.

traverse Just [1, 2, 3] -- Just [1, 2, 3]
sequenceA $ fmap Just [1, 2, 3] -- Just [1, 2, 3]

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:

sequenceA = traverse id

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