[科普中国]-递归类型

在计算机编程语言，一个递归类型（也被称为递归定义，电感定义或感应数据类型）是一种数据类型，选择那些包含相同类型的其它值的值。递归类型的数据通常被视为有向图。

递归在计算机科学中的一个重要应用是定义动态数据结构，如列表和树。递归数据结构可以响应运行时要求动态增长到任意大的大小; 相反，必须在编译时设置静态数组的大小要求。

有时，术语“归纳数据类型”用于不一定递归的代数数据类型。

简介在计算机编程语言中，递归类型（又名：递归定义、隐含类型或隐含定义）是一种特殊的数据类型，它表示自身内部可能包含其它的同样类型的值。

范例以下是一个在Haskell中使用链表类型的一个列子：

data List a = Nil | Cons a (List a)这表示a的链表s可以是一个空表或一个cons单元包含了一个'a'（链表的“头”）和另一个链表（“尾”）。

递归不允许在Miranda语言中和Haskell的同义类型中出现，所以以下的Haskell类型是非法的：

type Bad = (Int, Bad) type Evil = Bool -> Evil 相反地，表面上是相等的代数数据类型却是可以的：

data Good = Pair Int Good data Fine = Fun (Bool->Fine)相互递归数据类型数据类型也可以通过相互递归来定义。1最重要的基本示例是树，可以根据森林（树木列表）相互递归地定义树。象征：

f: [t[1], ..., t[k]]t: v f森林f由树木列表组成，而树木t由一对值v和森林f（其子）组成。这个定义是优雅的，并且易于抽象地工作（例如当证明有关树的属性的定理时），因为它用简单的术语表示树：一种类型的列表和一种两种类型的对。

通过内联林的定义，可以将此相互递归定义转换为单个递归定义：

t：v [t [1]，...，t [k]]树t由一对值v和树列表（它的孩子）组成。这个定义更紧凑，但有点混乱：一棵树由一对类型和另一种类型组成，需要解开才能证明结果。

在标准ML中，树和林数据类型可以相互递归地定义如下，允许空树：

datatype 'a tree = Empty | Node of 'a * 'a forestand 'a forest = Nil | Cons of 'a tree * 'a forest本词条内容贡献者为:

王慧维 - 副研究员 - 西南大学