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

落叶无声 阅读:13 2024-12-31 21:38:35 评论:0

我目前正在试验延续 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,世界没那么简单!!! - 我不会接受任何。

请您参考如下方法:

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 


其中 mCont 并且 c 是你在 ab 上的 Done/Loop 包装器:
chainRec :: ((a -> DL a b, b -> DL a b, a) -> Cont (DL a b), a) -> Cont b 

但是你的 chainRecrepeat 实现根本不使用 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) 
  ); 

或者如果我们甚至放弃惰性要求(类似于将 chaing => 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 调用初始化 fdo/while 而不是 do )并不重要,你的也很好,但重要的部分是 f(Loop, Done, v) 返回一个延续。

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


标签:JavaScript
声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

关注我们

一个IT知识分享的公众号