问题标签 [tailrecursion-modulo-cons]

我正在用 Haskell 创建一个简单的解析库，它使用 Template Haskell 将解析器规范编译为优化的代码。

但是，我试图弄清楚哪种代码对优化最有效，所以让我们考虑一个简单的解析器编写的解析器片段。

解析器可以看作是一个函数String -> (a, String)，其中a是我们在解析过程中想要识别的任何内容，而生成的字符串是我们未匹配的输入的任何部分。当解析器按顺序运行时，下一个解析器应该继续处理这个字符串。最后，如果最终结果是 shape ，我们可以说成功解析了一个完整的字符串("", _)。

在此示例中，我们将使用解析任意数量的“a”字符的解析器。 _{（错误处理，即如果看到除“a”以外的任何字符时报告错误，已被排除在代码片段之外，以保持一切简洁，以使问题清晰）。}

直截了当（天真的？）实施

如果我们用解析器编写递归解析器的代码，一个简单的手动实现可能是：

这匹配任意数量的'a''。解析器递归直到字符串为空。

查看创建的 GHC Core，我们看到以下输出：

在我未经训练的眼里，这似乎不是尾递归，因为我们首先进行递归调用，然后仍然需要将输出组合成一个元组。我还觉得奇怪/有趣的是let，源代码中的 仍然存在于编译代码中，这使得计算看起来确实需要在多个（即非尾递归）步骤中完成。

我想到了另外两种编写此代码的方法。（也许还有更多？）

续传风格

这导致：

从我们执行尾调用的意义上说，这看起来是尾递归的。然而，结果似乎确实是一个巨大的重击。在到达递归的基础之前，我们是否使用了大量额外的堆空间？

国家单子

这导致：

在这里，我不确定如何解释核心：-code 的 Thelet消失parser_raw了。相反，递归调用立即在case. 之后我们仍然需要将结果放入一个元组中，但是这个“无缺点”是否足以取悦递归之神？

所以，总结一下：这是编写简单解析函数的三种技术。我想知道其中哪一个是最节省内存的，以及如何通过查看 GHC 核心输出来获得一些直觉来识别尾递归。