javascript - 如何为延续 monad 实现堆栈安全的 chainRec 运算符？

Question

我目前正在试验延续 monad。 Cont 实际上在 Javascript 中很有用，因为它从回调模式中抽象出来。

当我们处理 monadic 递归时，总会有堆栈溢出的风险，因为递归调用不在尾部位置:

const chain = g => f => k =>
  g(x => f(x) (k));

const of = x => k =>
  k(x);
  
const id = x =>
  x;

const inc = x =>
  x + 1;

const repeat = n => f => x => 
  n === 0
    ? of(x)
    : chain(of(f(x))) (repeat(n - 1) (f));

console.log(
  repeat(1e6) (inc) (0) (id) // stack overflow
);

但是，即使我们能够将某些情况转换为尾递归，我们仍然注定失败，因为 Javascript 没有 TCO。因此，我们必须在某个时刻退回到循环。

puresrcipt 有一个带有 MonadRec 操作符的 tailRecM 类型类，它可以为某些 monad 启用尾递归 monadic 计算。所以我尝试主要根据fantasy land规范在Javascript中实现 chainRec:

const chain = g => f => k => g(x => f(x) (k));
const of = x => k => k(x);
const id = x => x;

const Loop = x =>
  ({value: x, done: false});

const Done = x =>
  ({value: x, done: true});

const chainRec = f => x => {
  let step = f(Loop, Done, x);

  while (!step.done) {
    step = f(Loop, Done, step.value);
  }

  return of(step.value);
};

const repeat_ = n => f => x => 
  chainRec((Loop, Done, [n, x]) => n === 0 ? Done(x) : Loop([n - 1, f(x)])) ([n, x]);

console.log(
  repeat_(1e6) (n => n + 1) (0) (id) // 1000000
);

这有效，但它看起来很像作弊，因为它似乎绕过了 monadic 链接，从而绕过了 Cont 的上下文。在这种情况下，上下文只是“计算的其余部分”，即。函数组合相反，因此返回预期值。但它对任何 monad 都有效吗？

为了清楚我的意思，请查看此 outstanding answer 中的以下代码片段:

const Bounce = (f,x) => ({ isBounce: true, f, x })

const Cont = f => ({
  _runCont: f,
  chain: g =>
    Cont(k =>
      Bounce(f, x =>
        Bounce(g(x)._runCont, k)))
})

// ...

const repeat = n => f => x => {
  const aux = (n,x) =>
    n === 0 ? Cont.of(x) : Cont.of(f(x)).chain(x => aux(n - 1, x))
  return runCont(aux(n,x), x => x)
}

这里 chain 以某种方式合并到递归算法中，即可以发生一元效应。不幸的是，我无法破译此运算符或将其与堆栈不安全版本协调(尽管 Bounce(g(x)._runCont, k) 似乎是 f(x) (k) 部分)。

最终，我的问题是我是否搞砸了 chainRec 的实现或误解了 FL 规范，或者两者兼而有之？

[编辑]

通过从不同的 Angular 看待问题，两个给出的答案都非常有帮助，值得被接受。由于我只能接受一个 - 嘿stackoverflow，世界没那么简单!!! - 我不会接受任何。

Answer 1

Did I mess up the implementation of chainRec, or misunderstood the FantasyLand spec, or both or none of it?

可能两者都有，或者至少是第一个。注意 the type should be

chainRec :: ChainRec m => ((a -> c, b -> c, a) -> m c, a) -> m b

其中 m 是 Cont 并且 c 是你在 a 或 b 上的 Done/Loop 包装器:

chainRec :: ((a -> DL a b, b -> DL a b, a) -> Cont (DL a b), a) -> Cont b

但是你的 chainRec 和 repeat 实现根本不使用 continations!

如果我们只实现那种类型，而不要求它需要恒定的堆栈空间，它看起来像

const chainRec = f => x => k =>
  f(Loop, Done, x)(step =>
    step.done
      ? k(step.value) // of(step.value)(k)
      : chainRec(f)(step.value)(k)
  );

或者如果我们甚至放弃惰性要求(类似于将 chain 从 g => f => k => g(x => f(x)(k)) 转换为 g => f => g(f) (即 g => f => k => g(x => f(x))(k) ))，它看起来像

const chainRec = f => x =>
  f(Loop, Done, x)(step =>
    step.done
      ? of(step.value)
      : chainRec(f)(step.value)
  );

甚至丢弃 Done/Loop

const join = chain(id);
const chainRec = f => x => join(f(chainRec(f), of, x));

(我希望我不会因为这个而走得太远，但它完美地呈现了 ChainRec 背后的想法)

有了惰性延续和非递归蹦床，我们会写

const chainRec = f => x => k => {
  let step = Loop(x);
  do {
    step = f(Loop, Done, step.value)(id);
//                                  ^^^^ unwrap Cont
  } while (!step.done)
  return k(step.value); // of(step.value)(k)
};

循环语法(使用 step 调用初始化 f， do/while 而不是 do )并不重要，你的也很好，但重要的部分是 f(Loop, Done, v) 返回一个延续。

我将 repeat 的实现留给读者作为练习:D
(提示:如果重复函数 f 已经使用延续，它可能会变得更有用，也更容易正确)