问题标签 [mutual-recursion]

你好！我编写了这个函数，但我需要在不使用任何List.*内置函数的情况下编写它。由于有一个调用外部函数的内部函数，我假设我必须定义两个相互递归的函数。

定义一个 concat 函数似乎很容易：

问题是，我被困在产生 concat 参数的函数的定义上：

我似乎无法设计出合适的解决方案。你能帮助我吗？

编辑：例如，给定这个输入

我想要这个输出：

我正在用 c++ 重写一个最初的 java 程序，并且我遇到了两个定义相互依赖的特定类的问题。遇到问题后，我google了一下，发现了前向声明。我尝试使用它，但它失败了。

问题是：两个类都使用另一个类的成员和函数，而不仅仅是指针，因此前向声明不起作用。所以我不断收到“不完整类型的无效使用”错误，以及“前向声明”错误。

关于如何解决这个问题的任何想法？

ps 我确实意识到这可能不是很好的结构，并且可以改善类之间的关系，但我希望它尽可能接近原始实现。

在一个在线课程中，Kyle Simpson 说下面的代码演示了在 javascript 中提升的必要性，因为如果不提升，“其中一个函数总是被声明得太晚”。

但这工作得很好。

那么故事是什么？抛开调用的方便和位置不谈，有什么需要吊装的情况吗？

1 背景

考虑下面的 Haskell 片段：

注意关于r1是如何相互递归的r2。AFAIK，这在 Haskell 中完全没问题（只要你不使用这两个值导致相互递归的调用循环永远不会终止）。例如，用户r2可能希望f1 r1通过f1 (f2 r2)（在本例中为“val1”）访问该值。（事实上​​，这就是我尝试在自己的代码中使用这些类型的数据结构的方式。）

2 问题

现在考虑以下 HSpec 单元测试：

这会导致测试编译器停止一段时间，然后最终失败。 这是否意味着我的代码有问题，或者这只是shouldBe定义方式的一个怪癖（我假设它检查相等性的方式不是懒惰的，并且涉及相互递归的非终止调用） ? 如果这只是 HSpecshouldBe函数的一个怪癖，那么有没有办法检查相互递归值之间的相等性？我最终希望能够做的事情如下：

我在 Haskell 中编写优先级攀升算法，但由于我不知道的原因，它不起作用。我认为 Parsec 状态信息在某些时候会丢失，但我什至不知道这是错误的根源：

由于某种原因，我的程序仅根据情况处理第一个操作或第一个操作数，但没有进一步处理

GHCi 会话：

我知道在 C++ 中为成员变量递归定义类型的问题：

编译器对此抱怨，因为不可能以这种递归方式分配内存。

我不明白的是，这似乎也适用于函数定义：

编译器给出了同样的错误：

这是为什么？编译器需要为返回类型保留空间对我来说没有意义。我应该用指针和前向声明解决这个问题吗？根据我的经验（来自 Java），程序员使用这些递归定义来设计软件是很常见的。在 C++ 中似乎很难实现这一点。

在 F# 中，我有一个很长的代码文件，例如

换句话说，有许多相互递归的函数，每个函数都有很多参数。

现在的问题是文件有 17000 行长，Visual Studio 变得太慢了。（例如，我无法将鼠标悬停在某个项目上以查看其类型；如果我按下点，则没有完成，等等）

因此，我需要将文件拆分为许多较小的文件。但我看不到一种机械而简单的方法来做到这一点。

你能给我一个建议吗？我想要一种将代码拆分为多个文件的机械方式，这不涉及编写所有函数的类型（保留类型推断）。

我在归纳类型event上定义了三个相互递归函数，使用两种不同的方式：使用with 和fix关键字，但是，Coq 分别抱怨主要参数和The reference ... was not found in ...。函数的两种实现如下：

Coq 抱怨递归调用 round 的主要参数等于“h”而不是“tl”。尽管如此，呼叫回合中的h是e的子项。按照Recursive definitions over an inductive type中的想法，我将parentround替换为以下内容：

它现在抱怨缺少roundinc的定义。

请帮我定义这三个相互递归的函数parentround、round和roundinc。

编辑定义中有第四个函数轮次，但是到目前为止还没有问题。

我试图理解为什么以下函数对于我给它们的任何输入都输出为零。我会认为，基于将 2 输入到函数 g 的递归性质，会产生 12。我似乎用于任一函数的任何整数都只会输出 0。谁能指出我在思考过程中出错的地方？

假设以下相互递归结构：

目标：为此结构生成常见的变态：foldl，foldr，foldk。

我产生了如下的天真变态：

如何“机械地”生成尾递归 foldl（使用累加器）和尾递归 foldr（使用延续）？

我已经阅读了Scott 的递归类型和折叠系列，并且我了解如何“机械地”为递归结构生成折叠。但是我在谷歌上找不到任何东西来为递归数据结构做“机械”的事情。

PS：可以通过内联来摆脱上面的相互递归，但让我们保留它，因为它代表了tpetricek 的 Markdown 解析器中相互递归的简化版本。