是否可以将所有递归结构都替换为非递归解决方案？

Question

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

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

编辑

我以列表为例，但我实际上是在问一般的所有数据结构。对于所有需要递归的情况，也许我们只需要一种递归数据结构？就像 Y 组合器是唯一需要的递归函数一样。 @TikhonJelvis 的回答让我想到了这一点。现在我很确定 post 更适合 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 是递归。

Answer 2

我不确定所有递归结构是否可以用非递归版本代替，但有些确实可以，包括列表。一种可能的方法是使用所谓的 Boehm-Berarducci encoding。这是一种将结构表示为函数的方法，特别是对该结构的折叠（foldr 在列表的情况下）：

{-# LANGUAGE RankNTypes #-}

type List a = forall x . (a -> x -> x) -> x -> x
                      -- ^^^^^^^^^^^^^    ^
                      -- Cons branch      Nil branch

（来自上面的link，格式略有不同）

这种类型也有点像对列表的案例分析。第一个参数表示 cons 情况，第二个参数表示 nil 情况。

一般来说，sum 类型的分支变成函数的不同参数，product 类型的字段变成函数类型，每个字段都有一个参数。请注意，在上面的编码中，nil 分支（通常）是一个非函数，因为 nil 构造函数没有参数，而 cons 分支有两个参数，因为 cons 构造函数有两个参数。定义的递归部分是 "replaced"，Rank N 类型（此处称为 x）。

Answer 3

我认为这个问题分解为考虑 Haskell 提供的三个不同的特征子集：

定义新数据类型的工具。
内置类型库。
允许与语言外部功能进行交互的外部函数接口。

只看 (1)，除了递归之外，本机类型定义工具并没有真正提供定义任何无限大的类型。

然而，查看 (2)，Haskell 2010 provides the Data.Array module，它提供了与 (1) 一起可用于构建许多不同结构的非递归定义的数组类型。

即使该语言不提供数组，(3) 也意味着我们可以将它们作为 FFI 扩展绑定到该语言。 Haskell 实现也被允许提供额外的功能来代替 FFI，许多 GHC 库利用这些功能（例如，vector）。

所以我想说最好的答案是 Haskell 只允许你定义非递归集合类型，只在它为你提供可以用作构建块的基本内置集合类型的范围内对于更复杂的。

是否可以将所有递归结构都替换为非递归解决方案？

Can all recursive structures be replaced by a non recursive solution?

f#

haskell

data-structures