On fantasy, part 2

⏰ Takes about 12 minutes to read

This is part 2 of a series on Implementing a (kinda) fantasy land compliant Maybe type. For part 1, go here

Last time we ended with three TODOS on our quest to implement a Maybe type. Those were:

  • How should the concat function work on booleans?
  • How should it work on objects?
  • Test the law of associativity ➡ a.concat(b).concat(c) is equivalent to a.concat(b.concat(c))

The first few questions are relatively straight forward. In the first case, after careful examination I decided that it’s impossible (or at least irresponsible) to define a standard way on how booleans can be concatenated. The reason is, that we can have more than 1 way of concatenating them that will fulfil the law of associativity, as follows:

  • boolean1 && boolean2 and boolean1 || boolean2 both work as concatenation, and they also both fulfil the law of associativity. Choosing one over the other would be confusing, so we’d rather not choose.

As I was pondering this, I realized I had committed the same crime in the last implementation: I decided that concat on numbers would be the sum of numbers. But it could also be the multiplication of numbers. So, I removed that one as well.

As for how it should work on objects, there’s already an implementation of concatenation in the native Javascript spec in Object.assign({}, obj1, obj2). So, I went with that one. In the end, our fantasyConcat implementation looks like this:

const fantasyConcat = (semiOne, semiTwo) => {
  if (
    semiOne.instances &&
    semiTwo.instances &&
    semiOne.instances.includes("Semigroup") &&
    semiTwo.instances.includes("Semigroup")
  )
    return semiOne.concat(semiTwo);
  if (Array.isArray(semiOne) && Array.isArray(semiTwo)) return semiOne.concat(semiTwo);
  if (typeof semiOne === "string" && typeof semiTwo === "string") return `${semiOne}${semiTwo}`;
  if (typeof semiOne === "object" && typeof semiTwo === "object") return Object.assign({}, semiOne, semiTwo);
  throw new Error("Not instances of semigroup, or concatenable primitives!");
};

So, if our values are instance of Semigroup, we defer the concatenation to them. Eventually we’ll reach one of our concatenable types, or it’ll blow up, which is what we want in this case.

As for testing the law:

Properties, all of the properties

A while back I spoke at large on property based testing, so I won’t go into a lot of detail about the syntax presented here. If you want to refresh on that a bit, or this is the first time you’ve heard of it, you can find more info here.

So, first let’s define the function that will test our law. My first attempt looked like this:

const associativity = (a, b, c) => a.concat(b).concat(c).toString() === a.concat(b).concat(c).toString();

But, that didn’t work. I thought at first that I could just tell jsverify to pass Maybe(randomString) as arguments because that sounds intuitive, right? Well, no. I don’t know what happens internally in jsverify but the arbitrary values it creates do not get evaluated if used like this. So, you have a Maybe(jsc.string) and a jsc.string is an object, so it doesn’t have a typeof string. Meaning our concat function broke 😢. That’s ok though, because after forcing the issue a bit, I came up with this:

const associativity = algebra => (a, b, c) =>
  algebra.of(a).concat(algebra.of(b)).concat(algebra.of(c)).toString() ===
  algebra
    .of(a)
    .concat(algebra.of(b).concat(algebra.of(c)))
    .toString();

Which does work, because we defer the instantiation of the algebras to the actual function. At this point, a, b & c are already random somethings, so this works beautifully. There’s also another change here that will be apparent once we get to the next algebra our Maybe needs to have an instance of.

So, here’s how our Property based test looks like:

const maybeAssociativity = associativity(Maybe); // partial application to have our algebra available.

// Creation of arbitrary strings and undefined so we get both Nothing and Just in the mix. More Just than Nothing though.
const arbitraryMaybeString = jsc.bless({
  generator: () => {
    switch (jsc.random(0, 2)) {
      case 0:
        return undefined;
      case 1:
        return jsc.string;
      case 2:
        return jsc.string;
    }
  },
});

it("should fulfil the law of associativity", () => {
  expect(jsc.checkForall(arbitraryMaybeString, arbitraryMaybeString, arbitraryMaybeString, maybeAssociativity)).toBe(
    true
  );
});

Success! This works because the maybeAssociativity function is expecting any type of primitive value at this point. It already knows it’ll wrap them in Maybe but that’s not relevant to the creation of the randomized inputs.

At this point, we have a working, fantasy-land compliant (kind of) Semigroup instance on our Maybe type. How awesome is that?

  • Semigroup ✅
  • Coming up next: Monoid

Monoid fun

After all the excitement that was implementing our Semigroup instance, Monoids are a bit quieter. Here’s what the spec says:

A value which has a Monoid must provide an empty function on its type representative

Huh, what’s a type representative then? We hadn’t seen that before. Turns out, the type representative is what we mostly know as the data type. In our case, it would be the Maybe object. And the Nothing and Just functions are data constructors. So, we need to provide a empty function on our Maybe object. And, that means it needs to fulfil 2 laws:

  • m.concat(M.empty()) is equivalent to m (right identity)
  • M.empty().concat(m) is equivalent to m (left identity)

Remember the tests we had for our Semigroup instance? Well, a couple of them were:

it("should return its argument if called on a Nothing", () => {
  const expected = "Just(1)";
  const actual = Nothing().concat(Just(1)).toString();
  expect(actual).toBe(expected);
});

it("should return itself if called on a Just with a Nothing as parameter", () => {
  const expected = "Just(1)";
  const actual = Just(1).concat(Nothing()).toString();
  expect(actual).toBe(expected);
});

That sounds mighty familiar. So, Just(1).concat(Nothing()) === Just(1). And Nothing().concat(Just(1)) === Just(1). Replace Just(1) with m and you get the exact definitions for the left/right identity laws. That means, our Maybe’s empty is Nothing! Armed with that knowledge, let’s change our Maybe implementation a bit:

const Maybe = {
  empty: () => Nothing(),
  of: value => (typeof value === "undefined" || value === null ? Nothing() : Just(value)),
};

And we’re done! … is what I would like to say. But we still haven’t properly checked the laws. You already know the drill. Here’s how the functions for checking our laws look like:

const rightIdentity = algebra => m => algebra.of(m).concat(algebra.empty()).toString() === algebra.of(m).toString();

const leftIdentity = algebra => m => algebra.empty().concat(algebra.of(m)).toString() === algebra.of(m).toString();

And here’s how the tests look like:

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

it("should fulfil the left identity property", () => {
  expect(jsc.checkForall(arbitraryMaybeString, maybeLeftIdentity)).toBe(true);
});

This passes. So you know what that means:

  • Semigroup ✅
  • Monoid ✅
  • Coming up next: Functor

Our Maybe implementation is coming along nicely. In the following days I will complete it with all the instances we set out to fulfil. And, if you’re feeling particularly curious, and the project has gotten a bit bigger than it was last time, here’s the git repo where I’ll work on it.

Until the next time! 🦄