F# Discriminated Unions

F# Discriminated Unions:

While learning about the features of F# Discriminated Unions has to be one of the best features out there along with pattern matching and Language oriented features. The allow you to represent a complex data structure, that can be recursive, like trees for e.g.

Probably the most common Discriminated Union in F# would be an Option, where the type can have Some value of generic type or None.

type Option =
    | Some of 'a
    | None

What's great about them that then don't need to hold a value or a concrete type, can be composed of several other types, and contain members for some sorts of basic operations. Combine them with pattern matching and you can do all sorts of magic.

So let's build a Tree type in F#:

A tree can have a Leaf and a Node.

- Leaf can have a value.

- Node is composed of two other Tree types being a Node or Leaf

type Tree<'t> =
    | Leaf of 't
    | Node of Tree<'t> * Tree<'t>;

And that's it we can start writing trees, and analyzing them if needed, but let's add some members here also.
What we would need is the ability to print a tree in a readable format, and possibly generate one by passing the depth that we want.

Let's add those members to the Tree type.

member tree.Print = 
        let rec print n pad =
            match n with
            | Node(x,y) ->; printfn "%sNode" pad; print x (pad + " "); print y (pad + " ");  
            | Leaf(x) ->; printfn "%sLeaf %A" pad x;
        print tree ""

What's going on here?

We create a member that traverses the using pattern matching and prints the tree, the pad parameter is used to produce a nice view of the nesting of the elements.

member tree.Generate depth =
        let rec generate depth expr =
            match depth with
            | 0 -> expr; 
            | _ -> generate (depth - 1) (Node(expr, expr));
        generate depth tree

Again using pattern matching we create an expression that represents our tree, and using recursion we pass the expr to the node if the depth parameter is not equal zero.

So the whole code for this type looks like this:

type Tree<'t> =
    | Leaf of 't
    | Node of Tree<'t> * Tree<'t>
    member tree.Print = 
        let rec print n pad =
            match n with
            | Node(x,y) -> printfn "%sNode" pad; print x (pad + " "); 
            print y (pad + " ");  
            | Leaf(x) -> printfn "%sLeaf %A" pad x;
        print tree ""
    member tree.Generate depth =
        let rec generate depth expr =
            match depth with
            | 0 -> expr; 
            | _ -> generate (depth - 1) (Node(expr, expr));
        generate depth tree

Using just a few lines of  expressive code we created a whole tree structure with members.

Now let's test the tree:

let (t:Tree<int>) = Node(Leaf 1, Leaf 2)
let genTest = t.Generate(4)
let printTest = t.Print

printfn "%A" (genTest)

This was very brief introduction into F#  Discriminated Unions, as with this feature many thing's are possible like creating ASTs and using other F# features creating whole DSL languages, but what was covered here should come in handy to anyone interested in F# programming, and Tree structures.