javascript - 如何将 TaskT 与 Trampoline 的 monad 实例结合起来进行无堆栈异步计算？

Question

Trampoline是一个单子，并为单子变压器堆栈增加了堆栈安全性。它通过依赖一个特殊的解释器monadRec（出于这个原因，Trampolinemonad 必须是最外层的 monad，即变压器堆栈的基本 monad。

在以下设置中TaskT（本质Cont上是共享）是 monad 转换器和Trampoline基本 monad：

// TASK

const TaskT = taskt => record(
  TaskT,
  thisify(o => {
    o.taskt = k =>
      taskt(x => {
        o.taskt = k_ => k_(x);
        return k(x);
      });

    return o;
  }));

// Monad

const taskChainT = mmx => fmm =>
  TaskT(k =>
    mmx.taskt(x =>
      fmm(x).taskt(k)));

const taskOfT = x =>
  TaskT(k => k(x));

// Transformer

const taskLiftT = chain => mmx =>
  TaskT(k => chain(mmx) (k));

// auxiliary functions

const taskAndT = mmx => mmy =>
  taskChainT(mmx) (x =>
    taskChainT(mmy) (y =>
      taskOfT([x, y])));

const delayTaskT = f => ms => x =>
  TaskT(k => setTimeout(comp(k) (f), ms, x));

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

const thisify = f => f({});

const log = (...ss) =>
  (console.log(...ss), ss[ss.length - 1]);

// TRAMPOLINE

const monadRec = o => {
  while (o.tag === "Chain")
    o = o.fm(o.chain);

  return o.tag === "Of"
    ? o.of
    : _throw(new TypeError("unknown trampoline tag"));
};

// tags

const Chain = chain => fm =>
  ({tag: "Chain", fm, chain});


const Of = of =>
  ({tag: "Of", of});

// Monad

const recOf = Of;

const recChain = mx => fm =>
  mx.tag === "Chain" ? Chain(mx.chain) (x => recChain(mx.fm(x)) (fm))
    : mx.tag === "Of" ? fm(mx.of)
    : _throw(new TypeError("unknown trampoline tag"));

// MAIN

const foo = x =>
  Chain(delayTaskT(x => x) (0) (x)) (Of);

const bar = taskAndT(
  taskLiftT(recChain) (foo(1)))
    (taskLiftT(recChain) (foo(2))); // yields TaskT

const main = bar.taskt(x => Of(log(x))); // yields Chain({fm, chain: TaskT})

monadRec(main); // yields [TaskT, TaskT] but [1, 2] desired

这不是我想要的，因为在Trampoline事件循环接收异步任务的结果之前强制评估。我需要的是相反的方式，但正如我已经提到的，没有TrampolineT变压器。我错过了什么？

标签： javascriptfunctional-programmingmonadsmonad-transformerstrampolines

Answer 1

此代码段中有几个问题。

IO问题 #1： (ie Task)没有 monad 转换器

众所周知，没有用于IO. ^[1]你的TaskT类型是仿照的ContT，ContT确实是一个单子转换器。但是，您正在使用TaskT执行异步计算，例如setTimeout，这就是问题出现的地方。

考虑 的定义TaskT，它类似于ContT。

newtype TaskT r m a = TaskT { taskt :: (a -> m r) -> m r }

因此，delayTaskT应该有类型(a -> b) -> Number -> a -> TaskT r m b。

const delayTaskT = f => ms => x =>
  TaskT(k => setTimeout(comp(k) (f), ms, x));

但是，setTimeout(comp(k) (f), ms, x)返回一个与 type 不匹配的超时 id m r。注意k => setTimeout(comp(k) (f), ms, x)应该有类型(b -> m r) -> m r。

事实上，当异步调用m r延续时，不可能变出一个类型的值。kmonad 转换器ContT仅适用于同步计算。

不过，我们可以Task将Cont.

newtype Task a = Task { task :: (a -> ()) -> () } -- Task = Cont ()

因此，无论何时Task存在于 monad 转换器堆栈中，它都将始终位于底部，就像IO.

如果您想让Taskmonad 堆栈安全，请阅读以下答案。

问题 #2：foo函数的返回类型错误

让我们暂时假设delayTaskT具有正确的类型。正如您已经注意到的，下一个问题是foo返回类型错误。

问题似乎是foo哪个返回 aTaskT包裹在 a 中Chain，而这个包裹TaskT与链完全分离，TaskT因此永远不会被评估/解雇。

我假设预期的类型foo是a -> TaskT r Trampoline a. 但是，实际类型foo是a -> Trampoline (TaskT r m a). 幸运的是，修复很容易。

const foo = delayTaskT(x => x) (0);

的类型foo与 相同taskOfT，即a -> TaskT r m a。我们可以专攻m = Trampoline。

问题#3：你没有taskLiftT正确使用

该taskLiftT函数将底层的一元计算提升到TaskT层中。

taskLiftT :: (forall a b. m a -> (a -> m b) -> m b) -> m a -> TaskT r m a

taskLiftT(recChain) :: Trampoline a -> TaskT r Trampoline a

现在，您正在taskLiftT(recChain)申请foo(1)和foo(2)。

foo :: a -> Trampoline (TaskT r m a) -- incorrect definition of foo

foo(1) :: Trampoline (TaskT r m Number)
foo(2) :: Trampoline (TaskT r m Number)

taskLiftT(recChain) (foo(1)) :: TaskT r Trampoline (TaskT r m Number)
taskLiftT(recChain) (foo(2)) :: TaskT r Trampoline (TaskT r m Number)

但是，如果我们使用正确的定义，foo那么类型甚至不会匹配。

foo :: a -> TaskT r Trampoline a -- correct definition of foo

foo(1) :: TaskT r Trampoline Number
foo(2) :: TaskT r Trampoline Number

-- Can't apply taskLiftT(recChain) to foo(1) or foo(2)

如果我们使用正确的定义，foo那么有两种方法来定义bar. 请注意，无法正确定义foousing setTimeout。因此，我重新定义foo为taskOfT.

1. 使用foo和不使用taskLiftT.

   const bar = taskAndT(foo(1))(foo(2)); // yields TaskT
   

   // TASK
   
   const TaskT = taskt => record(
     TaskT,
     thisify(o => {
       o.taskt = k =>
         taskt(x => {
           o.taskt = k_ => k_(x);
           return k(x);
         });
   
       return o;
     }));
   
   // Monad
   
   const taskChainT = mmx => fmm =>
     TaskT(k =>
       mmx.taskt(x =>
         fmm(x).taskt(k)));
   
   const taskOfT = x =>
     TaskT(k => k(x));
   
   // Transformer
   
   const taskLiftT = chain => mmx =>
     TaskT(k => chain(mmx) (k));
   
   // auxiliary functions
   
   const taskAndT = mmx => mmy =>
     taskChainT(mmx) (x =>
       taskChainT(mmy) (y =>
         taskOfT([x, y])));
   
   const delayTaskT = f => ms => x =>
     TaskT(k => setTimeout(comp(k) (f), ms, x));
   
   const record = (type, o) => (
     o[Symbol.toStringTag] = type.name || type, o);
   
   const thisify = f => f({});
   
   const log = (...ss) =>
     (console.log(...ss), ss[ss.length - 1]);
   
   // TRAMPOLINE
   
   const monadRec = o => {
     while (o.tag === "Chain")
       o = o.fm(o.chain);
   
     return o.tag === "Of"
       ? o.of
       : _throw(new TypeError("unknown trampoline tag"));
   };
   
   // tags
   
   const Chain = chain => fm =>
     ({tag: "Chain", fm, chain});
   
   
   const Of = of =>
     ({tag: "Of", of});
   
   // Monad
   
   const recOf = Of;
   
   const recChain = mx => fm =>
     mx.tag === "Chain" ? Chain(mx.chain) (x => recChain(mx.fm(x)) (fm))
       : mx.tag === "Of" ? fm(mx.of)
       : _throw(new TypeError("unknown trampoline tag"));
   
   // MAIN
   
   const foo = taskOfT;
   
   const bar = taskAndT(foo(1))(foo(2)); // yields TaskT
   
   const main = bar.taskt(x => Of(log(x))); // yields Chain({fm, chain: TaskT})
   
   monadRec(main); // yields [TaskT, TaskT] but [1, 2] desired

2. 不要使用foo和使用taskLiftT.

   const bar = taskAndT(
     taskLiftT(recChain) (Of(1)))
       (taskLiftT(recChain) (Of(2))); // yields TaskT
   

   // TASK
   
   const TaskT = taskt => record(
     TaskT,
     thisify(o => {
       o.taskt = k =>
         taskt(x => {
           o.taskt = k_ => k_(x);
           return k(x);
         });
   
       return o;
     }));
   
   // Monad
   
   const taskChainT = mmx => fmm =>
     TaskT(k =>
       mmx.taskt(x =>
         fmm(x).taskt(k)));
   
   const taskOfT = x =>
     TaskT(k => k(x));
   
   // Transformer
   
   const taskLiftT = chain => mmx =>
     TaskT(k => chain(mmx) (k));
   
   // auxiliary functions
   
   const taskAndT = mmx => mmy =>
     taskChainT(mmx) (x =>
       taskChainT(mmy) (y =>
         taskOfT([x, y])));
   
   const delayTaskT = f => ms => x =>
     TaskT(k => setTimeout(comp(k) (f), ms, x));
   
   const record = (type, o) => (
     o[Symbol.toStringTag] = type.name || type, o);
   
   const thisify = f => f({});
   
   const log = (...ss) =>
     (console.log(...ss), ss[ss.length - 1]);
   
   // TRAMPOLINE
   
   const monadRec = o => {
     while (o.tag === "Chain")
       o = o.fm(o.chain);
   
     return o.tag === "Of"
       ? o.of
       : _throw(new TypeError("unknown trampoline tag"));
   };
   
   // tags
   
   const Chain = chain => fm =>
     ({tag: "Chain", fm, chain});
   
   
   const Of = of =>
     ({tag: "Of", of});
   
   // Monad
   
   const recOf = Of;
   
   const recChain = mx => fm =>
     mx.tag === "Chain" ? Chain(mx.chain) (x => recChain(mx.fm(x)) (fm))
       : mx.tag === "Of" ? fm(mx.of)
       : _throw(new TypeError("unknown trampoline tag"));
   
   // MAIN
   
   const foo = taskOfT;
   
   const bar = taskAndT(
     taskLiftT(recChain) (Of(1)))
       (taskLiftT(recChain) (Of(2))); // yields TaskT
   
   const main = bar.taskt(x => Of(log(x))); // yields Chain({fm, chain: TaskT})
   
   monadRec(main); // yields [TaskT, TaskT] but [1, 2] desired

---

^[1] 为什么Haskell中没有IO转换器？