-
遞歸類型
鎖定
遞歸在計算機科學中的一個重要應用是定義動態數據結構，如列表和樹。遞歸數據結構可以響應運行時要求動態增長到任意大的大小; 相反，必須在編譯時設置靜態數組的大小要求。
有時，術語“歸納數據類型”用於不一定遞歸的代數數據類型。
- 中文名
- 遞歸類型
- 外文名
- Recursive data type
- 學 科
- 計算機科學
遞歸類型定義
遞歸類型使用範例
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
