12

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:

-- | Suspending, resumable monadic computations.
newtype Coroutine s m r = Coroutine {
   -- | Run the next step of a `Coroutine` computation. 
   --   The result of the step execution will be either a suspension or
   --   the final coroutine result.
   resume :: m (Either (s (Coroutine s m r)) r)
   }

instance (Functor s, Monad m) => Monad (Coroutine s m) where
   ....

Here is the translation:

const TAG = Symbol.toStringTag;

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

CoroutineT.map = ({map: mapSuspension}, {map: mapBase}) => f => function go(mmx) {
  return CoroutineT(mapBase(mx => mx.run({
    left: tx => Either.Left(mapSuspension(go) (tx)),
    right: x => Either.Right(f(x))
  })) (mmx.run));
};

CoroutineT.ap = ({map: mapSuspension}, {map: mapBase, chain}) => function go(mmf) {
  return mmx =>
    CoroutineT(chain(mmf.run) (mf => mx.run({
      left: tf => Either.Left(mapSuspension(go) (tf)),

      right: f => mapBase(mx => mx.run({
        left: tx => Either.Left(mapSuspension(go) (tx))
        right: x => Either.Right(f(x))
      })) (mmx.run)
    })));
};


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

CoroutineT.chain = ({map}, {of, chain}) => mmx => fmm => function go(mmx2) {
  return CoroutineT(chain(mmx2.run) (mx => mx.run({
    left: tx => of(Either.Left(map(go) (tx))),
    right: x => fmm(x).run
  })));
} (mmx);

// transformer

CoroutineT.lift = ({map}) => comp(CoroutineT) (map(Either.Right));

CoroutineT.mapT = ({map: mapSuspension}, {map: mapBase}) => f => function go(mmx) {
  return CoroutineT(
    mapBase(mx => mx.run({
      left: tx => Either.Left(mapSuspension(go) (tx)),
      right: x => Either.Right(x)
    })) (f(mmx.run)));
};

CoroutineT.consume = ({of, chain}) => f => mmx =>
  CoroutineT(chain(mmx.run) (mx => mx.run({
    left: tx => f(tx)
    right: x => of(Either.Right(x))
  })));

CoroutineT.exhaust = ({of, chain}) => f => function go(mmx) {
  return chain(mmx.run) (mx => mx.run({
    left: tx => go(f(tx)),
    right: of
  }));
};

CoroutineT.exhaustM = ({of, chain}) => fm => function go(mmx) {
  return chain(mmx.run) (mx => mx.run({
    left: tx => chain(fm(x)) (go),
    right: of
  }))
};

CoroutineT.fold = ({of, chain}) => f => init => mmx => function go([acc, mmx2]) {
  return chain(mmx2.run) (mx => mx.run({
    left: tx => go(f(acc) (tx)),
    right: x => of(Pair(acc, x))
  }));
} (Pair(init, mmx));

// suspension functor

CoroutineT.mapSuspension = ({map: mapSuspension2}, {map: mapBase}) => f => function go(mmx) {
  return CoroutineT(
    mapBase(mx => mx.run({
      left: tx => Either.Left(f(mapSuspension2(go) (tx))),
      right: x => Either.Right(x)
    })) (mmx.run));
};

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

// Yield suspension

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

Yield.map = f => tx => Yield(tx[0]) (f(tx[1]));

Yield.yield = ({of}) => x => CoroutineT.suspend({of}) (Yield(x) (of(null)));

// Either

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});

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.

Will Ness
  • 70,110
  • 9
  • 98
  • 181
  • Can you add a type declaration to `_go` and an example of how you would use it? – Bergi Dec 11 '21 at 01:40
  • 1
    "*the following do-notation like function seems consistent*" - it is not. It looks like you want translate `x <- mx` to `const x = yield mx;`. But this only works for "linear" monads (Id, Maybe, Either, State, IO, …), not for "diverging" monads like List where `chain` calls the callback multiple times. Generators are stateful, and doing `it.next()` is repeatable. – Bergi Dec 11 '21 at 01:41
  • "*a coroutine encoding of the above function*" - I have no idea of what you mean by that. Do you just want to call `_do(CoroutineT(…))`? What doesn't work in your current implementation? What would the type of the new function be? How would you expect it to be used, can you given an example for a call? – Bergi Dec 11 '21 at 01:44
  • @Bergi I extended the generator example. As far as I comprehend the topic coroutines are more general than generators, hence any generator based computation should be expressible using coroutines. This should hold for `_do` as well, although both computations aren't equivalent as you've mentioned. I've found some explanations [in the purescript docs](https://github.com/purescript-contrib/purescript-coroutines/tree/main/docs), but they use a different approach based on `FreeT`. –  Dec 11 '21 at 12:52
  • @Bergi Beyond that point I'm lost. I don't know how to use the coroutine type to express `_do` or if it makes sense at all trying. It's one thing to create/compose generalized types, but it's a different thing to actually apply them. There is a lot of knowledge hidden in the latter. –  Dec 11 '21 at 13:06
  • Thanks for the example usage of `_go`, that demonstrates well why generators are unfit to be used with the `List` monad - one would have expected `[4,5,5,6]` as the result but actually gets `[4,undefined,undefined]` (and would get an exception if `.concat` would actually check for its argument being an array). – Bergi Dec 12 '21 at 01:18
  • 1
    "*how to use the coroutine type to express `_do`*" - I don't think that makes sense, `_do` is meant to work with any monad type and you just keep the implementation as-is. What you *could* do is the other way round: using `_do` to express a `Coroutine`. – Bergi Dec 12 '21 at 01:20

0 Answers0