F# 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