问题标签 [mutual-recursion]

我正在用相互递归实现在 Haskell 中进行一些动态编程。

我决定使用记忆化来加快速度。

Monad.Memo 为这种情况提供了 MemoT 变压器。但它使用 Map 作为存储值的内部表示。虽然这给了我数量级的速度提升，但这仍然不够。

虽然 lib 支持基于数组和基于向量的实现作为内部存储，但它仅适用于简单的递归，我没有找到任何像 MemoT 这样的转换器来使用它进行相互递归。

使用基于向量的有效内部表示（如果有）进行相互递归记忆的最佳方法是什么？

我的下一个问题是关于记忆效应。所以我希望我的函数在第一次运行时会花费更多时间，而在连续运行时会花费更少的时间。但是我发现在 ghci 中运行它每次所花费的时间是相同的。所以第一次和第二次没有区别。我测量时间如下：

动态是我的功能。

完整的实现如下：

添加：

根据#liqui 评论，我尝试了 memcombinators。

所以首先是非记忆的初始实现：

然后我尝试记忆（仅更改了部分）：

结果有点悖论。它比非记忆递归实现慢 3 倍。只记住一个函数（即 fq）而不接触 fv 会使结果慢 2 倍。我用 memcombinators 记住的越多，计算就越慢。第一次和第二次调用之间再次没有区别。

也是最后一个问题。在 Monad.Memo 或 memcombinators 或 MemotTrie 之间进行选择的理由是什么？在评论中使用 last 2 是有道理的。什么情况下 Monad.Memo 是更好的选择？

我一直难以理解为什么 haskell 表达式会按预期let (x,y) = (y,1) in (x,y)收敛但导致被抛出。谁能解释一下？(1,1)fix (\(x,y)-> (y,1))<<loop>>

我有两条具有父子关系的记录：

我尝试使用以下语法初始化这些，但不起作用：

这将导致

如何在不依赖可变字段或事后复制和更新的情况下初始化这些with？

我最近开始学习 Haskell。

我在网上找到了这段代码，它返回列表中所有偶数/奇数位置的元素。

它利用了相互递归，但我似乎无法理解它在内部是如何工作的。

特别是，我不明白列表是如何向前推进和评估所有元素的。即使没有明确的索引检查，它如何检查偶数位置

有人可以提供见解吗？

我有一个 clojure 程序，其中两个函数递归地相互调用：

编译器在f1. 意思是 f2 没有定义。有没有办法declare在clojure中实现函数。我可以验证递归是否真正终止。

下面的代码返回 39，我无法理解逻辑如何工作到它到达 39 的位置。我一直得到 36 或 43。谁能一步一步列出这个程序是如何运行的？

考虑以下一对相互递归的 Coq 数据类型，它们表示Forest非空Tree的 a。每个BranchaTree都有一个额外的布尔标志，我们可以用isOK.

现在，如果我们忽略这个布尔标志，我们可以编写一对映射函数来将一个函数应用于 aForest或 a中的每个值Tree，这很好用：

但是，假设布尔值表示一些有效性检查，这在实际代码中会更复杂。所以我们首先检查布尔值，只有在必要时才真正递归。这意味着我们有三个相互递归的函数，但其​​中一个只是处理工作。不幸的是，这不起作用：

问题在于，它mapTree_bad调用了mapOKTree_bad一个实际上并不小的论点。

除了......所有mapOKTree_bad正在做的只是一些预处理后的额外步骤。这将永远终止，但 Coq 看不到这一点。为了说服终止检查器，我们可以改为定义mapOKTree_good，它是相同的，但是是本地let绑定；然后，终止检查器将看穿let-binding 并允许我们定义mapForest_goodand mapTree_good。如果我们想得到mapOKTree_good，我们可以在定义相互递归函数之后使用一个普通的旧定义，它与let-binding 具有相同的主体：

这行得通，但它并不漂亮。有什么方法可以说服 Coq 的终止检查器接受这些_bad变体，还是_good我有最好的技巧？对我有用的命令，例如Program Fixpointor Function，也是一个完全合理的解决方案。

我遇到了一个相互递归的问题。我采用的基本结构是我有一个定义类型类的模块和几个定义该类型类实例的模块。然而，每个实例都是根据所有其他实例定义的。

如果该描述有点过于抽象，这里有一些代码，其结构类似于我的代码。（我已经把它剪掉了很多，以使必要的部分变得明显，并在与整体结构无关的部分添加了一些省略号）。

我的课程如下所示：

然后我有实例

现在我可以通过将所有实例放入单个模块来简单地解决这个问题，但是我有 8 个实例，而不是我的示例中显示的 2 个实例，它们都是相互递归的。最重要的是，每个实例都非常大。这意味着生成的模块将是一个巨大的无法导航的混乱。

现在，haskell wiki 有两个解决相互递归问题的建议，但它们实际上更多的是关于相互递归类型，并且它们都不会在这里工作。

无论如何，如果不简单地组合我的所有模块，是否可以绕过这种相互递归？

我概括了clojure的loop/recur蹦床，以便它与间接递归一起工作：

但是，我必须在调用方显式调用蹦床。有没有办法让它再次隐含，就像loop/一样recur？

顺便说一句，这里是loop/ recur：

我正在尝试将以下 Haskell 代码转换为 Javascript：

虽然我很难理解($ self)。这是我到目前为止所取得的成就：

错误是Uncaught TypeError: f.runDefer(...)[1] is not a function。

这里是来源。