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]
```

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
```

This modified text is an extract of the original Stack Overflow Documentation created by following contributors and released under CC BY-SA 3.0

This website is not affiliated with Stack Overflow