On fantasy, part 1

⏰ Takes about 20 minutes to read

On fantasy, part 1

The internet is full of fantastic things, created by fantastic people. One of such things, is the Fantasy-Land specification. As the creators describe it, it’s an Algebraic Javascript Specification which works as a guide on how to create interoperable algebraic structures in Javascript. Its goal is that, everyone who follows the specification, can use the creations of others with complete certainty that their structures will work as expected. This is of course something we get in other languages like Haskell for free, but since this is Javascript, the only way to achieve this kind of behaviour is in a prescriptive fashion, like this spec does.

My history with Fantasy Land is not a field of roses, unless those roses were 100% made out of thorns. I first tried to read the spec about 2 years ago, before I even knew what a type signature was and failed horribly. Then, I tried about 1 year ago, now armed with some type signature knowledge, and still failed because I didn’t know the first thing about how a type system should work. This will be my third time taking a stab at the spec, and so far, it’s going swell. All that Haskelling has definitely paid off 🦄.

A Fantastic Maybe

Yesterday, I posted a little function I wrote that tried to deal with the existence of nested properties in JS objects. In there, I very briefly mentioned how the pattern I created looked very much like a Maybe. Then this happened:

At the same time, Tobias sent me a link to the Fantasy Land spec, referring to my previous attempts at Algebraic JS datatypes, and how I could try and follow the spec. Those two things combined brewed a perfect storm in which to create another Maybe implementation. The following is an initial attempt to build one, following the spec but not being entirely valid (there are syntax rules, and prefix name rules that I won’t follow).

The Algebras

My Maybe will have instances of the following list of Algebras:

  • Semigroup
  • Monoid
  • Functor
  • Applicative
  • Foldable
  • Traversable
  • Monad

I chose those, mostly because they align with the instance that Haskell’s Maybe has. And, I’ll go in order, starting with the Semigroup.

A Semigroup must implement just one function: concat, which has the following signature:

concat :: Semigroup a => a ~> a -> a

Let’s unpack that.

  • concat ➡ function name
  • :: ➡ after this, comes the function’s signature
  • Semigroup a => ➡ this is a type restriction, meaning that every time we see a in what comes next, a needs to have an instance of Semigroup.
  • a ~> ➡ the squiggly line means that it’s a method on a. Think of it like, a is an object, that needs to have a property called concat that needs to be a function. And it needs to fulfil this type signature.
  • a -> a ➡ the actual function. In this case, it means that it takes an a as an input, and returns an a as output. We can say that, since the letters used are the same, that both the input and the output need to be of the same type, same as the object the function belongs to.

In one go:

concat is a function belonging to all Semigroup objects, that takes a Semigroup of the same type as input and returns a Semigroup of the same type as output.

That’s quite a mouthful, but I think it makes some sense. Granted, I’m not the best at explaining algebraic concepts. Yet.

Implementation baby steps

Let’s remember a bit what Maybe does. For that, I wrote some tests:

describe("The Maybe type", () => {
  describe("Has two possible definitions", () => {
    it("should return Nothing if the value passed is undefined || null", () => {
      const expected = Nothing().isNothing();
      const actual = Maybe(undefined).isNothing();
      expect(actual).toBe(expected);
    });

    it("should return Just if the value passed is not undefined || null", () => {
      const expected = Just(1).isJust();
      const actual = Maybe(1).isJust();
      expect(actual).toBe(expected);
    });
  });
});

Note; at first I tried to use toEqual in order to compare objects, but that didn’t work at all, so I worked around it by defining isNothing and isJust functions

So, according to these tests, Maybe(undefined || null) === Nothing() and Maybe(something) === Just(something). Here’s the code for that:

const Maybe = value => (typeof value === "undefined" || value === null ? Nothing() : Just());

const Nothing = value => ({
  isNothing: () => true,
  isJust: () => false,
});

const Just = value => ({
  isNothing: () => false,
  isJust: () => true,
});

On to the next challenge:

describe("Has a concat method which", () => {
  it("should have a type of function", () => {
    const expected = "function";
    const actual = typeof Maybe().concat;
    expect(actual).toEqual(expected);
  });
});

This one is really straight forward:

const Maybe = value => (typeof value === "undefined" || value === null ? Nothing() : Just());

const Nothing = value => ({
  isNothing: () => true,
  isJust: () => false,
  concat: () => {},
});

const Just = value => ({
  isNothing: () => false,
  isJust: () => true,
  concat: () => {},
});

Next one!


it("should return its argument if called on a Nothing", () => {
  const expected = “Just(1)”;
  const actual = Nothing()
    .concat(Just(1))
    .toString();
  expect(actual).toEqual(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);
});

Ok, so if one of the sides is a Nothing, then the other side needs to be returned. That also means that if both sides are Nothing, then Nothing will be returned. Here, I use the toString trick again, to be able to compare easily between 2 structures in JS, including their internal values. And, the code that passes this test is:

const Nothing = value => ({
  isNothing: () => true,
  isJust: () => false,
  concat: other => other,
  toString: () => "Nothing",
});

const Just = value => ({
  isNothing: () => false,
  isJust: () => true,
  concat: () => {
    return Just(value);
  },
  toString: () => `Just(${value})`,
});

Now is where it gets interesting. The next one tests how concat works when both sides are Just (isn’t that poetic?).

it("should return the result of concatenating its value with the parameter's value when both are Just [array]", () => {
  const expected = Just([1, 2, 3, 4, 5, 6]).toString();
  const actual = Just([1, 2, 3])
    .concat(Just([4, 5, 6]))
    .toString();
  expect(actual).toEqual(expected);
});

In this case we pass arrays, because we know how arrays should be concatenated. And what we’re saying is that it should concatenate the values inside, and return them wrapped in a Just as well.

A couple lines of code make this pass:


const Nothing = value => ({
  value: () => Nothing(),
  isNothing: () => true,
  isJust: () => false,
  concat: other => other,
  toString: () => "Nothing",
});

const Just = value => ({
  value: () => value,
  isNothing: () => false,
  isJust: () => true,
  concat: other => {
    If (other.isNothing()) return Just(value);
    return Just(value.concat(other.value()))
  },
  toString: () => `Just(${value})`,
});

Since we know arrays have a concat method on Javascript, then we just use it. We needed a way to use the value wrapped by the Just, so we created a value() function that returns it.

Now, that passes that test… but what about something like: Just(1).concat(Just(2))? And strings? Objects? Other Semigroups?

That’s clearly a problem, so I wrote a helper function that kind of solves it. It 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 === "number" && typeof semiTwo === "number") return semiOne + semiTwo;
  if (typeof semiOne === "string" && typeof semiTwo === "string") return `${semiOne}${semiTwo}`;
  throw new Error("Not instances of semigroup, or concatenable primitives!");
};

It’s a big bunch of ifs, testing wether it’s an instance of Semigroup, with an ugly solution to that and other types afterwards to know how to concatenate them. Note how here we chose to concatenate numbers as summing them, but we could’ve also chosen multiplication, since they fulfil the same laws.

This function can then be used like this:


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

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

And now we can pass the following tests:

it("should return the result of concatenating its value with the parameter's value when both are Just String", () => {
  const expected = Just("Hello World").toString();
  const actual = Just("Hello ").concat(Just("World")).toString();
  expect(actual).toEqual(expected);
});

it("should return the result of summing its value with the parameter's value when both are Just Number", () => {
  const expected = Just(3).toString();
  const actual = Just(1).concat(Just(2)).toString();
  expect(actual).toEqual(expected);
});

So far, we managed to implement a concat function that will sort of work with most things. We still don’t know how to concat booleans, or objects for example, so there’s some room for improvement there. Apart from that, we also know that Semigroup must fulfil the law of associativity, meaning that: a.concat(b).concat(c) is equivalent to a.concat(b.concat(c)), and we haven’t tested that either so far.

When I started, I thought this was going to be a breeze, and I would be done in a day. Turns out I was quite wrong, but it’s been really fun so far. Next week, I’ll continue with the implementation, and when it’s done, I’ll refactor yesterday’s function using my Maybe to fulfil Wolfram’s wishes. 🎊