如何为延续 monad 实现堆栈安全的 chainRec 运算符? [英] How to implement a stack-safe chainRec operator for the continuation monad?
问题描述
我目前正在试验延续 monad.Cont 实际上在 Javascript 中很有用，因为它从回调模式中抽象出来.
当我们处理一元递归时，总会有堆栈溢出的风险，因为递归调用不在尾部位置:
const chain = g =>f＝＞k＝＞g(x => f(x) (k));= x => 的常量k＝＞k(x);const id = x =>X;const inc = x =>x + 1;const 重复 = n =>f＝＞x =>n === 0?(x) 的: 链(of(f(x))) (repeat(n - 1) (f));控制台日志(repeat(1e6) (inc) (0) (id)//堆栈溢出);然而，即使我们能够将某些情况转换为尾递归，我们仍然注定要失败，因为 Javascript 没有 TCO.因此，我们必须在某个时刻退回到循环.
puresrcipt 有一个 MonadRec 类型类，带有一个 tailRecM 操作符，可以为一些 monad 启用尾递归 monadic 计算.所以我主要是根据fantasy land规范尝试在Javascript中实现chainRec:
const chain = g =>f＝＞k＝＞g(x => f(x) (k));= x => 的常量k＝＞k(x);const id = x =>X;const 循环 = x =>({value: x, done: false});const 完成 = x =>({value: x, done: true});const chainRec = f =>x =>{让步 = f(Loop, Done, x);while (!step.done) {step = f(Loop, Done, step.value);}返回(步骤值)；};const repeat_ = n =>f＝＞x =>chainRec((Loop, Done, [n, x]) => n === 0 ? Done(x) : Loop([n - 1, f(x)])) ([n, x]);控制台日志(repeat_(1e6) (n => n + 1) (0) (id)//1000000);这行得通，但看起来很像作弊，因为它似乎绕过了单子链，从而绕过了Cont的上下文.在这种情况下，上下文只是其余的计算"，即.函数组合相反，因此返回预期值.但它对任何 monad 都有效吗?
要清楚我的意思，请查看此优秀答案中的以下代码片段:
const Bounce = (f,x) =>({ isBounce: true, f, x })const Cont = f =>({_runCont: f,链:g =>续(k =>弹跳(f，x =>弹跳(g(x)._runCont, k)))})//...const 重复 = n =>f＝＞x =>{const aux = (n,x) =>n === 0 ?Cont.of(x) : Cont.of(f(x)).chain(x => aux(n - 1, x))返回 runCont(aux(n,x), x => x)}这里chain 以某种方式被纳入递归算法，即可以发生一元效应.不幸的是，我无法破译此运算符或将其与堆栈不安全版本协调(Bounce(g(x)._runCont, k) 似乎是 f(x) (k) 部分，尽管如此).
最终，我的问题是我是否搞砸了 chainRec 的实现，或者误解了 FL 规范，或者两者都没有，或者都没有?
通过从不同的角度看待问题，两个给出的答案都非常有帮助，值得被接受.既然我只能接受一个——嘿stackoverflow，世界没那么简单！！！- 我不会接受任何.
我是否搞砸了
chainRec的实现，或者误解了 FantasyLand 规范，或者两者兼而有之?
可能两者都有，或者至少是第一个.请注意，类型应该是
<块引用>chainRec :: ChainRec m =>((a -> c, b -> c, a) -> m c, a) ->米其中 m 是 Cont 并且 c 是你在 a 或 b 上的 Done/Loop 包装器:
chainRec :: ((a -> DL a b, b -> DL a b, a) -> Cont (DL a b), a) ->续但是您的 chainRec 和 repeat 实现根本不使用 continations！
如果我们只实现那种类型，而不要求它需要恒定的堆栈空间，它看起来像
const chainRec = f =>x =>k＝＞f(Loop, Done, x)(step =>一步完成?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 =>一步完成?of(step.value):chainRec(f)(step.value));甚至丢弃 Done/Loop
const join = chain(id);const chainRec = f =>x =>加入(f(chainRec(f), of, x));(我希望我不会因为这个而走得太远，但它完美地呈现了 ChainRec 背后的想法)
使用惰性延续和非递归蹦床，我们会写
const chainRec = f =>x =>k＝＞{让步 = Loop(x);做 {step = f(Loop, Done, step.value)(id);//^^^^ 展开 Cont} while (!step.done)返回 k(step.value);//of(step.value)(k)};循环语法(用 f 调用初始化 step，do/while 而不是 do)没关系，你的也很好，但重要的是 f(Loop, Done, v) 返回一个延续.
我将把 repeat 的实现留给读者作为练习:D
(提示:如果重复函数 f 已经使用了延续，它可能会变得更有用，也更容易正确)
I am currently experimenting with the continuation monad. Cont is actually useful in Javascript, because it abstracts from the callback pattern.
When we deal with monadic recursion, there is always the risk of a stack overflow, because the recursive call isn't in tail position:
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
);
However, even if we are able to transform some cases into tail recursion we are still doomed, because Javascript doesn't have TCO. Consequently we have to fall back to a loop at some point.
puresrcipt has a MonadRec typeclass with a tailRecM operator that enables tail recursive monadic computations for some monads. So I tried to implement chainRec in Javascript mainly according to the fantasy land spec:
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
);
This works, but it looks a lot like cheating, because it seems to bypass the monadic chaining and thus Cont's context. In this case the context is just "the rest of the computation", ie. function composition in reverse and as a result the expected value is returned. But does it work for any monad?
To make it clear what I mean take a look at the following code snippet from this 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)
}
Here chain is somehow incorporated into the recursive algorithm, that is the monadic effect can occur. Unfortunately, I cannot decipher this operator or reconcile it with the stack-unsafe version (Bounce(g(x)._runCont, k) seems to be the f(x) (k) portion, though).
Ultimately, my question is if I messed up the implementation of chainRecor misunderstood the FL spec or both or none of it?
[EDIT]
Both given answers are very helpful by looking at the problem from different perspectives and deserve to be accepted. Since I can only accept one - hey stackoverflow, the world isn't that simple!!! - I won't accept any.
Did I mess up the implementation of
chainRec, or misunderstood the FantasyLand spec, or both or none of it?
Probably both, or at least the first. Notice that the type should be
chainRec :: ChainRec m => ((a -> c, b -> c, a) -> m c, a) -> m b
wherein m is Cont and c is your Done/Loop wrapper over a or b:
chainRec :: ((a -> DL a b, b -> DL a b, a) -> Cont (DL a b), a) -> Cont b
But your chainRec and repeat implementations don't use continations at all!
If we implement just that type, without the requirement that it should need constant stack space, it would look like
const chainRec = f => x => k =>
f(Loop, Done, x)(step =>
step.done
? k(step.value) // of(step.value)(k)
: chainRec(f)(step.value)(k)
);
or if we drop even the lazyness requirement (similar to transforming chain from g => f => k => g(x => f(x)(k)) to just g => f => g(f) (i.e. g => f => k => g(x => f(x))(k))), it would look like
const chainRec = f => x =>
f(Loop, Done, x)(step =>
step.done
? of(step.value)
: chainRec(f)(step.value)
);
or even dropping Done/Loop
const join = chain(id);
const chainRec = f => x => join(f(chainRec(f), of, x));
(I hope I'm not going out on a limb too far with that, but it perfectly presents the idea behind ChainRec)
With the lazy continuation and the non-recursive trampoline, we would however write
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)
};
The loop syntax (initialise step with an f call, do/while instead of do) doesn't really matter, yours is fine as well but the important part is that f(Loop, Done, v) returns a continuation.
I'll leave the implementation of repeat as an exercise to the reader :D
(Hint: it might become more useful and also easier to get right if you have the repeated function f already use continuations)
这篇关于如何为延续 monad 实现堆栈安全的 chainRec 运算符?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
