Sunday, 12 December 2021

How to implement monadic do notation using a Coroutine?

I translated the coroutine implementation from Control.Monad.Coroutine to Javascript. The translation might contain a few bugs, but my actual problem is that I don't know how to put everything together to apply it.

The raw coroutine type is m (Either (s (Coroutine s m r)) r), where m has a monad and s a functor constraint. Here is the translation:

const TAG = Symbol.toStringTag;

const CoroutineT = mttx => ({
  [TAG]: "Coroutine",
  run: mttx
});

CoroutineT.map = ({map}, {map: map2}) => f => mttx =>
  CoroutineT(map2(ttx => ttx.run({
    right: x => Either.Right(f(x)),
    left: tx => Either.Left(map2(map(f)) (tx))
  })) (mttx.run));

CoroutineT.ap = ap;

CoroutineT.of = ({of}) => x => CoroutineT(of(Either.Right(x)));

CoroutineT.chain = ({map}, {of, chain}) => mttx => fmtt =>
  CoroutineT(chain(mttx.run) (ttx => ttx.run({
    left: tx => of(Either.Left(map(appr(chain, fmtt)) (tx))),
    right: x => fmtt(x).run
  })));

CoroutineT.lift = ({of, chain}) =>
  comp(CoroutineT) (liftM({of, chain}) (Either.Right));

CoroutineT.consume = ({of, chain}) => fm => mttx =>
  chain(CoroutineT.lift({of, chain}) (mttx.run)) (ttx => ttx.run({
    left: fm,
    right: of
  }));

CoroutineT.exhaust = ({of, chain}) => fm => function go(mttx) {
  return chain(mttx.run) (Either.cata(comp(go) (fm)) (of));
};

CoroutineT.suspend = ({of}) => tx => CoroutineT(of(Either.Left(tx)));

// Yield Suspension

const Yield = x => y => ({
  [TAG]: "Yield",
  run: [x, y]
});

Yield.map = f => tx => Yield(tx[0]) (f(tx[1]));
Yield.yield = ({of}) => x => CoroutineT.suspend({of}) (Yield(x) (of(null)));

Here are a few more combinators for the sake of completeness:

const Either = {};

Either.Left = x => ({
  [TAG]: "Either",
  run: ({left}) => left(x)
});

Either.Right = x => ({
  [TAG]: "Either",
  run: ({right}) => right(x)
});

Either.cata = left => right => tx => tx.run({left, right});

// Coroutine

CoroutineT.mapMonad = ({map}, {of, chain}) => fm => function go(mmtx) {
  return CoroutineT(
    liftM({of, chain}) (mtx => mtx.run({
      left: tx => Either.Left(map(go) (tx)),
      right: x => Either.Right(x)
    })) (fm(mmtx.run)));
};

CoroutineT.mapSuspension = ({map}, {of, chain}) => fm => function go(mmtx) {
  return CoroutineT(
    liftM({of, chain}) (mtx => mtx.run({
      left: tx => Either.Left(fm(map(go) (tx))),
      right: x => Either.Right(x)
    })) (mmtx.run));
};

CoroutineT.exhaustM = ({of, chain}) => function go(fm) {
  return mttx => chain(mttx.run) (Either.cata(kipe({chain}) (go) (fm)) (of));
};

CoroutineT.fold = ({of, chain}) => f => function go(acc) {
  return mttx => chain(mttx.run) (ttx => ttx.run({
    left: tx => uncurry(go) (f(acc) (tx)),
    right: x => of([acc, x])
  }));
};

// Await Suspension

const Await = f => ({
  [TAG]: "Await",
  run: f
});

Await.map = f => tg => Await(x => f(tg.run(x)));
Await.await = ({of}) => CoroutineT.suspend({of}) (Await(of))

const ap = ({of, chain}) => mf => mx =>
  chain(mf) (f => chain(mx) (x => of(f(x))));
  
const kipe = ({chain}) => gm => fm => // Kleisli pipe
  x => chain(gm(x)) (fm);
  
const appr = (f, y) => x => f(x) (y);
 
const liftM = ({of, chain}) => f => mx =>
  chain(mx) (x => of(f(x)));

const uncurry = f => ([x, y]) => f(x) (y);

const comp = g => f => x => g(f(x));

Coroutines are a generalization of generators so implementing the following do-notation like function seems consistent (even though we're stuck with nesting again):

const _do = ({chain, of}) => init => gtor => {
  const go = ({done, value: mx}) =>
    done
      ? mx
      : chain(mx) (x => go(it.next(x)));

  const it = gtor(init);
  return go(it.next());
};

const of = x => [x];

const chain = xs => fm =>
  xs.reduce((acc, x) =>
    acc.concat(fm(x)), []);

const xs = [1,2],
  ys =[3,4];

_do({chain, of}) () (function*() {
  const x = yield xs,
    y = yield ys;

  return [x + y];
});

I have no idea how to even begin with. The monad is probably Id, because we don't need an effect for this computation. Maybe someone can give a sketch how a coroutine encoding of the above function would look like.



from How to implement monadic do notation using a Coroutine?

No comments:

Post a Comment