Add polymorphic type catamorphisms

[gabejohnson]

As discussed in https://github.com/fantasyland/fantasy-land/issues/151#issuecomment-243648722, #154 and https://github.com/fantasyland/fantasy-land/issues/185#issuecomment-355856738, I propose a specification for Either by providing a definition of a folding method named either.

It isn't really a type specification, it's more of an interface or algebra specification as multiple structures could be isomorphic to Either and hence provide an either method.

Open question: Should this specification be displayed in README.md, or in a type specific file?

[i-am-tom]

So, Gabe and I have talked about this, and I thought it would be a good time to share a proposal I wrote on the back of a figurative beer mat about 6 months ago.

Types are really simple, especially when church-encoded. Here are a bunch of them:

Maybe.js

exports['@@fantasyland-maybe/just'] = x => { cata: (_, f) => f(x) }
exports['@@fantasyland-maybe/nothing'] = x => { cata: (x, _) => x }

Either.js

exports['@@fantasyland-either/left'] = x => { cata: (f, _) => f(x) }
exports['@@fantasyland-either/right'] = x => { cata: (_, g) => g(x) }

Reader.js

exports['@@fantasyland-reader/reader'] = f => { cata: env => f(env) }

For all these types, there are well-defined instances for the various typeclasses:

Later in Maybe.js...

...

exports['@@fantasyland/map'] = f => m => m.cata({
  nothing: exports['@@fantasyland-maybe/nothing'],
  just: f
})

So on, so forth. When reduced to Church encoding, everything has a nice, clean implementation that is as basic as it could possibly be. It is also enough of a structure to define all the implementations for all the spec.

---

NOW, say I'm writing a library, ReallyCoolMaybe, that I want to implement the fantasyland spec. I write it like this:

const MyReallyCoolMaybe = Object.assign({}, require('fantasyland/types/Maybe'), {
  // My really cool methods

  just: ... // My own error checking on my own constructor
})

I can write my library exactly how I like, with my own methods, never feeling pinned to a particular implementation of the spec. I can even worry about tail-recursion and the like by overriding the basic fold (providing that the new fold is indistinguishable to the user).

I now have a common interface, which means values of my custom type will work with any other FL-compatible library. I now have my own methods, so I'm not restricted by a Fantasy Land implementation. This, to me, is the minimum possible structure we can require, while retaining all the utility. I have all the FL interfaces implemented, as well as the "constructors" for building church-encoded types, which I am then free to augment as I please. The point is that, whatever the situation, I know that a fantasy-land-compatible type has this cata (or whatever colour we paint the shed) function with a well-documented signature, and anything else is vendor-specific frill.

My 2c, anyway.