On fantasy, part 6

⏰ Takes about 6 minutes to read

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

It’s time. To fold all the things.

Today’s instance will be Foldable, and this is another instance that adds only one method to our Maybe:

reduce :: Foldable f => f a ~> ((b, a) -> b, b) -> b

u.reduce(f, x)

And, some rules:

  • f must be a binary function
    • first argument to f must be of the same type as x
    • return value of f must be of the same type as x
  • x is the initial accumulator value for the reduction

Now, that last part… what exactly happened there? We got 2 new keywords, so let’s break them down and place them in our function:

  • Accumulator ➡ This means this value will be aggregated by something else in some way in multiple iterations. It also means it will persist from one iteration to the other.
  • Reduction ➡ Reducing means taking many things and turning them into one thing. In Javascript, we’re used to Array.prototype.reduce, which is intended to do exactly this.

So, reduce is a function on a Foldable f that takes a binary (2 arguments) function and an initial value. This initial value will be passed as the first argument to the function. The second value passed to the function, will be the value inside the Foldable f, and the return value of this function will be the result of our reduction.

Now, how should this function look for our Maybe?

Start with Nothing

We have 2 options for what this function can do when called on a Nothing.

  • We can return Nothing
  • Or, we can return the initial value.

Both make sense from our Nothing’s perspective, but only one makes sense if we look at what the function is supposed to do. Our return value’s type is supposed to be the same as the initial value’s type. So, if we return Nothing, we won’t fulfil that. Thus, the only way to do this is to return our initial value. It would look like this:

it("should return the initial value provided when called on a Nothing", () => {
  const expected = 10;
  const actual = Nothing().reduce((acc, x) => acc + x, 10);
  expect(actual).toBe(expected);
});

const Nothing = value => ({
  // …
  reduce: (fn, initial) => initial,
  // …
});

And, on our Just we have a value inside that we can use as second value to the function. We trust this function to do something with the initial value and the one on our Just and return something that fulfils the rules. It can look like this:

it("should return the result of calling the function with initial value and value inside of Just", () => {
  const expected = 100;
  const actual = Just(2).reduce(Math.pow, 10);
  expect(actual).toBe(expected);
});

const Just = value => ({
  // …
  reduce: (fn, initial) => fn(initial, value),
  // …
});

There’s something really important happening here. All the other functions we’ve defined so far return a value wrapped inside a type. For our Just, all functions have returned a Just of something. But reduce doesn’t. Reduce is returning a value without the wrapper. This is important, because it’s the first time we get a way to receive that value directly, without handling it through the type. This makes reduce super powerful, and also sort of dangerous. You don’t want to use reduce unless you’re absolutely certain you won’t need the type anymore, because that would be defeating its own purpose.

And for the grand finale (of this instance), the laws! Here’s what reduce’s laws look like:

u.reduce is equivalent to u.reduce((acc, x) => acc.concat([x]), []).reduce

const foldableReduce = (fn, initial, a) =>
  a.reduce(fn, initial) === a.reduce((acc, x) => acc.concat([x]), []).reduce(fn, initial);

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

Aaand we’re done! That’s it for our Foldable instance.

  • Setoid ✅
  • Semigroup ✅
  • Monoid ✅
  • Functor ✅
  • Apply ✅
  • Applicative ✅
  • Foldable ✅
  • Traversable coming up next!

We’re approaching the end of this journey. I’d say there are 2 blog posts left on it. I hope you’ve enjoyed reading it so far as much as I’ve enjoyed writing it.