How to use the ContT monad transformer?

Question

The ContT monad transformer has the same implementation like the Cont monad, but I'm not able to apply it to all three Either cases

• Right
• Left from the current monadic action
• Left from a previous monadic computation

The last one fails and all attempts to fix it failed as well:

const record = (type, o) => (
  o[Symbol.toStringTag] = type.name || type,
  o);

const union = type => (tag, o) => (
  o[Symbol.toStringTag] = type,
  o.tag = tag.name || tag,
  o);

const match = (tx, o) => o[tx.tag] (tx);

const Either = union("Either");
const Left = left => Either(Left, {left});
const Right = right => Either(Right, {right});

const eithChain = mx => fm =>
  match(mx, {
    Left: _ => mx,
    Right: ({right: x}) => fm(x)
  });

const ContT = contt => record(ContT, {contt});

const contChainT = mmk => fmm =>
  ContT(c => mmk.contt(x => fmm(x).contt(c)));

const main = foo =>
  contChainT(ContT(k => k(foo))) (mx =>
    eithChain(mx) (x =>
      x === 0
        ? ContT(k => k(Left("ouch!")))
        : ContT(k => k(Right(x * x)))));

main(Right(5)).contt(console.log); // Right(25)
main(Right(0)).contt(console.log); // Left("ouch!")
main(Left("yikes!")).contt(console.log); // Type Error

This is fruststrating. Any hints are much appreciated!

Answer 1

Your main function does not type check.

const main = foo =>
  contChainT(ContT(k => k(foo))) (mx =>
    eithChain(mx) (x =>
      x === 0
        ? ContT(k => k(Left("ouch!")))
        : ContT(k => k(Right(x * x)))));

First, let's simplify it. Given, const pureContT = x => ContT(k => k(x)) we can rewrite main as follows.

const main = foo =>
  contChainT(pureContT(foo)) (mx =>
    eithChain(mx) (x =>
      pureContT(x === 0
        ? Left("ouch!")
        : Right(x * x))));

However, chain(pure(x))(f) is the same as f(x) (left identity law). Hence, we can further simplify.

const main = mx =>
  eithChain(mx) (x =>
    pureContT(x === 0
      ? Left("ouch!")
      : Right(x * x)));

Here, you can see the problem. The eithChain function has the following type.

Either e a -> (a -> Either e b) -> Either e b

However, the callback given to eithChain returns a ContT instead of an Either.

---

I would actually say that you're approaching this problem wrong.

ContT r m a = (a -> m r) -> m r

-- Therefore

ContT r (Either e) a = (a -> Either e r) -> Either e r

This is not what you want. You should be using the EitherT transformer instead.

EitherT e m a = m (Either e a)

Cont r a = (a -> r) -> r

-- Therefore

EitherT e (Cont r) a = Cont r (Either e a) = (Either e a -> r) -> r

Here's what I would do.

// Left : e -> Either e a
const Left = error => ({ constructor: Left, error });

// Right : a -> Either e a
const Right = value => ({ constructor: Right, value });

// Cont : ((a -> r) -> r) -> Cont r a
const Cont = runCont => ({ constructor: Cont, runCont });

// either : (e -> b) -> (a -> b) -> Either e a -> b
const either = left => right => either => {
    switch (either.constructor) {
    case Left: return left(either.error);
    case Right: return right(either.value);
    }
};

// MonadEitherT : Monad m -> Monad (EitherT e m)
const MonadEitherT = ({ pure, bind }) => ({
    pure: x => pure(Right(x)),
    bind: m => f => bind(m)(either(e => pure(Left(e)))(f))
});

// MonadCont : Monad (Cont r)
const MonadCont = {
    pure: x => Cont(k => k(x)),
    bind: m => f => Cont(k => m.runCont(x => f(x).runCont(k)))
};

// MonadEitherCont : Monad (EitherT e (Cont r))
const MonadEitherCont = MonadEitherT(MonadCont);

// main : Either String Number -> EitherT String (Cont r) Number
const main = either => MonadEitherCont.bind(MonadCont.pure(either))(x =>
    MonadCont.pure(x === 0 ? Left("ouch!") : Right(x * x)));

// show : Either e a -> String
const show = either
    (e => `Left(${JSON.stringify(e)})`)
    (x => `Right(${JSON.stringify(x)})`);

// print : Either e a -> ()
const print = x => console.log(show(x));

main(Right(5)).runCont(print); // Right(25)
main(Right(0)).runCont(print); // Left("ouch!")
main(Left("yikes!")).runCont(print); // Left("yikes!")

Answer 2

Complementing to Aadit's answer I managed to implement a version with ContT as transformer. All I needed to manipulate the current continuation was the standard Monad Cont implementation and the corresponding lift:

const record = (type, o) => (
  o[Symbol.toStringTag] = type.name || type,
  o);

const union = type => (tag, o) => (
  o[Symbol.toStringTag] = type,
  o.tag = tag.name || tag,
  o);

const match = (tx, o) => o[tx.tag] (tx);

const Either = union("Either");
const Left = left => Either(Left, {left});
const Right = right => Either(Right, {right});

const eithChain = mx => fm =>
  match(mx, {
    Left: _ => mx,
    Right: ({right: x}) => fm(x)
  });

const ContT = contt => record(ContT, {contt});

const contChainT = mmk => fmm =>
  ContT(k => mmk.contt(x => fmm(x).contt(k)));

const contLiftT = chain => mmk =>
  ContT(k => chain(mmk) (k));

const log = x => (console.log(x), x);

const main = foo =>
  contChainT(contLiftT(eithChain) (foo)) (x =>
    x === 0
      ? ContT(k => Left("yikes!"))
      : ContT(k => k(x * x)));

const foo = main(Right(5)).contt(x => Right(log(x))); // logs 25
const bar = main(Right(0)).contt(x => Right(log(x)));
const baz = main(Left("ouch!")).contt(x => Right(log(x)));

log(foo); // Right(25)
log(bar); // Left("yikes!")
log(baz); // Left("ouch!")

It seems as if ContT/M with an arbitrary base monad M and T/Cont with an arbitrary transformer T are commutative in their effetcs. I don't have the mathematical skills to prove such claim though.