F# Discriminated Unions Recursive discriminated unions
Example
Recursive type
Discriminated unions can be recursive, that is they can refer to themselves in their definition. The prime example here is a tree:
type Tree =
| Branch of int * Tree list
| Leaf of int
As an example, let's define the following tree:
1
2 5
3 4
We can define this tree using our recursive discriminated union as follows:
let leaf1 = Leaf 3
let leaf2 = Leaf 4
let leaf3 = Leaf 5
let branch1 = Branch (2, [leaf1; leaf2])
let tip = Branch (1, [branch1; leaf3])
Iterating over the tree is then just a matter of pattern matching:
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]
Mutually dependent recursive types
One way to achieve recursion is to have nested mutually dependent types.
// 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
Defining a record type directly inside a discriminated union is deprecated:
// BAD
type Expression =
| LiteralExpr of obj
| ArithmeticExpr of {left: Expression; op:string; right: Expression}
// illegal in recent F# versions
You can use the and keyword to chain mutually dependent definitions:
// GOOD
type Arithmetic = {left: Expression; op:string; right: Expression}
and Expression =
| LiteralExpr of obj
| ArithmeticExpr of Arithmetic
