How to write a TaskT Monad Transformer to compose asynchronous computations with other effects?

Question

I construct monad transformers as variants of chain/of that take an additional argument - a type directory of the outer monad:

const None =
  ({runOption: null, tag: "None", [Symbol.toStringTag]: "Option"});

const Some = x =>
  ({runOption: x, tag: "Some", [Symbol.toStringTag]: "Option"});
  
const optOfT = of => x => of(Some(x));

const optChainT = ({chain, of}) => fmm => mmx =>
  chain(mx => {
    switch (mx.tag) {
      case "None": return of(None);
      case "Some": return fmm(mx.runOption);
    }
  }) (mmx);

const arrOf = x => [x];

const arrChain = fm => xs =>
  xs.reduce((acc, x) => arrPushFlat(acc) (fm(x)), []);

const arrPushFlat = xs => ys => {
  ys.forEach(x =>
    xs.push(x));

  return xs;
};

const xs = [Some("foo"), None, Some("bar")];

console.log(
  optChainT({chain: arrChain, of: arrOf})
    (s => [Some(s.toUpperCase())]) (xs)); // [Some("FOO"), None, Some("BAR")]

So basically a transformer is a handwritten composition of two monads, i.e. it takes two monads and returns a new composite monad, which is thus itself composable. Welcome to composable effects.

But I cannot wrap my head around monad transformers when lazyness comes on the table. What if I want to create a monad transformer for [Task<Option<a>, Error>]? I'd need a transformer for asynchronous tasks, i.e. a tChainT, but how would this operator look like?

Here is a mechanical implementation that (AFAIK) illustrates why monads are not composable in a general manner:

const tChainT = ({chain, of}) => fmm => mmx =>
  chain(mx =>
    tChain(fmm) (mx) // A
      ) (mmx);

Line A returns a Task that when run will eventually yield an Array of Tasks of Options and then will be passed to the given continuation. But I need the result right away.

Here is the part of my Task implementation that is relevant to the question:

const Task = k =>
  ({runTask: (res, rej) => k(res, rej), [Symbol.toStringTag]: "Task"});

const tChain = fm => mx =>
  Task((res, rej) => mx.runTask(x => fm(x).runTask(res, rej), rej));

const tOf = x => Task((res, rej) => res(x));

Aadit M Shah Aadit M Shah · Accepted Answer · 2019-12-07T17:45:38

The tChainT function from your question doesn't work as expected because it has the wrong type.

const tChainT = ({chain, of}) => fmm => mmx =>
  chain(mx =>
    tChain(fmm) (mx) // A
      ) (mmx);

// can be simplified to

const tChainT = ({ chain }) => fmm => chain(tChain(fmm));

// tChain  ::                   (a -> Task e b) -> Task e a -> Task e b
//                                                 |______|    |____|
//                                                    |          |
// chain   :: Monad    m     =>                      (a     ->   m    b) -> m        a      ->   m    b
//                    _|__                                                 _|__    __|___       _|__
//                   |    |                                               |    |  |      |     |    |
// tChainT :: Monad (Task e) => (a -> Task e b) ->                        Task e (Task e a) -> Task e b

The tChainT function from your answer also has the wrong type.

// tChainT :: Monad m => (a -> Task e b) -> m (Task e a) -> m (Task e b)
const tChainT = ({chain, of}) => fm => mmx =>
  chain(mx =>
    of(tChain(fm) (mx))) (mmx); // ***A***

Notice that the return type of fm is Task e b instead of m (Task e b). Thus, tChainT does not return a valid monadic bind function. In fact, it's impossible to create a function of the type Monad m => (a -> m (Task e b)) -> m (Task e a) -> m (Task e b) because m (Task e a) is the wrong structure of the TaskT e monad transformer. The correct structure is as follows.

// newtype TaskT e m a = TaskT { runTaskT :: (a -> m (), b -> m ()) -> m () }
const TaskT = runTaskT => ({ [Symbol.toStringTag]: "TaskT", runTaskT });

// tChainT :: (a -> TaskT e m b) -> TaskT e m a -> TaskT e m b
const tChainT = f => m => TaskT((res, rej) =>
    m.runTaskT(x => f(x).runTaskT(res, rej), rej));

// tOfT :: a -> TaskT e m a
const tOfT = x => TaskT((res, rej) => res(x));

Notice that tChainT and tOfT have the same implementation as tChain and tOf respectively. This is because the underlying monad of TaskT comes from the resolution and rejection handlers. Hence, the continuation machinery handles it for us. After all Task is just Cont with an extra continuation for rejection.

How to write a TaskT Monad Transformer to compose asynchronous computations with other effects?

1 Answers