On fantasy, part 7

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!