F# 8 Discriminated Unions

OK so our F# journey continues. We have looked at some of the basic building block types such as Records/Tuples, it is now time to look at Discriminated Unions.

Discriminated unions provide support for values that can be one of a number of possible values. The possible values are known as “union cases”, and take the form shown below

case-identifier1 [of [ fieldname1 : ] type1 [ * [ fieldname2 : ] type2 …]

Don’t worry if this syntax looks scary, what it really boils down to is having a label such that each case can be recognized (discriminated) from the others, and a type for the union case. The label name has certain rules around it such as:

• Must start with an uppercase letter
• Can be an identifier including the union case type name itself. Which can be a little confusing, but does have the benefit of describing the union case quite well

Here is an example of a bad identifier:

And here is what something may look like when using a label identifier which is the same as the union case, which as previously stated is perfectly valid:

type LabelUnionType = Int of int | String of string

Constructing Discriminated Unions

So how does one construct a union case. Well there are various ways, you are able to use one of the following approaches:

let currentLabelUnionType1 =   13
printfn "let currentLabelUnionType1 =   13" 
printfn "%O" currentLabelUnionType1
   
let currentLabelUnionType2 =  Int 23
printfn "let currentLabelUnionType2 =  Int 23" 
printfn "%O" currentLabelUnionType2
printfn "%A" currentLabelUnionType2
 
let currentLabelUnionType3 =  "Cat"
printfn "let currentLabelUnionType3 =  \"Cat\"" 
printfn "%O" currentLabelUnionType3
printfn "%A" currentLabelUnionType3
 
let currentLabelUnionType4 =  String "Cat"
printfn "let currentLabelUnionType4 =  String \"Cat\"" 
printfn "%O" currentLabelUnionType4
printfn "%A" currentLabelUnionType4

Which when run may produce the following results when run through the printfn function (I am either using a %A or %O printfn formatter below):

You can pretty much use any type in the union cases, such as:

• Tuples
• Records
• Other types

The only rule is that the type must be defined before your union case can use it.

Here is an example that uses a tuple type in the union cases:

type unionUsingTuples = CCY of (int * String) | Rates of (int * decimal)
.....
.....
let tupledUnion = (12, "GBP")

Empty Unions

You may also use empty unions. Which are ones where you do not specify a type. This makes them much more like standard .NET enum values. Here is an example of that.

type Player = Cross | Nought
....
....
let emptyUnion = Cross

What About Similar Cases Across Types

The eagle eyed amongst you may see a problem. What would happen if we had something like this:

type PurchaseOrders = Orders of (string * int) | Empty
type ClientOrders = Orders of (string * int) | Empty

This causes us a problem, doesn’t it. How would we distinguish between these discriminated union types? Well, luckily, we can just use a fully qualified approach to this, so we can simply do this, and everything will work as expected. It should be noted that you could take this one step further and include the module name if a module is involved (we will see more on this later, in a subsequent article).

let purchaseOrders = PurchaseOrders.Orders ("box of 100 scrubbing brushes", 1)
let clientOrders = PurchaseOrders.Orders ("scrubbing brush", 23)

Discriminated Unions Equality

As with a lot of F# types, Discriminated Unions are only considered equal if:

• The length of their union cases match
• The types of their union cases match
• The values of their union cases match

Are Not Equal

Here is an example where things are not considered equal:

let purchaseOrders = PurchaseOrders.Orders ("box of 100 scrubbing brushes", 1)
let clientOrders = PurchaseOrders.Orders ("scrubbing brush", 23)

printfn "purchaseOrders = clientOrders %A" (purchaseOrders = clientOrders)

Which looks like this when run:

c

Are Equal

Here is an example where things are considered equal, even though the underlying discriminated union types are different types. This is kind of inline with regular .NET code, you know if the members are the same, they have the same values and there is the correct number of them, they are pretty much the same thing (if we ignore hash codes that is):

let purchaseOrders = PurchaseOrders.Orders ("box of 100 scrubbing brushes", 1)
let clientOrders = PurchaseOrders.Orders ("box of 100 scrubbing brushes", 1)

Which looks like this when run:

Pattern Matching Discriminated Unions

As with most of F#, you are able to pattern match against discriminated union. Shown below is a small function that accepts a Card discriminated union and will print the union cases it was called with and simply returns a Unit type (void if you recall that from previous articles in this series):

type Card = ValueCard of int | Jack | Queen | King | Ace
....
....
let cardFunction card = 
    match card with
    | ValueCard i -> printfn "its a value card of %A" i
    | Jack -> printfn "its a Jack"
    | Queen -> printfn "its a Jack"
    | King -> printfn "its a Jack"
    | Ace -> printfn "its a Ace"
    () //return unit

   
//shows you how to pass it in without a Let binding
do cardFunction (Card.ValueCard 8)

//or you could use explicit Let binding if you do desire
let aceCard =  Ace
do cardFunction aceCard

Here is the result of running the pattern matching code above:

So Just Exactly What Is Going On Behind The Scenes There

So we have now seen some examples of how Discriminated Unions work. So what do you think would happen if we had a F# library that used Discriminated Unions and we chose to use that from C#/VB.NET. Do you think that would work. The answer is sure it would. I will be doing a whole post on Interop somewhere down the line, but I just thought it may be fun to visit part of that right now for Discriminated Unions as they are so different from anything we see in standard .NET programming.

So let's take the card example above, which was this code:

type Card = ValueCard of int | Jack | Queen | King | Ace

And then run it through a decompiler, such as Reflector / DotPeek (whatever you have essentially). I used DotPeek and got this C# code for that single line of F#. So as you can see, the F# compiler is doing a lot of work to ensure the F# types will interop nicely with regular .NET such as C#/VB.NET.

using Microsoft.FSharp.Core;
using System;
using System.Collections;
using System.Diagnostics;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;

[CompilationMapping(SourceConstructFlags.Module)]
public static class Program
{
  [EntryPoint]
  public static int main(string[] argv)
  {
    return 0;
  }

  [DebuggerDisplay("{__DebugDisplay(),nq}")]
  [CompilationMapping(SourceConstructFlags.SumType)]
  [Serializable]
  [StructLayout(LayoutKind.Auto, CharSet = CharSet.Auto)]
  public class Card : IEquatable<Program.Card>, IStructuralEquatable, 
    IComparable<Program.Card>, IComparable, IStructuralComparable
  {
    [CompilerGenerated]
    [DebuggerNonUserCode]
    [DebuggerBrowsable(DebuggerBrowsableState.Never)]
    public int Tag
    {
      [DebuggerNonUserCode] get
      {
        return this._tag;
      }
    }

    [CompilerGenerated]
    [DebuggerNonUserCode]
    [DebuggerBrowsable(DebuggerBrowsableState.Never)]
    public bool IsValueCard
    {
      [DebuggerNonUserCode] get
      {
        return this.get_Tag() == 0;
      }
    }

    [CompilerGenerated]
    [DebuggerNonUserCode]
    [DebuggerBrowsable(DebuggerBrowsableState.Never)]
    public static Program.Card Jack
    {
      [CompilationMapping(SourceConstructFlags.UnionCase, 1)] get
      {
        // ISSUE: reference to a compiler-generated field
        return Program.Card._unique_Jack;
      }
    }

    [CompilerGenerated]
    [DebuggerNonUserCode]
    [DebuggerBrowsable(DebuggerBrowsableState.Never)]
    public bool IsJack
    {
      [DebuggerNonUserCode] get
      {
        return this.get_Tag() == 1;
      }
    }

    [CompilerGenerated]
    [DebuggerNonUserCode]
    [DebuggerBrowsable(DebuggerBrowsableState.Never)]
    public static Program.Card Queen
    {
      [CompilationMapping(SourceConstructFlags.UnionCase, 2)] get
      {
        // ISSUE: reference to a compiler-generated field
        return Program.Card._unique_Queen;
      }
    }

    [CompilerGenerated]
    [DebuggerNonUserCode]
    [DebuggerBrowsable(DebuggerBrowsableState.Never)]
    public bool IsQueen
    {
      [DebuggerNonUserCode] get
      {
        return this.get_Tag() == 2;
      }
    }

    [CompilerGenerated]
    [DebuggerNonUserCode]
    [DebuggerBrowsable(DebuggerBrowsableState.Never)]
    public static Program.Card King
    {
      [CompilationMapping(SourceConstructFlags.UnionCase, 3)] get
      {
        // ISSUE: reference to a compiler-generated field
        return Program.Card._unique_King;
      }
    }

    [CompilerGenerated]
    [DebuggerNonUserCode]
    [DebuggerBrowsable(DebuggerBrowsableState.Never)]
    public bool IsKing
    {
      [DebuggerNonUserCode] get
      {
        return this.get_Tag() == 3;
      }
    }

    [CompilerGenerated]
    [DebuggerNonUserCode]
    [DebuggerBrowsable(DebuggerBrowsableState.Never)]
    public static Program.Card Ace
    {
      [CompilationMapping(SourceConstructFlags.UnionCase, 4)] get
      {
        // ISSUE: reference to a compiler-generated field
        return Program.Card._unique_Ace;
      }
    }

    [CompilerGenerated]
    [DebuggerNonUserCode]
    [DebuggerBrowsable(DebuggerBrowsableState.Never)]
    public bool IsAce
    {
      [DebuggerNonUserCode] get
      {
        return this.get_Tag() == 4;
      }
    }

    static Card()
    {
    }

    [CompilationMapping(SourceConstructFlags.UnionCase, 0)]
    public static Program.Card NewValueCard(int item)
    {
      return (Program.Card) new Program.Card.ValueCard(item);
    }

    [CompilationMapping(SourceConstructFlags.UnionCase, 1)]
    public static Program.Card get_Jack()
    {
      // ISSUE: reference to a compiler-generated field
      return Program.Card._unique_Jack;
    }

    [CompilationMapping(SourceConstructFlags.UnionCase, 2)]
    public static Program.Card get_Queen()
    {
      // ISSUE: reference to a compiler-generated field
      return Program.Card._unique_Queen;
    }

    [CompilationMapping(SourceConstructFlags.UnionCase, 3)]
    public static Program.Card get_King()
    {
      // ISSUE: reference to a compiler-generated field
      return Program.Card._unique_King;
    }

    [CompilationMapping(SourceConstructFlags.UnionCase, 4)]
    public static Program.Card get_Ace()
    {
      // ISSUE: reference to a compiler-generated field
      return Program.Card._unique_Ace;
    }

    public static class Tags
    {
      public const int ValueCard = 0;
      public const int Jack = 1;
      public const int Queen = 2;
      public const int King = 3;
      public const int Ace = 4;
    }

    [DebuggerTypeProxy(typeof (Program.Card.ValueCard\u0040DebugTypeProxy))]
    [DebuggerDisplay("{__DebugDisplay(),nq}")]
    [Serializable]
    [SpecialName]
    public class ValueCard : Program.Card
    {
      [CompilationMapping(SourceConstructFlags.Field, 0, 0)]
      [CompilerGenerated]
      [DebuggerNonUserCode]
      public int Item
      {
        [DebuggerNonUserCode] get
        {
          return this.item;
        }
      }
    }

    [SpecialName]
    internal class ValueCard\u0040DebugTypeProxy
    {
      [CompilationMapping(SourceConstructFlags.Field, 0, 0)]
      [CompilerGenerated]
      [DebuggerNonUserCode]
      public int Item
      {
        [DebuggerNonUserCode] get
        {
          return this._obj.item;
        }
      }
    }
  }
}

Recursive Cases (Tree Structures)

Discriminated Unions may also be used in a recursive manner, where the union itself may be used as one of the types in one or more of the cases. This makes Discriminated Unions very suitable for modelling tree like structures, such as:

• Mathematical Expressions
• Abstract syntax trees
• Xml

MSDN actually has some good examples on this, so I decided to do some more borrowing (stealing) here (thanks MSDN). The following paragraphs are taken from the following MSDN URL:

• http://msdn.microsoft.com/en-us/library/dd233226.aspx

In the following code, a recursive discriminated union is used to create a binary tree data structure. The union consists of two cases, Node, which is a node with an integer value and left and right subtrees, and Tip, which terminates the tree.

The Tree structure for myTree in the example below is as shown in the figure here:

And here is how we would model the myTree using Discriminated Unions. Notice how we include the Discriminated Union itself as one of the union cases. In this case, the union cases are either:

1. A tip (empty union case, acts like standard enum in .NET)
2. Or a 3 valued tuple of int, Tree, Tree

The other thing to note is that the sumTree function is marked with a “rec” keyword. What does this magic incantation do to our function? Well it marks the sumTree function as one that will be called recursively. Without the “rec” keyword on the sumTree function, the F# compiler would complain. In this case, the compiler would issue the following error.

But we are good citizens, and will use the correct key words to support our use case, so onwards we go.

type Tree =
    | Tip
    | Node of int * Tree * Tree
....
....
....
....
let rec sumTree tree =
    match tree with
    | Tip -> 0
    | Node(value, left, right) ->
        value + sumTree(left) + sumTree(right)
let myTree = Node(0, 
                    Node(1, 
                        Node(2, Tip, Tip), 
                        Node(3, Tip, Tip)), 
                    Node(4, Tip, Tip))
let resultSumTree = sumTree myTree

printfn "Value of sumTree is %A" resultSumTree

Which when run will show the following results:

MSDN also has one other good example that I thought might be worth stealing (yes, I am being blatant about it now. I think as long as you guys/girls get something out of this borrowed example which I clearly say is borrowed, I am all like ‘meh’). Let's see that example here:

type Expression = 
    | Number of int
    | Add of Expression * Expression
    | Multiply of Expression * Expression
    | Variable of string
....
....
....
let rec Evaluate (env:Map<string,int>) exp = 
    match exp with
    | Number n -> n
    | Add (x, y) -> Evaluate env x + Evaluate env y
    | Multiply (x, y) -> Evaluate env x * Evaluate env y
    | Variable id    -> env.[id]

let environment = Map.ofList [ "a", 1 ;
                                "b", 2 ;
                                "c", 3 ]

// Create an expression tree that represents 
// the expression: a + 2 * b. 
let expressionTree1 = Add(Variable "a", Multiply(Number 2, Variable "b"))

// Evaluate the expression a + 2 * b, given the 
// table of values for the variables. 
let result = Evaluate environment expressionTree1

printfn "Value of sumTree is %A" result

Which when run will show the following results: