F Sharp Programming/Discriminated Unions

From Wikibooks, open books for an open world
Jump to: navigation, search
Previous: Sets and Maps Index Next: Mutable Data
F# : Discriminated Unions


Discriminated unions, also called tagged unions, represent a finite, well-defined set of choices. Discriminated unions are often the tool of choice for building up more complicated data structures including linked lists and a wide range of trees.

Creating Discriminated Unions[edit]

Discriminated unions are defined using the following syntax:

type unionName =
    | Case1
    | Case2 of datatype
    | ...

By convention, union names start with a lowercase character, and union cases are written in PascalCase.

Union basics: an On/Off switch[edit]

Let's say we have a light switch. For most of us, a light switch has two possible states: the light switch can be ON, or it can be OFF. We can use an F# union to model our light switch's state as follows:

type switchstate =
    | On
    | Off

We've defined a union called switchstate which has two cases, On and Off. You can create and use instances of switchstate as follows:

type switchstate =
    | On
    | Off
 
let x = On    (* creates an instance of switchstate *)
let y = Off   (* creates another instance of switchstate *)
 
let main() =
    printfn "x: %A" x
    printfn "y: %A" y
 
main()

This program has the following types:

type switchstate = On | Off
val x : switchstate
val y : switchstate

It outputs the following:

x: On
y: Off

Notice that we create an instance of switchstate simply by using the name of its cases; this is because, in a literal sense, the cases of a union are constructors. As you may have guessed, since we use the same syntax for constructing objects as for matching them, we can pattern match on unions in the following way:

type switchstate =
    | On
    | Off
 
let toggle = function  (* pattern matching input *)
    | On -> Off
    | Off -> On
 
let main() =
    let x = On
    let y = Off
    let z = toggle y
 
    printfn "x: %A" x
    printfn "y: %A" y
    printfn "z: %A" z
    printfn "toggle z: %A" (toggle z)
 
main()

The function toggle has the type val toggle : switchstate -> switchstate.

This program has the following output:

x: On
y: Off
z: On
toggle z: Off

Holding Data In Unions: a dimmer switch[edit]

The example above is kept deliberately simple. In fact, in many ways, the discriminated union defined above doesn't appear much different from an enum value. However, let's say we wanted change our light switch model into a model of a dimmer switch, or in other words a light switch that allow users to adjust a lightbulb's power output from 0% to 100% power.

We can modify our union above to accommodate three possible states: On, Off, and an adjustable value between 0 and 100:

type switchstate =
    | On
    | Off
    | Adjustable of float

We've added a new case, Adjustable of float. This case is fundamentally the same as the others, except it takes a single float value in its constructor:

open System
 
type switchstate =
    | On
    | Off
    | Adjustable of float
 
let toggle = function
    | On -> Off
    | Off -> On
    | Adjustable(brightness) ->
        (* Matches any switchstate of type Adjustable. Binds
        the value passed into the constructor to the variable
        'brightness'. Toggles dimness around the halfway point. *)
        let pivot = 0.5
        if brightness <= pivot then
            Adjustable(brightness + pivot)
        else
            Adjustable(brightness - pivot)
 
let main() =
    let x = On
    let y = Off
    let z = Adjustable(0.25) (* takes a float in constructor *)
 
    printfn "x: %A" x
    printfn "y: %A" y
    printfn "z: %A" z
    printfn "toggle z: %A" (toggle z)
 
    Console.ReadKey(true) |> ignore
 
main()

This program outputs:

x: On
y: Off
z: Adjustable 0.25
toggle z: Adjustable 0.75

Creating Trees[edit]

Discriminated unions can easily model a wide variety of trees and hierarchical data structures.

For example, let's consider the following binary tree:

            /\
           /  \
          1   /\
             /  \
            2   /\
               /  \
              /\   3
             /  \
            4    5

Each node of our tree contains exactly two branches, and each branch can either be a integer or another tree. We can represent this tree as follows:

type tree =
    | Leaf of int
    | Node of tree * tree

We can create an instance of the tree above using the following code:

open System
 
type tree =
    | Leaf of int
    | Node of tree * tree
 
let simpleTree =
    Node(
        Leaf 1,
        Node(
            Leaf 2,
            Node(
                Node(
                    Leaf 4,
                    Leaf 5
                ),
                Leaf 3
            )
        )
    )
 
let main() =
    printfn "%A" simpleTree
    Console.ReadKey(true) |> ignore
 
main()

This program outputs the following:

Node (Leaf 1,Node (Leaf 2,Node (Node (Leaf 4,Leaf 5),Leaf 3)))

Very often, we want to recursively enumerate through all of the nodes in a tree structure. For example, if we wanted to count the total number of Leaf nodes in our tree, we can use:

open System
 
type tree =
    | Leaf of int
    | Node of tree * tree
 
let simpleTree =
    Node (Leaf 1, Node (Leaf 2, Node (Node (Leaf 4, Leaf 5), Leaf 3)))
 
let countLeaves tree =
    let rec loop sum = function
        | Leaf(_) -> sum + 1
        | Node(tree1, tree2) ->
            sum + (loop 0 tree1) + (loop 0 tree2)
    loop 0 tree
 
let main() =
    printfn "countLeaves simpleTree: %i" (countLeaves simpleTree)
    Console.ReadKey(true) |> ignore
 
main()

This program outputs:

countLeaves simpleTree: 5

Generalizing Unions For All Datatypes[edit]

Note that our binary tree above only operates on integers. Its possible to construct unions which are generalized to operate on all possible data types. We can modify the definition of our union to the following:

type 'a tree =
    | Leaf of 'a
    | Node of 'a tree * 'a tree
 
(* The syntax above is "OCaml" style. It's common to see 
   unions defined using the ".NET" style as follows which
   surrounds the type parameter with <'s and >'s after the 
   type name:
 
type tree<'a> =
    | Leaf of 'a
    | Node of tree<'a> * tree<'a>
*)

We can use the union define above to define a binary tree of any data type:

open System
 
type 'a tree =
    | Leaf of 'a
    | Node of 'a tree * 'a tree  
 
let firstTree =
    Node(
        Leaf 1,
        Node(
            Leaf 2,
            Node(
                Node(
                    Leaf 4,
                    Leaf 5
                ),
                Leaf 3
            )
        )
    )
 
let secondTree = 
    Node(
        Node(
            Node(
                Leaf "Red",
                Leaf "Orange"
            ),
            Node(
                Leaf "Yellow",
                Leaf "Green"
            )
        ),
        Node(
            Leaf "Blue",
            Leaf "Violet"
        )
    )
 
let prettyPrint tree =
    let rec loop depth tree =
        let spacer = new String(' ', depth)
        match tree with
        | Leaf(value) ->        
            printfn "%s |- %A" spacer value
        | Node(tree1, tree2) ->
            printfn "%s |" spacer
            loop (depth + 1) tree1
            loop (depth + 1) tree2
    loop 0 tree
 
let main() =
    printfn "firstTree:"
    prettyPrint firstTree
 
    printfn "secondTree:"
    prettyPrint secondTree
    Console.ReadKey(true) |> ignore
 
main()

The functions above have the following types:

type 'a tree =
    | Leaf of 'a
    | Node of 'a tree * 'a tree
 
val firstTree : int tree
val secondTree : string tree
val prettyPrint : 'a tree -> unit

This program outputs:

firstTree:
 |
  |- 1
  |
   |- 2
   |
    |
     |- 4
     |- 5
    |- 3
secondTree:
 |
  |
   |
    |- "Red"
    |- "Orange"
   |
    |- "Yellow"
    |- "Green"
  |
   |- "Blue"
   |- "Violet"

Examples[edit]

Built-in Union Types[edit]

F# has several built-in types derived from discriminated unions, some of which have already been introduced in this tutorial. These types include:

type 'a list = 
    | Cons of 'a * 'a list
    | Nil
 
type 'a option =
    | Some of 'a
    | None

Propositional Logic[edit]

The ML family of languages, which includes F# and its parent language OCaml, were originally designed for the development of automated theorem provers. Union types allow F# programmers to represent propositional logic remarkably concisely. To keep things simple, lets limit our propositions to four possible cases:

type proposition =
    | True
    | Not of proposition
    | And of proposition * proposition
    | Or of proposition * proposition


Let's say we had a series of propositions and wanted to determine whether they evaluate to true or false. We can easily write an eval function by recursively enumerating through a propositional statement as follows:

let rec eval = function
    | True -> true
    | Not(prop) -> not (eval(prop))
    | And(prop1, prop2) -> eval(prop1) && eval(prop2)
    | Or(prop1, prop2) -> eval(prop1) || eval(prop2)

The eval function has the type val eval : proposition -> bool.

Here is a full program using the eval function:

open System
 
type proposition =
    | True
    | Not of proposition
    | And of proposition * proposition
    | Or of proposition * proposition
 
let prop1 =
    (* ~t || ~~t *)
    Or(
        Not True,
        Not (Not True)
    )
 
let prop2 =
    (* ~(t && ~t) || ( (t || t) || ~t) *)
    Or(
        Not(
            And(
                True,
                Not True
            )
        ),
        Or(
            Or(
                True,
                True
            ),
            Not True
        )
    )
 
let prop3 = 
    (* ~~~~~~~t *)
    Not(Not(Not(Not(Not(Not(Not True))))))
 
let rec eval = function
    | True -> true
    | Not(prop) -> not (eval(prop))
    | And(prop1, prop2) -> eval(prop1) && eval(prop2)
    | Or(prop1, prop2) -> eval(prop1) || eval(prop2)
 
let main() =
    let testProp name prop = printfn "%s: %b" name (eval prop)
 
    testProp "prop1" prop1
    testProp "prop2" prop2
    testProp "prop3" prop3
 
    Console.ReadKey(true) |> ignore
 
main()

This program outputs the following:

prop1: true
prop2: true
prop3: false

Additional Reading[edit]

Theorem Proving Examples (OCaml)

Previous: Sets and Maps Index Next: Mutable Data