On fantasy, part 8

⏰ Takes about 7 minutes to read

This is the final part 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, part 6 is [here] (https://www.dabolivar.com/posts/day-91/) and the latest part 7 is here

The one before the last one

Today is the day we complete our Maybe 🎉. And in order to accomplish that, we have to give it 2 more instances:

  • Chain
  • Monad

And we’ll start with Chain.

Chaining

According to the spec, in order to implement Chain, we must also implement Apply. That’s already done! No, here are the other requirements:

chain :: Chain m => m a ~> (a -> m b) -> m b > m.chain(f)

This signature is less convoluted than the last one, so let’s try and read it in one go:

Chain is a method on a Chain of a that takes a function as argument and returns a Chain of b of the same type as that which it was called on.

And, it has some rules:

  • The function f must return a value of the same type as the value that the chain function is called on.
  • chain must return a value of the same type as the value it was called on.

With that in mind, let’s jump to our implementations.

Nothing is relatively straightforward. If we look at the signature, we know that the function must return the same type, so it must return a Maybe. Since it doesn’t make sense to return a Just from a Nothing in this case, we are left with just returning Nothing like:

const Nothing = value => ({
  // …
  chain: fn => Nothing(),
  // …
});

And, our Just implementation can also be built from the type signature. The function that chain takes as an argument must also return a Maybe. In that case, we don’t need to wrap the result in the Just we already have, so we’re left with an implementation that looks like this:

const Just = value => ({
  // …
  chain: fn => fn(value),
  // …
});

And that’s it! Chain has just one law that must be fulfilled, and it looks like this:

m.chain(f).chain(g) is equivalent to m.chain(x => f(x).chain(g)) (associativity)

And here’s how we test it:

const chainAssociativity = (f, g, m) =>
  m
    .chain(f)
    .chain(g)
    .equals(m.chain(x => f(x).chain(g)));

it("should fulfil the associativity property", () => {
  expect(jsc.checkForall(jsc.fn(maybeArb), jsc.fn(maybeArb), maybeArb, chainAssociativity)).toBe(true);
});
  • Chain ✅

And now, we’re only left with one algebra to implement: the Monad.

Monads

This is not a Monad blog post. There are plenty of those around, and to be honest, I’m not yet qualified to accurately explain or teach Monads. So, let’s just look at what Fantasy Land has to say about them:

A value that implements the Monad specification must also implement the Applicative and Chain specifications.

You know, when I got to this point and read that I assumed there must be something else. Turns out there’s not. That’s it. And in our case, it’s already done since we implemented both Applicative and Chain before.

We just have to test Monad’s laws to see if we did things right or not:

  • M.of(a).chain(f) is equivalent to f(a) (left identity)
  • m.chain(M.of) is equivalent to m (right identity)

Here’s how we test those:

const monadLeftIdentity = algebra => (f, a) => algebra.of(a).chain(f).equals(f(a));

const monadRightIdentity = algebra => (f, m) => m.chain(algebra.of).equals(m);

const maybeMonadLeft = monadLeftIdentity(Maybe);

const maybeMonadRight = monadRightIdentity(Maybe);

describe("Has an instance of Monad which", () => {
  it("should fulfil the left identity property", () => {
    expect(jsc.checkForall(jsc.fn(maybeArb), jsc.string, maybeMonadLeft)).toBe(true);
  });

  it("should fulfil the right identity property", () => {
    expect(jsc.checkForall(jsc.fn(maybeArb), maybeArb, maybeMonadRight)).toBe(true);
  });
});

And you know what was great about this? It worked! On the first try! It was very surprising to find out that we had already implemented a Monad without writing any more code.

Now, our instance is finally complete:

  • Setoid ✅
  • Semigroup ✅
  • Monoid ✅
  • Functor ✅
  • Apply ✅
  • Applicative ✅
  • Foldable ✅
  • Traversable ✅
  • Chain ✅
  • Monad ✅

And, here’s a Gist with the completed implementation: https://gist.github.com/ddanielbee/9eb478e93c213db7cabee85c18918747

Back to the beginning

In part 1 I wrote about the motivation for all of this. It was because Wolfram was curious how Maybe code looks, in comparison to Non-Maybe code. And I’ll show you that difference… tomorrow!