递归歧视的联合

递归类型

受歧视的联合可以是递归的，也就是说它们可以在其定义中引用自己。这里的主要例子是树：

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