haskell - 所有递归结构都可以用非递归解决方案代替吗？

Question

例如，您可以在 Haskell 中定义一个列表而不定义递归结构吗？或者用某些函数替换所有列表？

data List a = Empty | (a, List a) -- <- recursive definition

编辑

我给出了列表作为示例，但我实际上是在询问所有一般数据结构。也许我们只需要一种递归数据结构来满足所有需要递归的情况？就像 Y 组合器是唯一需要的递归函数一样。 @TikhonJelvis 的回答让我思考这一点。现在我很确定这篇文章更适合 cs.stackexchange。

关于当前选择的答案

我真的在寻找看起来更像@DavidYoung 和@TikhonJelvis 给出的答案，但他们只给出了部分答案，我很欣赏他们。因此，如果有人有使用函数概念的答案，请分享。

Answer 1

这个问题有点奇怪。我认为答案是并非如此，但是数据类型的定义不必直接递归。

最终，列表是递归数据结构。如果没有某种递归某处，您就无法定义它们。这是其本质的核心。

但是，我们不必使 List 的实际定义递归。相反，我们可以将递归分解为单个数据类型 Fix，然后用它定义所有其他递归类型。从某种意义上说，Fix 只是捕获了数据结构递归的本质。 (这是 fix 函数的类型级版本，它对函数执行相同的操作。)

data Fix f = Roll (f (Fix f))

这个想法是，Fix f 对应于重复应用于自身的 f。为了使其与 Haskell 的代数数据类型一起工作，我们必须在每个级别引入一个 Roll 构造函数，但这不会改变类型所代表的内容。

本质上，f像这样重复地应用于自身，这就是递归的本质。

现在我们可以定义一个与 List 类似的非递归类，它需要一个额外的类型参数 f 来替换我们之前的递归:

data ListF a f = Empty | Cons a f

这是一种简单的数据类型，不是递归的。

如果我们将两者结合起来，我们就会得到旧的 List 类型，除了在每个递归步骤中使用一些额外的 Roll 构造函数。

type List a = Fix (ListF a)

这种类型的值如下所示:

Roll (Cons 1 (Roll (Cons 2 (Roll Empty))))

它携带与 (Cons 1 (Cons 2 Empty)) 相同的信息，甚至只是 [1, 2]，但散布了一些额外的构造函数。

因此，如果给您 Fix，您可以在不使用递归的情况下定义 List。但这并不是特别特别，因为从某种意义上来说，Fix 就是递归。