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

Question

例如，你可以在没有定义递归结构的情况下在Haskell中定义一个列表吗？或者用一些函数替换所有列表？

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

编辑

我给列表作为一个例子，但我真的问一般所有的数据结构。 也许我们只需要一个递归数据结构来处理需要递归的所有情况？就像Y combinator是唯一需要的递归函数一样。 @TikhonJelvis的回答让我想到了这一点。 现在我很确定这篇文章更适合cs.stackexchange。

关于当前选择的答案

我真的找了一个看起来更像@DavidYoung & @TikhonJelvis给出的那些答案，但他们只给了部分答案，我很欣赏他们。 所以，如果有任何使用功能概念的答案，请分享。

Answer 1

我认为这个问题分解成考虑到Haskell中提供了三种不同功能的子集：

1. 设施定义新的数据类型。
2. 内置类型的曲目。
3. 允许与语言外部功能接口的外部函数接口。

只看（1），本机类型定义工具并不真正提供除递归以外的任何无限大类型的定义。 （2），然而，Haskell 2010 provides the Data.Array module，它提供的数组类型与（1）一起可以用来构建许多不同结构的非递归定义。即使语言没有提供数组，（3）意味着我们可以将它们作为FFI扩展插入到语言中。 Haskell实现还允许提供可用于此的额外功能，而不是FFI，许多GHC库都利用这些功能（例如，vector）。

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

Answer 2

这是一个奇怪的问题。我认为答案是不是真的，但数据类型的定义不必直接递归。

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

但是，我们不必对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 3

我不确定是否全部递归结构可以被非递归版本替换，但一些肯定可以，包括列表。一种可能的方法是使用所谓的Boehm-Berarducci encoding。这一种方式来表示的结构作为一个函数，具体地折叠在该结构（foldr在列表中的情况下）：

{-# LANGUAGE RankNTypes #-} 

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

（来自具有稍微不同的格式以上的链接）

这种类型也是类似于列表中的案例分析。第一个参数代表cons情况，第二个参数代表无情况。

通常，和类型的分支变成函数的不同参数，并且产品类型的字段变为具有每个字段的参数的函数类型。请注意，在上面的编码中，nil分支（通常）是非函数，因为nil构造函数不接受任何参数，而cons分支有两个参数，因为cons构造函数接受两个参数。定义的递归部分用“N”类型（这里称为x）“替换”。