Day 78; on Algebras, part 5

⏰ Takes about 8 minutes to read

This post is part 5 of a series on Algebras in Software Development. Here are part 1, part 2, part 3 and part 5

Yesterday, we listed the 2 laws that must hold true for any Functor and wrote a very simple JS implementation of a very popular Functor called Maybe. Today will be all about proving that those laws actually do hold true. For simplicity’s sake, here are the laws again:

  • Identity ➡ If the function you pass to fmap is the identity function, then fmap id functor === id functor. So, the identity function is a functor’s Identity value.
  • Composition ➡ fMapping multiple times with different functions will yield the same result as fMapping once with a function that is a composition of the multiple ones (in the same order, of course).

And here’s the implementation we’ll be working on today:

// Maybe Functor

const Nothing = () => ({
  fmap: fn => Nothing(),
  inspect: () => "Nothing",
  toString: () => "Nothing",
});

const Just = x => ({
  fmap: fn => Just(fn(x)),
  inspect: () => `Just(${x})`,
  toString: () => `Just(${x})`,
});

Lawfulness

There are a couple ways we can test this. The first one is to just check it by hand in an unit test, something like:

// […] Using Jest

describe("Law abidding Maybe Functor", () => {
  const id = x => x;
  it("fulfils identity", () => {
    const expected = Just(1);
    const actual = Just(1).fmap(id);
    expect(actual).toEqual(expected);
  });
});

But that’s boring. Also, it shows us that the law holds for Just, but not for Nothing. So we would have to write a new test for Nothing. And then, we’re only making sure it holds for a Just of 1 and… you get the idea.

Properties galore

A while back, I wrote a bit about Property Based Testing. I won’t go into a lot of detail about it here because I’m planning to run a series on it in the future (next week), so just believe me for now when I tell you that a type of testing that has the word Property in its name is perfect for testing Properties.

My first stop when trying to figure out how to do Property Based Testing in JS was this post from HC Labs. In there, Stefan shows a couple different libraries and how they work. I chose to use jsverify because it seemed to be the most robust one, even if it has the most esoteric documentation I’ve ever seen.

Whenever we’re testing properties, there are 3 steps to follow.

  • The first step is defining which things our property can work on, meaning, what type of input can it receive. In our case, it’s a Maybe functor with any type of value inside, but since any type of value gets hard quickly, let’s assume integers. So, we can get either Nothing(integer) or Just(integer) as inputs for our identity property.
  • The second step is writing a way for our framework to generate random values of the type we need. Jsverify is rather good at this and has multiple ways of accomplishing it. In my case, here's what I ended up with after skimming through the docs for a while:
const jsc = require("jsverify");

const arbitraryMaybe = jsc.bless({
  generator: () => {
    switch (jsc.random(0, 1)) {
      case 0:
        return Nothing(jsc.integer);
      case 1:
        return Just(jsc.integer);
    }
  },
});

There’s a lot happening there, but what’s important for us right now is that this function tells jsverify to randomly build values that are either a Nothing or a Just with a random integer value inside. Now, the third and last step is:

  • Write a function that tests your property. For our identity property, it’s this:
const id = x => x;

const functorIdentity = f => f.fmap(id).toString() === f.toString();
// toString used here as a workaround to not having native deep equal in JS.

With that, we’re set! We can replace our unit tests with property based tests like the following:

// […]

describe("Law abidding Maybe Functor", () => {
  const id = x => x;
  it("fulfils identity", () => {
    expect(jsc.checkForall(arbitraryMaybe, functorIdentity)).toBe(true);
  });
});

That’s all. Jsverify will run our function 100 times, using random values, as defined by our generator function above and return true only if all 100 tests passed our property function. If not, we’ll get an error message with what case made it fail and what the result was in that case. With this, we can be more certain that our Functor implementation holds true to its laws, and honestly, I think it’s as close to mathematical certainty as you can get.

If this looks weird, it’s because its very unfamiliar. Property Based Testing is not widely used in JS and the syntax / conventions can look really weird if one hasn’t seen it in other languages before. Nevertheless I think it’s an useful addition to our testing tool belt. That’s why I’ll devote most of next week to write about it, specifically in JS.

And if you’re curious about how this all looks together, here’s a Gist with all the code (and also a test for the other property 🦄).