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

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 是递归.

Answer 2

我不确定是否所有递归结构都可以被非递归版本替换,但有些肯定可以,包括列表.一种可行的方法是使用所谓的Boehm-Berarducci编码.这是一种将结构表示为函数的方法,特别是在该结构上的折叠(foldr在列表的情况下):

{-# LANGUAGE RankNTypes #-}

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

(从上面的链接略有不同的格式)

这种类型也类似于列表中的案例分析.第一个参数表示cons情形,第二个参数表示nil情况.

通常,sum类型的分支成为函数的不同参数,产品类型的字段变为具有每个字段的参数的函数类型.请注意,在上面的编码中,nil分支(通常)是非函数,因为nil构造函数不带参数,而cons分支有两个参数,因为cons构造函数有两个参数.定义的递归部分用Rank N类型(x在此称为)替换.