# Fantas, Eel, and Specification 12: Traversable

08 May 2017It’s ** Traversable Monday™**, everyone! Granted,

*tomorrow*would have made for a catchier opening, but I wasn’t thinking this far ahead when I picked the day to release these. Still, I bet you can’t

*wait*for

`Monad`

s now! Putting all that aside, does everyone remember how great the `insideOut`

function from the `Applicative`

post was? Well, today’s post is all about your **new favourite typeclass**.

This little class comes with, hands down, the most *frightening* signature we’ve seen so far! Just *look* at this thing:

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

*Right*? Let’s break it down. We can take a `Traversable`

structure (whatever *that* means) with an inner `a`

type, use this `a -> f b`

function (where `f`

is some `Applicative`

), and we’ll land on `f (t b)`

. *Wait, what*?

The little bit of **magic** here is that, if we used the `a -> f b`

with `map`

, we’d end up with `t (f b)`

, right? The `f b`

replaces the `a`

in the `t a`

; nothing we haven’t seen before. **However**, with `traverse`

, the `f`

and `t`

come out **the other way round!**

In a **shocking** development, let’s see some examples *before* we trouble ourselves with the laws, as they’re a bit **intimidating**. Let’s say you have an `Array`

of `Int`

user IDs, and we need to do some **AJAX** for each one to get some details:

```
// getById :: Int -> Task e User
const getById = id => // Do some AJAX
```

Luckily, we have our wonderful `Task`

applicative to encapsulate the AJAX requests. We map over our `Array`

with `getById`

, and we end up with an `Array`

of `Task`

objects. **Neat**! However, whatever we’re doing with them, we probably want to do it on the *entire* `Array`

, so wouldn’t it be better to combine them into a single `Task e [User]`

? Well, our luck just continues, because we have our nifty little `insideOut`

:

```
// insideOut :: Applicative f
// => [f a] -> f [a]
const insideOut = (T, xs) => xs.reduce(
(acc, x) => lift2(append, x, acc),
T.of([]))
// paralleliseTaskArray
// :: [Int] -> Task e [User]
const paralleliseTaskArray = users =>
insideOut(Task, users.map(API.getById))
```

First we `map`

, then we `insideOut`

. Thanks to `Task`

’s `Applicative`

instance, we’ve successfully reached our goal! On top of *that*, the wonder of `Apply`

means all our AJAX will happen **in parallel**, with no extra effort!

Well, it turns out that there’s a name for `insideOut`

that encompasses more outer types than just `Array`

, and we call it `sequence`

! What’s more, a `map`

immediately followed by `sequence`

has a more common name: `traverse`

!

```
Array.prototype.traverse =
function (T, f) {
return this.reduce(
// Here's the map bit! vvvv
(acc, x) => lift2(append, f(x), acc),
T.of([]))
}
// Don't worry, though: `sequence` can also
// be written as a super-simple `traverse`!
const sequence = (T, xs) =>
xs.traverse(T, x => x)
```

So, whenever we see `map`

followed by `sequence`

, we can just use `traverse`

. Whenever all we want to do is **flip the types**, we can use `sequence`

.

I usually define`sequence`

and`traverse`

on my`Traversable`

types because they both get plenty of use.

Thinking about inner types, why stop with `Task`

? What if we use another `Applicative`

instead? Let’s play with `Either`

:

```
// toChar :: Int -> Either String Char
const toChar = n => n < 0 || n > 25
? Left(n + ' is out of bounds!')
: Right(String.fromCharCode(n + 65))
// Right(['A', 'B', 'C', 'D'])
;[0, 1, 2, 3].traverse(Either, toChar)
// Left('-2 is out of bounds!')
;[0, 15, 21, -2].traverse(Either, toChar)
```

By using `traverse`

with an inner type of `Either`

, we get back the first `Left`

if *any* of the values `map`

to a `Left`

! In other words, we get back the **first error**. Consider, for a minute, how **incredibly useful** this is for **form validation**.

What if we just want the successes, and to filter out the rest? We`map`

our function, then`map(map(x => [x]))`

to get all the`Right`

values into a singleton list, then`fold`

the list with the`Either`

semigroupstarting with`Right([])`

. I swear, I can’t get through a single post without mentioning some sort of fold!

In fact, why stop with `Array`

? We can define `Traversable`

instances for all sorts of things: `Maybe`

, `Either`

, `Pair`

, and even our `Tree`

from last time! What’s the *secret*, though?

A `Traversable`

type needs to know how to **rebuild itself**. It pulls itself apart, lifts each part into the `Applicative`

, and then puts itself back together. With the wonderful help of `of`

and `ap`

, it’s not hard to get all the pieces *into* the `Applicative`

, so the only trickery is the work on either side. *Luckily*, this is often very straightforward:

```
// Transform _2, then `map` in the _1!
Pair.prototype.traverse = function (_, f) {
return f(this._2).map(
x => Pair(this._1, x))
}
// Keep the nothing OR map in the Just!
Maybe.prototype.traverse = function (T, f) {
return this.cata({
Just: x => f(x).map(Maybe.Just),
Nothing: () => T.of(Maybe.Nothing)
})
}
// Lift all the bits, then rebuild!
Tree.prototype.traverse = function (T, f) {
return this.cata({
Node: (l, n, r) => lift3(
l => n => r =>
Tree.Node(l, n, r),
l.traverse(T, f),
f(n),
r.traverse(T, f))
Leaf: () => T.of(Tree.Leaf)
})
}
```

If you’ve been following the Reader/Writer/State series, we’ll actually be taking a look at the`Pair`

traversable in the finale!

If you can `map`

and `reduce`

your type (i.e. it’s a `Functor`

and a `Foldable`

), there’s a really good chance that it can be a `Traversable`

, too. Trust me: `Task`

’s `Applicative`

instance is *enough* reason to get excited about this!

`Task`

is also a good example of a type thatisn’t`Traversable`

, despite it having a similar structure to`Either`

. What’s the difference? Well, consider a`Task`

that returns a`Maybe`

to denote success. If wecouldtraverse`Task`

, we’d get back`Just`

a successful task, or`Nothing`

. See why this is impossible? We don’tknowwhether the`Task`

succeeds until we run it!

Before you get *too* excited and go all **super-villian** on me with your new-found **superpowers**, let’s end on **the laws**. *Brace yourselves*. We’ll start with **identity**, as it’s definitely the simplest:

```
u.traverse(F, F.of) === F.of(u)
```

If we take a `Traversable`

structure of type `T a`

, and *traverse* it with `F.of`

(which is `a -> F a`

for some `Applicative F`

), we’ll get back `F (T a)`

. **Map and turn inside-out**. What *this* law says is that we’d have ended up in the same place if we’d just called `F.of`

on the whole `T a`

structure. Squint a little, and ignore the `TypeRep`

: `U.traverse(F.of) === F.of(U)`

doesn’t look a million miles from `U.map(id) === id(U)`

(the identity law for `Functor`

), does it?

Next up is **naturality**, which is a bit of a mess in the spec, so let’s try to **clean it up**. Let’s imagine we have two `Applicative`

types, `F`

and `G`

, and some function `t :: F a -> G a`

, that does nothing but **change the Applicative**.

A function that transforms one

`Functor`

into anotherwithouttouching the inner value is called anatural transformation!

```
t(u.sequence(F)) === u.traverse(G, t)
```

So, we start with some `U (F a)`

-type thing, `sequence`

it, and land on `F (U a)`

. We then call `t`

on the result, and finally land on `G (u a)`

. **Naturality** says that we could just call `t`

directly in a `traverse`

and end up in the same place! I read this as saying, “*A traverse should behave the same way regardless of the inner Applicative*”; it doesn’t matter whether we do the transformation

**during**or

**after**.

This law is actually

impliedbyparametricity, which is a topic we might cover in the future. Basically, it means that the type signature of`traverse`

is restricted enough that this can’tnotbe true for any`Traversable`

that follows theother twolaws!

Last up is **composition**, and we’re going to need to introduce a type we haven’t seen before. `Compose`

is a way of combining two `Functor`

s into one (and even two `Applicative`

s into one!), and it goes a little something like this:

```
// Type Compose f g a = Compose (f (g a))
const Compose = (F, G) => {
const Compose_ = daggy.tagged('Compose', ['stack'])
// compose(F.of, G.of)
Compose_.of = x =>
Compose_(F.of(G.of(x)))
// Basically map(map(f))
Compose_.map = function (f) {
return Compose_(
this.stack.map(
x => x.map(f)
)
)
}
// Basically lift2(ap, this, fs)
Compose_.ap = function (fs) {
return Compose_(
this.stack
.map(x => f => x.ap(f))
.ap(fs.stack)
)
}
return Compose_
}
```

We’re not going to spend too much time on this type, so have a **couple of looks** to make sure you’re following. The key point here is that we’ve stacked two `Applicative`

s to form a **composite** `Applicative`

- how **amazing** is that? Even more excitingly, this rule generalises to **any number** of nested `Applicative`

s - they compose **completely mechanically**!

`Compose`

willalsobe an important part of the upcoming`State`

post, so don’t think we’ve seen the last of it!

Anyway, let’s get back to the point of introducing this type *here*. We’ll use `F`

and `G`

as our `Applicative`

placeholders again, and end up with the law below. The spec only uses `traverse`

, but this should make things a bit clearer:

```
const Comp = Compose(F, G)
// The type signature helps, I think:
// t (F (G a)) -> Compose F G (t a)
u.map(Comp).sequence(Comp) ===
Comp(u.sequence(F)
.map(x => x.sequence(G)))
```

This one’s the **ugliest** of the bunch! We start with some `u`

of type `t (F (G a))`

, where `t`

is `Traversable`

. On the **left-hand** side, we `map`

over this with `Comp`

and land on `t (Compose F G a)`

. Because `Compose F G`

is an `Applicative`

, we can turn this **inside out** and land on `Compose F G (t a)`

. Whew!

The **right-hand** side says we can `sequence`

the `t (F (G a))`

to get us to `F (t (G a))`

, then `map`

a `sequence`

over it to get us to `F (G (t a))`

. If we pass this into `Comp`

, we land on `Compose F G (t a)`

, and we **must land** on the **same result** as the left-hand side did!

This is a *really* dense law, but **just remember this**: we can either `Compose`

the `Applicative`

s **inside** the `Traversable`

and *then* `sequence`

, or `sequence`

and *then* `Compose`

. **It shouldn’t matter**. I read this as a kind of **re-inforcement** of **naturality**; not only should the `Traversable`

leave the `Applicative`

alone, but it should **respect Applicative composition**.

`Traversable`

has some *thorough* laws, but this is a **good thing**! The tighter the **restrictions**, the better we can **optimise** the instances we write: we’ve already had a *taste* of the power behind the `Traversable`

/ `Applicative`

relationship! *However*, there’s a problem that we still haven’t addressed:

We know we can do **parallel** computation with our `Applicative`

, but how do we do **serial** computation? How do we **compose** functions that return `Functor`

s? These questions, and others, will be solved **next week** when we cover `chain`

.

Until then, `traverse`

all the things! A Gist of this post’s motivating examples is available. `Array`

will, by far, be the one you use the most, but don’t be afraid to experiment. I look forward to your creations!

♥