语言中出现递归类型时是否需要折叠和展开？

Question

语言中出现递归类型时是否需要

fold

和

unfold

？我正在阅读 Benjamin C. Pierce 所著的《类型和编程语言》一书。第 4 节“递归类型”介绍了扩展递归类型的特殊术语

fold

和

unfold

。但是我们可以显式检查构造函数属于什么类型，并检查所有匹配的模式是否都是该类型的构造函数。或者只有当递归类型始终通过 Haskell 或 ocaml 中的变体类型定义时，这才有效？为什么 Haskell 不允许你定义非变体类型的递归类型？

Answer 1

Pierce 在具有“等递归类型”的语言上下文中引入了

fold

和

unfold

术语，但指出等递归类型（包括这些术语）和等递归类型（不包括这些术语）都是在理论上和实践中都已使用的合理方法。所以，我认为这就是你的答案：使用等递归类型的编程语言不需要

fold

或

unfold

术语。

请注意，Haskell 非常明显地属于等递归阵营。整数列表的类型（皮尔斯称之为

IntList

）及其一步展开的类型（皮尔斯称之为

<nil:Unit,cons:{Int,IntList}>

）的变体类型与 Haskell 中的相同类型，即类型

[Int]

。因此，Haskell 没有皮尔斯所说的那种

fold

或

unfold

术语。

请注意，这与标准库中是否有

fold

或

unfold

“函数”、显式检查构造函数属于什么类型的能力或是否存在变体类型几乎没有关系。

变体类型在这里可能很重要的唯一原因是，如果没有some类型的和类型，就很难充分利用递归类型，就像在没有至少一个基本情况的情况下很难编写递归函数一样递归。变体类型是一种方便的求和类型，但不是绝对必要的。 Lisp S 表达式可能会被视为等递归类型，而不是变体类型。

Haskell 要求将递归类型定义为变体类型的原因是，Haskell 本质上要求所有新类型被定义为“变体类型”（即标记联合），即使在类型只有一个变体的小情况下，例如:

data Pos = Pos Int Int
           ^^^- one variant!

唯一的例外是一些原始的未装箱类型（例如，

Int#

），它们都不是递归的。