F# Discriminated Unions
When I started learning F# discriminated unions were probably the first thing that really sold me on the language only partially because there’s nothing like them in C#. From a traditional .NET background a quick glance at them, particularly simple ones, may lead you to believe that they’re just glorified enumerations but in reality, discriminated unions are so much more powerful. While enumerations are limited to a single, fixed integral value but applications for discriminated unions go far beyond that.
Like enumerations, discriminated unions allow us to define values that can only be one of a specified set of named cases but that’s where the similarities end. Discriminated unions allow us to associate zero or more data items of any type with each case. The effect is that we can easily define tree structures, simple object hierarchies, and even leverage pattern matching.
Discriminated Unions as Object Hierarchies
I think the easiest way to get into discriminated unions is to start off with an example. In my studies of the language I’ve become quite fond of the example I first encountered in Programming F# where discriminated unions and a list comprehension are used to define a standard, unshuffled card deck. This example does a great job illustrating not only simple, “dataless” unions but also shows how we can associate multiple data items and even combine discriminated unions to achieve more expressive code.
We start by defining a discriminated union for each suit. The suits don’t have any data associated with them so this discriminated union simply includes the case names.
type Suit = | Heart | Diamond | Spade | Club
The second discriminated union defines the individual cards. Each card belongs to a particular suit and non-face cards will also include their denomination.
type Card = | Ace of Suit | King of Suit | Queen of Suit | Jack of Suit | ValueCard of Suit * int
With just these two constructs we can define a value representing any card in a standard deck. For instance, if we wanted to represent the Ace of Spades, or 7 of Hearts we’d write Ace(Spade) and ValueCard(Heart, 7), respectively.
We don’t need to include to the actual discriminated union name when referring to a case. Should there be a naming conflict we’re free to include the union name with dot syntax (Suit.Heart) or we could instruct the compiler to force a qualified name with the RequireQualifiedAccess attribute.
If you were paying attention during the Card example you probably noticed a familiar syntax. When multiple data elements are associated with a case (such as with ValueCard) we use the tuple syntax to identify each element’s data type. While this allows for a lot of flexibility it also brings along some of the drawbacks of tuples such as not being able to define names for each value. We’ll look at one way to work around this limitation a little later when we discuss pattern matching.
The tuples in discriminated unions are syntactic tuples. The types the compiler generates for each case are nested classes that derive from the discriminated union type. The data elements are exposed as read-only properties following the same conventions as tuples but there aren’t any actual tuple class instances involved.
Now that we’re armed with some basic knowledge of discriminated unions we can use a list comprehension to easily construct a full, unshuffled deck.
let deck = [ for suit in [ Heart; Diamond; Spade; Club ] do yield Ace(suit) yield King(suit) yield Queen(suit) yield Jack(suit) for v in 2 .. 10 do yield ValueCard(suit, v) ]
No introductory discussion about discriminated unions would be complete without at least a brief mention of the option type. The option type is a predefined discriminated union (Microsoft.FSharp.Core.FSharpOption) that’s useful for indicating when a value may or may not exist (remember: null generally isn’t used in F#). There are only two cases in the option type: Some(_) and None. Because the type itself is an unconstrained generic type, its cases can be used to indicate the presence of any value.
Although options are generally referenced in pattern matching expressions there’s an associated option module that contains several useful functions including Option.get, Option.bind, and Option.exists.
Discriminated Unions as Trees
A really nice aspect of discriminated unions is that they can be self-referencing. This makes creating simple tree structures trivial. To illustrate let’s create a very rudimentary HTML structure.
type Markup = | Element of string * Markup list | EmptyElement of string | Content of string
Note that the Element case has two associated pieces of data: a string (the element name), and a list of additional Markup instances. From just these three cases we can quickly represent a simple HTML document:
let htmlTree = Element("html", [ Element("head", [ Element("title", [ Content("Very Simple HTML") ]) ]) Element("body", [ Element("article", [ Element("h1", [ Content("Discriminated Unions") ]) Element("p", [ Content("See how ") Element("b", [ Content("easy") ]) Content(" this is?") ]) Element("p", [ Content("F#"); EmptyElement("br"); Content("is fun") ]) ]) ]) ])
Discriminated Unions in Pattern Matching
We’ve seen how discriminated unions can be used to easily define both object hierarchies and tree structures. Like with so many things in F# though that power is amplified when combined with pattern matching. With pattern matching we can not only can we provide conditional logic for operating against each case but we can also work around the limitation I mentioned earlier where each associated data item is assigned a less than useful name.
Let’s expand upon the Markup example from the previous section to illustrate. Here we’ll define a recursive function to convert the htmlTree value to an HTML string.
let rec toHtml m : string = match m with | Element (tag, children) -> let sb = System.Text.StringBuilder() let append (s : string) = sb.Append s |> ignore append (sprintf "<%s>" tag) List.iter (fun c -> append (c |> toHtml)) children append (sprintf"</%s>" tag) sb.ToString() | EmptyElement tag -> sprintf "<%s />" tag | Content v -> sprintf "%s" v;; htmlTree |> toHtml > val it : string = "<html><head><title>Very Simple HTML</title></head><body><article><h1>Discriminated Unions</h1><p>See how <b>easy</b> this is?</p><p>F#<br />is fun</p></article></body></html>"
In this example we have a pattern for each Markup case. Each case is covered by a pattern so there’s no need to introduce the wildcard (_) pattern here. Each pattern includes an identifier for each data item associated with the case. The identifiers allow us to refer to each item with something meaningful rather than the default name. Identifiers are also useful within when constraints to provide more granular control over what matches a given pattern. For instance if we wanted to apply different handling for p elements we could add the pattern | Element (tag, children) when tag = "p" -> ... to the beginning of the match expression.
Members in Discriminated Unions
Just as with record types, discriminated unions ultimately compile down to classes. As such, we can expand upon them with additional members such as methods. Continuing with the Markup it makes sense to keep the toHtml method with the Markup type so let’s combine them.
To convert the function to a method we only need to make a few small tweaks. First, we’ll eliminate the argument since we’ll be operating against the current instance. We’ll also add a type annotation to the delegate used by the List.iter function.
type Markup = | Element of string * Markup list | EmptyElement of string | Content of string member x.toHtml() : string = match x with | Element (tag, children) -> let sb = System.Text.StringBuilder() let append (s : string) = sb.Append s |> ignore append (sprintf "<%s>" tag) List.iter (fun (c : Markup) -> append (c.toHtml())) children append (sprintf"</%s>" tag) sb.ToString() | EmptyElement tag -> sprintf "<%s />" tag | Content v -> sprintf "%s" v
Note that the member function is no longer marked as recursive. This is because recursion is implicitly allowed for members.
Now that the toHtml function is a method of the Markup type we can call it like we would a method on any other type:
htmlTree.toHtml() > val it : string = "<html><head><title>Very Simple HTML</title></head><body><article><h1>Discriminated Unions</h1><p>See how <b>easy</b> this is?</p><p>F#<br />is fun</p></article></body></html>"
Discriminated unions are a highly useful construct with applications far beyond that of enumerations. Whether they’re being used to construct an object hierarchy or represent a tree structure discriminated unions can greatly enhance the clarity of your code.
Sometimes a discriminated union is bit overkill for the problem space and an enumeration is all that’s needed. In the next post we’ll explore how to define enumerations in F#.