递归类型
计算机编程语言
在计算机编程语言,一个递归类型(也被称为递归定义,电感定义或感应数据类型)是一种数据类型,选择那些包含相同类型的其它值的值。递归类型的数据通常被视为有向图
定义
在计算机编程语言中,递归类型(又名:递归定义、隐含类型或隐含定义)是一种特殊的数据类型,它表示自身内部可能包含其它的同样类型的值。
使用范例
以下是一个在Haskell中使用链表类型的一个列子:
这表示a的链表s可以是一个空表或一个cons单元包含了一个'a'(链表的“头”)和另一个链表(“尾”)。
递归不允许在Miranda语言中和Haskell的同义类型中出现,所以以下的Haskell类型是非法的:
相反地,表面上是相等的代数数据类型却是可以的:
相互递归数据类型
数据类型也可以通过相互递归来定义。最重要的基本示例是,可以根据森林(树木列表)相互递归地定义树。象征:
森林f由树木列表组成,而树木t由一对值v和森林f(其子)组成。这个定义是优雅的,并且易于抽象地工作(例如当证明有关树的属性的定理时),因为它用简单的术语表示树:一种类型的列表和一种两种类型的对。
通过内联林的定义,可以将此相互递归定义转换为单个递归定义:
树t由一对值v和树列表(它的孩子)组成。这个定义更紧凑,但有点混乱:一棵树由一对类型和另一种类型组成,需要解开才能证明结果。
在标准ML中,树和林数据类型可以相互递归地定义如下,允许空树:
参考资料
最新修订时间:2022-08-25 16:21
目录
概述
定义
使用范例
参考资料