Datatype-generic typeclass instances

[masaeedu]

Sometimes it's useful to be able to define logical instances of various typeclasses for any datatype that is of the correct shape, without tying yourself to a particular underlying representation of the type.

Here for example is a generic implementation of Maybe, parametrized by a pair of constructors and a case matcher:

// Datatype-generic instance of map, of, chain
  // Just :: a -> T a
  // None :: T a
  // match :: { "Just" :: a -> b, "None" :: b } -> T a -> b
  // where T is an arbitrary concrete datatype
const GenericMaybe = ({ Just, None, match }) => {
  // Functor
  const map = f => match({ None, Just: x => Just(f(x)) });

  // Monad
  const of = Just;
  const chain = f => match({ None, Just: f });

  return { map, of, chain };
};

What does this buy us? Given a generic implementation like this, we can take any value level representation of data that can be massaged into a Just, None and match, and obtain Maybe behavior for said type. As an example:

const k = Symbol("my maybe key");
const none = {};

// One possible data representation of a Maybe a: { [k] :: a, ... } | { ... }
const MyMaybe = {
  Just: value => ({ [k]: value }),
  None: none,
  match: ({ Just, None }) => o =>
    o.hasOwnProperty(k) ? Just(o[k]) : None
}

const { map, chain, of } = GenericMaybe(MyMaybe);

Now we have map, chain, of etc. operations available for data in a form possibly more naturally suited to my application domain, without having to wrap or unwrap anything. See the fiddle linked below for some example usage.

Assuming Sanctuary provided datatype-generic implementations (where reasonable), it would be easy for users who recognize isomorphisms between raw data they're working with and a generic Sanctuary type to reach in and pull out implementations that work directly with their data for free. The benefit is that the cost of wrapping and unwrapping things is paid at the function level, where it is (usually) not the hot path, and where there are more opportunities for optimization. Performing the wrapping and unwrapping at the data level is more costly and syntactically tedious for the user.

Here's a jsfiddle with all the code in case you want to play with things.

Related reading:

• https://www.microsoft.com/en-us/research/publication/scrap-your-boilerplate-a-practical-approach-to-generic-programming/
• https://wiki.haskell.org/GHC.Generics
• https://hackage.haskell.org/package/uniplate

[masaeedu]

Another nice coincidence I found: implemented datatype agnostically, Maybe and Either actually have the same instances for functor and monad:

const GenericEither = ({ Left, Right, match }) => {
  const map = f => match({ Left, Right: x => Right(f(x)) });
  const of = Right;
  const chain = f => match({ Left, Right: f });

  return { map, of, chain };
};

// A concrete representation of an Either a: { "left" :: Bool, "v" :: a }
const MyEither = {
  Left: v => ({ left: true, v }),
  Right: v => ({ left: false, v }),
  match: ({ Left, Right }) => ({ left, v }) => (left ? Left(v) : Right(v))
};

// Reuse generic implementation for our Either
{
  const { of, map, chain } = GenericEither(MyEither);

  console.log([
    map(x => x * 2)(of(21)),
    map(x => x * 2)(MyEither.Left("error"))
  ]);
}

// A concrete representation of a Maybe a: { [k] :: a, ...  } | { ... }
const k = Symbol("my maybe key");
const MyMaybe = {
  Just: v => ({ [k]: v }),
  None: {},
  match: ({ Just, None }) => o => (o.hasOwnProperty(k) ? Just(o[k]) : None)
};

// Reuse generic implementation for our Maybe
{
  const { None, Just } = MyMaybe;

  // translating the constructor names is boilerplate
  // I can easily abstract out into a single function call,
  // but it's good to see the guts
  const { of, map, chain } = GenericEither({
    Left: None,
    Right: Just,
    match: ({ Left, Right }) => MyMaybe.match({ None: Left, Just: Right })
  });

  console.log([
    map(x => x + 2)(of(42)),
    map(x => x + 2)(None),
    chain(x => (x > 40 ? None : of(x * 2)))(of(42)),
    chain(x => (x > 40 ? None : of(x * 2)))(of(32)),
    map(x => None)(of(42)),
    map(x => of(x * 2))(of(42))
  ]);
}

[davidchambers]

This is an interesting idea, but it's not clear to me exactly what you're proposing. Are you suggesting that Sanctuary define S.Nothing and S.Just in terms of S.GenericMaybe, or are you suggesting that we remove S.Nothing and S.Just and require users to define their own data constructors in terms of S.GenericMaybe?

[masaeedu]

@davidchambers The former, but with the underlying generic instances also exported (perhaps in a different package) so that the user can interpret their existing data as an instance of these classes in a pinch. This can be done for most of the concrete datatypes Sanctuary defines (Cons lists, Either, Maybe, Pair, etc.).

[masaeedu]

Btw, it's possible to entirely automate the process of creating the constructors and match in those cases where a user doesn't care about the underlying representation. This is just the ADT definition const { Just, None, match } = adt({ Just: [a], None: [] }), with the underlying representation of Just(42) being, say, { case: "Just", values: [42] }.

Implementing adt is fairly straightforward, but there's also libraries like Daggy that could be used for this purpose with some minor translation between match and cata (i.e. function vs method).

[masaeedu]

Copying another motivating example I posted in the Gitter; generic lists:

const Arr = (() => {
  const Nil = [];
  const Cons = head => rest => [head, ...rest];
  const match = ({ Cons, Nil }) => a =>
    a.length === 0 ? Nil : Cons(a[0])(a.slice(1));

  return { Nil, Cons, match };
})();

// ImmutableJS?
const Imm = (() => {
  const Nil = ...
  const Cons = ...
  const match = ...

  return { Cons, Nil, match };
})();

const GenericList = ({ Cons, Nil, match }) => {
  // Misc
  const length = match({ Nil: 0, Cons: _ => rest => 1 + length(rest) });

  // Functor
  const map = f =>
    match({ Nil, Cons: head => rest => Cons(f(head))(map(f)(rest)) });

  return { length, map };
};

console.log(GenericList(Arr).length([0, 1, 2]));
// 3
console.log(GenericList(Arr).map(x => x * 2)([1, 2, 3]));
// [2, 4, 6]