问题标签 [continuation-passing]

首先是一些背景：我正在玩这个优秀KFoldTree的博客文章。我有一个 n 元而不是二进制的树结构。使用二叉树，将 CPS 变换应用于传递给的函数KFoldTree并不难。你最终会得到类似的东西：

n 叉树的问题是你必须即时构建这个延续链。你想要结束的应该是这样的：

其中children是折叠结果类型的列表。例如，如果我正在编写一个漂亮的打印机，children应该是 type string list，而kchildren应该是 type (string list -> string) -> string。

那么我们如何定义一个产生 的函数kchildren，给定一个((Node -> string) -> string) list（继续漂亮的打印机示例）？

我看不到 spray 的指令如何与continuation pass style (CPS)相对应。

更具体地说，延续是（在 Haskell 中），但是当使用喷射指令（其类型为where ）时(a -> r) -> r，我找不到这种类型（ ）在哪里。(a -> r) -> rRoute->Routetype Route = RequestContext => Unit

也不相似Route->Route， 那么指令与CPS有什么关系呢？type Route = RequestContext => Unit(a -> r) -> r

有人可以展示喷雾的指令如何对应于延续传递风格吗？

Expert F# 3.0一书的第 9 章展示了在遍历二叉树时如何使用连续传递样式来避免堆栈溢出。我编写的树遍历代码几乎与书中的代码相同，但我仍然得到堆栈溢出。我的代码如下：

将此加载到 F# 交互式环境中并计算表达式sizeContAcc leftLeaningTree6会使堆栈溢出。为什么是这样？

我无法理解 Scheme 中收集器函数的使用。我正在使用“The Little Schemer”一书（Daniel P. Friedman 和 Matthias Felleisen 着）。一个带有一些解释的综合示例将对我有很大帮助。使用收集器函数的函数示例如下：

...以示例调用 being(identity '(a b c) self)和 the self-functionBeing (define self (lambda (x) x))。该identity函数返回给定的列表l，因此给定调用的输出将是(a b c)。使用的确切语言是 R5RS Legacy 语言。

定义了一个函数 fact 以在延续传递样式中找到阶乘，

打电话给，

在使用断点之后，我了解到在我们调用此函数后，程序执行为

n = 4，事实（4，外部），然后

n = 4，事实（3，内部（t0）），然后

n = 3，事实（2，内部（t0）），然后

n = 2, fact(1,inner(t0)) 然后

我的乐趣(1)

在此之后我无法理解，myFun(1) 中的 1 值如何传递给 t0

（后来的访问者：这个问题的两个答案都给出了很好的见解，如果你有兴趣，你可能应该同时阅读它们，我只能将一个作为 SO 的限制除外）

从我在网上找到的关于 continuation monad 的所有讨论中，他们要么提到了如何将它与一些琐碎的例子一起使用，要么他们解释说它是一个基本的构建块，就像这篇关于所有 monad 之母的文章中的 continuation monad一样。

我想知道是否有超出这个范围的适用性。我的意思是，在延续单子中包装递归函数或相互递归是否有意义？它有助于可读性吗？

这是取自此 SO 帖子的延续模式的 F# 版本：

它仅仅是学术兴趣，例如帮助理解单子或计算构建器？还是有一些现实世界的适用性，增加了类型安全性，或者它是否规避了其他难以解决的典型编程问题？

即，来自 Ryan Riley 的带有 call/cc 的 continuation monad表明处理异常很复杂，但它没有解释它试图解决什么问题，并且示例也没有说明为什么它特别需要这个 monad。诚然，我只是不明白它的作用，但它可能是一个宝库！

（注意：我对了解 continuation monad 的工作原理不感兴趣，我想我对它有相当的了解，只是看不出它解决了什么编程问题。）

它无法'a在编译时解决的错误消息对我来说非常清楚。我猜测是否可以使上述工作的问题的答案是否定的，没有直接将函数添加到数据类型中。但那我不妨使用一个接口，或者完全摆脱泛型参数。

编辑：马克的回复确实符合我的要求，但让我扩展这个问题，因为我没有充分解释它。我想要做的是使用上面的技术来模仿这篇文章中所做的事情。这样做的动机是避免内联函数，因为它们的可组合性很差——如果没有专门的通用参数，它们就不能作为 lambdas 传递。

我希望我可以通过将带有通用参数的联合类型传递给闭包来解决它，但是......

最后一行给出了一个类型错误。有没有解决的办法？尽管由于它们对可组合性的限制，我更希望函数不要被内联。

我有一个想要以尾递归形式编写的函数。该函数计算k通过掷骰子s次数获得总和的方法数n。我已经在这个答案上看到了这个函数的数学解决方案。如下：

我在 R 中的参考递归实现是：

正如我从这个答案中学到的那样，我试图以连续传递风格重新编写函数，但我没有成功。有没有办法以尾递归的形式编写这个函数？

编辑

我知道 R 没有针对尾递归进行优化。我的问题不是 R 特定的，任何其他语言的解决方案同样受欢迎。即使它是一种没有针对尾递归进行优化的语言。

我尝试将此代码转换为 CPS 表单：

我是 scala 的新手，在理解语法方面遇到了很大的问题。如果你给我一些语法来解决这个任务会很有帮助

这是我的代码类型不匹配：

我正在尝试使用parsec编写以下解析器：

这就像many函数一样，但不是返回[a]，而是返回成功的次数Parser a。

这行得通，但我似乎无法让它在恒定的堆空间中运行。这是有道理的，因为递归调用go不在尾部调用位置。

如果 parsec 将构造函数导出到ParsecT，则可以以manyLengthCPS 的形式重写。这与函数非常相似manyAccum ：

此manyLengthCPS函数确实在恒定堆空间中运行。

这是ParsecT为了完整性的构造函数：

我还尝试manyLengthCPS使用低级函数直接变成非 CPSmkPT函数：

就像manyLength,manyLengthLowLevel不在恒定堆空间中运行。

是否可以编写manyLength使其在恒定堆空间中运行，即使没有以 CPS 样式编写它？如果不是，为什么不呢？是否有一些基本原因可以在 CPS 样式中但在非 CPS 样式中是可能的？