On fantasy, part 5

⏰ Takes about 14 minutes to read

This is part 5 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 and 4 here

Our Maybe is growing a lot. So far, we’ve implemented instances of:

  • Semigroup (adds concat)
  • Monoid (adds empty on the type representative )
  • Functor (adds map)
  • Apply (adds ap)

Next one on the list is Applicative. But, before we get there, there was one thing bugging me a lot as I got here, and that was that I had no proper way of checking my values for equality. Now, this is a problem for Javascript the language in itself (look here), but that can’t stop us! In fact, one of the algebras defined in the fantasy-land spec provides us with exactly what we want.

Enter the Setoid

Here’s what the spec has to say:

equals :: Setoid a => a ~> a -> Boolean

So, it’s a method called equals on an object with an instance of Setoid that receives one parameter and returns a boolean. Sort of like this: setoid.equals(b) and there’s just one rule: b must be of the same Setoid instance. So, in our case, our Maybe has to be able to know if it’s equal to another Maybe. So, here are the test cases we need to cover in plain English:

  • A Nothing is equal to another Maybe if the other Maybe is also a Nothing.
  • A Nothing is not equal to another Maybe if the other Maybe is a Just.
  • A Just is not equal to another Maybe if that Maybe is a Nothing.
  • A Just is equal to another Maybe if that Maybe is a Just and the values inside each of them are also equal to one another.

And, here are our tests for that:

it("should return true for 2 Nothing", () => {
  const actual = Nothing().equals(Nothing());
  expect(actual).toBe(true);
});
it("should return false for 1 Nothing and 1 Just", () => {
  const actual = Nothing().equals(Just(1));
  expect(actual).toBe(false);
});
it("should return false for 1 Just and 1 Nothing", () => {
  const actual = Just(1).equals(Nothing());
  expect(actual).toBe(false);
});
it("should return true for 2 Just with the same value inside", () => {
  const actual = Just(1).equals(Just(1));
  expect(actual).toBe(true);
});

And, like we did in map, it makes sense here to also defer the responsibility to a helper function that will work for any possible Setoid in the future. Here’s how that looks:

const sameType = (x, y) =>
  typeof x === typeof y &&
  typeof x.constructor !== "undefined" &&
  typeof y.constructor !== "undefined" &&
  x.constructor.typeRepresentation === y.constructor.typeRepresentation;

const fantasyEquals = (x, y) => {
  if (!sameType(x, y)) return false;
  if (
    typeof x.constructor.typeRepresentation !== "undefined" &&
    typeof y.constructor.typeRepresentation !== "undefined" &&
    x.constructor.typeRepresentation === y.constructor.typeRepresentation
  )
    return fantasyEquals(x.value(), y.value());
  return x === y;
};

const Nothing = value => ({
  // …
  equals: other => other.isNothing(),
  // …
});

const Just = value => ({
  // …
  equals: other => (other.isNothing() ? false : fantasyEquals(Just(value), other)),
  // …
});

We ask first if both arguments the function received are of the same type, following our type conventions. If they are, then we check if they are also algebras of the same type, and if so we re-iterate on the inner values. Our goal with this function is to eventually reach a primitive value inside of our Setoid that we can directly compare for equality, which is what happens on the last line with x === y. Note: I’m aware this function fails for equal arrays and equal objects in JS, but I didn’t want to complicate it too much for the post. The final version in the GitHub repo does contain a naive equality check for these kind of structures.

There are also a couple laws to test in here:

it("should return true for 2 Nothing", () => {
  const actual = Nothing().equals(Nothing());
  expect(actual).toBe(true);
});
it("should return false for 1 Nothing and 1 Just", () => {
  const actual = Nothing().equals(Just(1));
  expect(actual).toBe(false);
});
it("should return false for 1 Just and 1 Nothing", () => {
  const actual = Just(1).equals(Nothing());
  expect(actual).toBe(false);
});
it("should return true for 2 Just with the same value inside", () => {
  const actual = Just(1).equals(Just(1));
  expect(actual).toBe(true);
});

And, like we did in map, it makes sense here to also defer the responsibility to a helper function that will work for any possible Setoid in the future. Here’s how that looks:

const reflexivity = a => a.equals(a) === true;

const symmetry = (a, b) => a.equals(b) === b.equals(a);

it("should fulfil the law of reflexivity", () => {
  expect(jsc.checkForall(maybeArb, reflexivity)).toBe(true);
});
it("should fulfil the law of symmetry", () => {
  expect(jsc.checkForall(maybeArb, maybeArb, symmetry)).toBe(true);
});

That’s it for the detour, but the cool thing is that we can now more accurately test our implementations against equality.

Applicativeness

According to the spec, there’s just one small looking thing we should do here:

of :: Applicative f => a -> f a > F.of(a)

With a couple rules:

  • Any Applicative must also have an instance of Apply ✅
  • This method is on the type representative, not on the type constructors. In our case, that means it’s on Maybe and not on our Just / Nothing functions.
  • It should return a value of the same Applicative. So, our Maybe.of function, should take one argument a of any type, and return a Maybe.
  • No parts of a should be checked. This is the one that makes us think a bit.

When I saw this for the first time, my first assumption was to build a function that checked wether the value a “existed” as in wasn’t undefined or null and return a Nothing if it did not exist, or a Just of it if it did exist. But then I read the last rule: No parts of a should be checked. If that’s the case, then we have no way of knowing wether it makes sense to return a Nothing or a Just. That leaves us with just one option, which is always returning a Just of the value that gets passed along.

So, here’s how our function looks like on our Maybe type representative.

const Maybe = {
  empty: () => Nothing(),
  of: value => Just(value),
  typeRepresentation: "Maybe",
};

It may look simple, but remember how my first reflex was to do something completely wrong. And, like with all of our algebras, there are some laws that need to be checked:

const applicativeIdentity = algebra => x => algebra.of(x).ap(algebra.of(id)).equals(algebra.of(x));

const applicativeHomomorphism = algebra => (f, x) =>
  algebra
    .of(x)
    .ap(algebra.of(f))
    .equals(algebra.of(f(x)));

const applicativeInterchange = algebra => (u, y) =>
  algebra
    .of(y)
    .ap(u)
    .equals(u.ap(algebra.of(f => f(y))));

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

it("should fulfil the homomorphism property", () => {
  expect(jsc.checkForall(jsc.fn(jsc.string), jsc.string, applicativeHomomorphism(Maybe))).toBe(true);
});

it("should fulfil the interchange property", () => {
  expect(jsc.checkForall(maybeFnArb, jsc.string, applicativeInterchange(Maybe))).toBe(true);
});

So far so good, right?

  • Setoid ✅
  • Semigroup ✅
  • Monoid ✅
  • Functor ✅
  • Apply ✅
  • Applicative ✅

So far we’ve implemented 6 instances, and now we have only 4 algebras left to go! Those are:

  • Foldable coming up next!
  • Traversable
  • Chain
  • Monad

This means, we’ll get a minimum of 3 more posts on this series, which started out as something quick to take care of in a couple hours and grew a bit out of proportion. But hasn’t stopped being fun.