如何为继续单元实现堆栈安全的chainRec操作符？ [英] How to implement a stack-safe chainRec operator for the continuation monad?
问题描述
我目前正在试验延续monad。
当我们处理一元递归时，总是有堆栈溢出的风险，因为递归调用不在尾部位置：
const chain = g => f => k => g（x => f（x）（k））; const = 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 运算符，用于对一些单子进行尾递归单子计算。所以我试图在Javascript中实现 chainRec ，主要根据幻想地形规范： data-lang =jsdata-hide =falsedata-console =truedata-babel =false>
const chain = g => f => k => g（x => f（x）（k））; const = 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（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？
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？ （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规范或者两者兼而有之或者都没有？
通过从不同角度观察问题并给予接受，两种答案都非常有帮助。既然我只能接受一个 - 嘿，stackoverflow，世界并不那么简单！ - 我不接受任何。
我搞乱了
chainRec，或者误解了FantasyLand规范，或者两者兼而有之或者都没有？
，或者至少是第一个。请注意，类型应该是
chainRec :: ChainRec m => （（a→c，b→c，a）→m c，a）→> mb
其中 m 是 Cont 和 c 是您的完成/循环包装器，位于 a 或 b ：
chainRec ::（（a - > DL ab，b - > DL ab，a） - > Cont（DL ab），a） - > Cont b
但您的 chainRec 和 repeat 实现根本不使用延期！
如果我们实现这种类型，没有要求它应该需要不变的堆栈空间，它看起来像
const chainRec = f => x => k => （step.value）（k）
（循环，完成，x）（步骤=>
step.done
？k（step.value） chainRec（f）（step.value）（k）
）;
或者如果我们放弃了懒惰需求（类似于转换 chain < （x => f（x）（k））从 g => f => k => g （f）= f（g）= f（g）= f（g）= f（g） x））（k））），它看起来像
const chainRec = f => ; x => （step.value）
：chainRec（f）（step.value）$ b（循环，完成，x）（step =>
step.done
？ $ b）;
甚至是放弃完成/循环
const join = chain（id）;
const chainRec = f => x => join（f（chainRec（f），of，x））;
（我希望我不会太过分，但它完美地呈现 ChainRec ）
通过懒惰延续和非递归蹦床，我们会写 p>
const chainRec = f => x => k => {
让step = Loop（x）;
do {
step = f（Loop，Done，step.value）（id）;
// ^^^^ unwrap Cont
} while（！step.done）
return k（step.value）; //（step.value）（k）
};
循环语法（初始化 step f 调用， do / while 而不是 do ）doesn真的很重要，你也很好，但重要的是 f（循环，完成，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)
这篇关于如何为继续单元实现堆栈安全的chainRec操作符？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
