*This is part 7 of a series on Implementing a (kinda) fantasy land compliant Maybe type. For part 1, go here, part 2 is here, part 3 can be found here, part 4 here, 5 is here and 6 is here*

Today is **Traversable** day, and I’m not going to lie to you, I’m still trying to grasp what **Traversable** is really supposed to do. But, like I said a while back, I learn better myself when I talk or write about things, so I hope we’ll all have a better understanding of what **Traversable** really does at the end of the day. Let’s go!

## Traversing. What is it good for.

To understand our journey, we’ll begin by understanding what traversing means:

to pass or move over, along, or through. to go to and fro over or along. to extend across or over.

Three different definitions, but they all share one thing: it’s about movement through different states. As for the spec:

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

>`u.traverse(A, f)`

Hold the phone there. This is the first time we see a lot of things, so let’s go over that type definition one piece at a time:

`traverse :: Applicative f, Traversable t =>`

➡ method name, and we have 2 type restrictions. We’ll see an`f`

that must have an instance of**Applicative**and a`t`

which must have an instance of**Traversable**.`t a ~>`

➡ This means our method is in the traversable`t`

that holds an`a`

of some type (no restrictions on`a`

).`(TypeRep f, ...)`

➡ We very briefly went over what**Type Representatives**where, but here we’re using one of them. Type representatives are what in**Haskell**we define as datatypes. In our case, it would be the**Maybe**object. And**Just / Nothing**are our type constructors, which are the actual types we work with. In this piece of code, we’re saying that our method will take a type representative of our**Applicative**`f`

as its first argument.`(... a -> f b)`

➡ This is our the second argument to our`traverse`

method, and it is a function which takes an`a`

of the same type inside of the**Traversable**we’re working on, and returns a`b`

of some other type (without restrictions) inside of the**Applicative**`f`

. So, one example of a function that does that, would be:`x => Just(x + 1)`

.`-> f (t b)`

➡ Finally, this is the return type of our method. It’s a`b`

, which is the same type as the function we pass as argument returns, inside of our**Traversable**`t`

, inside of our**Applicative**`f`

. Let’s assume we have an**Applicative**instance called**Left**. One example of a type that this function could return, would be:`Left(Just(1))`

.

That was a mouthful, but we’re getting there. Here are the rules this method (`u.traverse(A, f)`

) lives by:

`A`

must be the type representative of an**Applicative**`f`

is a function, which returns a value that must be of the type represented by`A`

.`traverse`

must return a value of the type represented by`A`

.

Armed with all of this, let’s look at what our implementations could look like.

## Start from Nothing

As usual, it makes more sense to start with the implementation for **Nothing**. Let’s look at the type signature again:

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

In this case, our `Traversable t`

will be **Nothing**. That means, that our result will be, an `f(Nothing)`

, because **Nothing** doesn’t hold any `a`

which we could apply a function to turn it into `b`

. That leaves us with one, and one implementation only possible for our **Nothing**.

`const Nothing = value => ({`

// …

traverse: (typeRepresentative, fn) => typeRepresentative.of(Nothing()),

// …

});

We know the `typeRepresentative`

argument must have an instance of **Applicative**. Which means it must have an `of`

function, so we can safely call `typeRepresentative.of`

and pass our **Nothing** as the value. What the type representative does with our **Nothing** is not our concern.

Now, for our **Just**, things get a bit messier. Let’s go, one step at a time, and return to our signature once more:

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

So, in this case, we have that `t`

is **Just**. So, we’re calling `traverse`

on a `Just(a)`

. Now, the return value must look something like: `Just(Traversable b)`

. And, we also see that the function returns an `f b`

, which is an **Applicative** of `b`

. Oh, and did I forget to mention that any instance of **Traversable** must also implement both **Foldable** and **Functor**? This is important, because we’re going to map over things. This is how our implementation looks like:

`const Just = value => ({`

// …

traverse: (typeRepresentative, fn) => fantasyMap(Just, fn(value)),

// …

});

What’s going on there? We’re mapping `Just`

, the function, to the result of applying the argument `fn`

to the value inside our instance of **Just**, the one we’re calling the method on. If we look at the type signature, we’ll see that that function must take an `a`

, which is the same type as what we have inside our `Traversable t`

and return an `f b`

, where `f`

is the **Applicative** instance that we passed the Type representative of. In our, just one algebra world (we only have **Maybe**), this is a test that represents what we pass around and get as a result:

`it("should return the result of mapping Just over the result of applying the function to the value inside the Just", () => {`

const expected = Just(Just(3));

const actual = Just(9).traverse(Maybe, x => Just(Math.sqrt(x)));

expect(actual.equals(expected)).toBe(true);

});

We take a `Just(9)`

, call its `traverse`

method passing first the type representative `Maybe`

and a function that takes a value `x`

and returns a `Just(Math.sqrt(x))`

. It could’ve just as well returned only `Just(x)`

, since that would’ve also satisfied the type signature. When we pass this, and we replace the values inside of our function implementation, we get this line:

`fantasyMap(Just, x => Just(Math.sqrt(x))(9))`

And, when we reduce the function, we get:

`fantasyMap(Just, Just(Math.sqrt(9))`

Which in turn is:

`fantasyMap(Just, Just(3))`

And if we look at the implementation of `fantasyMap`

, we find:

`const fantasyMap = (fn, value) => {`

if (typeof value.instances !== "undefined" && value.instances.includes("Functor")) return value.map(fn);

return fn(value);

};

So, since what we’re passing as `value`

is in fact an instance of `Functor`

, the result value will be calling that value’s `map`

method with the same function we passed in as argument. What that all means, is that eventually, we apply `Just`

to the `3`

inside of our `Just(3)`

, turning it into a `Just(3)`

. We then go back out, and re-wrap the result of the function in our original structure, which was a `Just`

, getting us a `Just(Just(3))`

at the end.

## Why?

In keeping up my part of the honesty deal: I don’t know yet. In being even more honest, I hadn’t even read the Haskellbook on **Traversable** yet before trying to implement this. That’s why I guided myself solely by the type signatures and eventually got somewhere.

Now, I’m sure some of you are wondering about the law… and yes, there are some laws. Unfortunately, I haven’t come up with a way to test those laws in our current setup, so I owe the confirmation of the laws to you. I’ll make up for it, I promise.

This brings us one convoluted step closer to our goal:

Setoid ✅

- Semigroup ✅
- Monoid ✅
- Functor ✅
- Apply ✅
- Applicative ✅
- Foldable ✅
- Traversable ✅
- Chain and Monad tomorrow!