遞歸類型

在計算機程式語言，一個遞歸類型（也被稱為遞歸定義，電感定義或感應數據類型）是一種數據類型，選擇那些包含相同類型的其它值的值。遞歸類型的數據通常被視為有向圖。

遞歸在計算機科學中的一個重要套用是定義動態數據結構，如列表和樹。遞歸數據結構可以回響運行時要求動態增長到任意大的大小; 相反，必須在編譯時設定靜態數組的大小要求。

有時，術語“歸納數據類型”用於不一定遞歸的代數數據類型。

基本介紹

• 中文名：遞歸類型
• 外文名：Recursive data type
• 學科：計算機科學

簡介

在計算機程式語言中，遞歸類型（又名：遞歸定義、隱含類型或隱含定義）是一種特殊的數據類型，它表示自身內部可能包含其它的同樣類型的值。

範例

以下是一個在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)

相互遞歸數據類型

數據類型也可以通過相互遞歸來定義。最重要的基本示例是樹，可以根據森林（樹木列表）相互遞歸地定義樹。象徵：

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