遞迴歧視的聯合

遞迴型別

受歧視的聯合可以是遞迴的，也就是說它們可以在其定義中引用自己。這裡的主要例子是樹：

type Tree =
    | Branch of int * Tree list
    | Leaf of int

例如，讓我們定義以下樹：

    1
  2   5
3   4

我們可以使用遞迴區分聯合來定義這個樹，如下所示：

let leaf1 = Leaf 3
let leaf2 = Leaf 4
let leaf3 = Leaf 5

let branch1 = Branch (2, [leaf1; leaf2])
let tip = Branch (1, [branch1; leaf3])

然後迭代樹只是模式匹配的問題：

let rec toList tree =
    match tree with
    | Leaf x -> [x]
    | Branch (x, xs) -> x :: (List.collect toList xs)

let treeAsList = toList tip // [1; 2; 3; 4; 5]

相互依賴的遞迴型別

實現遞迴的一種方法是巢狀相互依賴的型別。

// BAD
type Arithmetic = {left: Expression; op:string; right: Expression}
// illegal because until this point, Expression is undefined
type Expression = 
| LiteralExpr of obj
| ArithmeticExpr of Arithmetic

不建議直接在區分聯合內定義記錄型別：

// BAD
type Expression = 
| LiteralExpr of obj
| ArithmeticExpr of {left: Expression; op:string; right: Expression}
// illegal in recent F# versions

你可以使用 and 關鍵字連結相互依賴的定義：

// GOOD
type Arithmetic = {left: Expression; op:string; right: Expression}
and Expression = 
| LiteralExpr of obj
| ArithmeticExpr of Arithmetic