On fantasy, part 3

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

Last time, we finished our Semigroup instance on our Maybe implementation, and gave it also a Monoid instance. Today, we’ll focus on another algebra, namely the Functor.

Map all the things

The Functor specification contains just one method: map, which looks like this:

map :: Functor f => f a ~> (a -> b) -> f b

And what that means, is that it’s a method on every Functor instance that takes one argument which must be a function and returns a Functor of the same type. And if that sounds familiar, it’s because javascript’s Array implements a map function that works like this!

In our case, we have two possibilities: either we map on a Nothing or on a Just with something inside. For the first case, my assumption is that, mapping over Nothing should yield also Nothing. So, our first test and the code that makes it pass:

it("should return Nothing if called on a Nothing", () => {
  const expected = Nothing().toString();
  const actual = Nothing().map(Math.sqrt).toString();
  expect(actual).toBe(expected);
});

const Nothing = value => ({
  value: () => Nothing(),
  isNothing: () => true,
  isJust: () => false,
  concat: other => other,
  map: fn => Nothing(),
  toString: () => "Nothing",
  inspect: () => "Nothing",
  instances: ["Semigroup", "Monoid"],
});

So Nothing().map(fn) will always return Nothing. For our second case, we need to apply the function to what we have inside, and then re-wrap it in our Just. A first test (and implementation) would be:

it("should return the result of applying the function over the value if it's not an object or array", () => {
  const expected = Just(3).toString();
  const actual = Just(9)
    .map(Math.sqrt)
    .toString();
  expect(actual).toBe(expected);
});

const Just = value => ({
  value: () => value,
  isNothing: () => false,
  isJust: () => true,
  concat: other => {
    if (other.isNothing()) return Just(value);
    return Just(fantasyConcat(value, other.value()));
  },
  map: fn => return Just(fn (value)),
  toString: () => `Just(${value})`,
  inspect: () => `Just(${value})`,
  instances: ["Semigroup", "Monoid"]
});

That makes the test pass. But remember how we said Array has a map function? We could take advantage of that, since we know already how Arrays are supposed to get mapped over, or at least what a very canonical implementation of mapping over a List like structure looks like. And we can extend such an implementation to also work on Objects if we like. So, we abstract our mapping behaviour in a helper function and use it inside every instance of Functor we write:

const fantasyMap = (fn, value) => {
  if (Array.isArray(value)) return value.map(fn);
  if (typeof value === "object")
    return Object.keys(value).reduce((acc, cur) => {
      acc[cur] = fn(value[cur]);
      return acc;
    }, {});
  return fn(value);
};

// And our Just turns into:

const Just = value => ({
  value: () => value,
  isNothing: () => false,
  isJust: () => true,
  concat: other => {
    if (other.isNothing()) return Just(value);
    return Just(fantasyConcat(value, other.value()));
  },
  map: fn => Just(fantasyMap(fn, value)),
  toString: () => `Just(${value})`,
  inspect: () => `Just(${value})`,
  instances: ["Semigroup", "Monoid"],
});

Now, we either map over arrays, objects or just any old plain value that isn’t either of those.

There’s just one more step to complete our instance of Functor, and that is testing the law. Functor’s map fulfils 2 laws:

• u.map(a => a) is equivalent to u (identity)
• u.map(x => f(g(x))) is equivalent to u.map(g).map(f) (composition)

And here’s how we write our tests for them:

const jsc = require("jsverify");

// Laws
const identity = x => x.map(y => y).toString() === x.toString();

const composition = (f, g, x) => x.map(compose(f, g)).toString() === x.map(g).map(f).toString();

// Note: Better way to write arbitraries for our algebras. I think.

const maybeArb = jsc.string.smap(
  Just,
  x => x.value(),
  y => y.toString()
);

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

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

Note: I found a better way to write arbitraries for our algebras, yay! How it works is something I don’t quite comprehend yet. But as soon as I do, I’ll write about it.

And with that, we’re done! Our Maybe implementation now has a Functor instance! We’re just getting started though, we still have 4 more algebra instances to give our Maybe so it doesn’t get picked on by the other Maybes out there.

• Semigroup ✅
• Monoid ✅
• Functor ✅
• Coming up next: Apply & Applicative!