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
其中
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
已经使用延续,它可能会变得更有用,也更容易正确)
声明
1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。