Discriminated unions in F#
Posted by Brian on April 7, 2008
Discriminated unions are used a lot in F# code. A discriminated union is a data type with a finite number of distinct alternative representations. If you have used "union" in C/C++, you can think of discriminated unions as a somewhat similar construct; the main differences are that F# discriminated unions are type-safe (every instance knows which alternative is ‘active’) and that F# discriminated unions work with pattern-matching. Here is a short example that suggests how to define and use a discriminated union type:
| Alternative1 of int * string
| Alternative2 of bool
| Alternative3
// constructing instances
let du1 = Alternative1(42,"life")
let du3 = Alternative3
let f du =
// pattern matching
match du with
| Alternative1(x,s) -> printfn "x is %d, s is %s" x s
| Alternative2(b) -> printfn "b is %A" b
| Alternative3 -> printfn "three"
f du3 // three
The list<‘a> type
One of the most common F# types, list<‘a>, is a discriminated union. It has two alternatives: nil (spelled "[]"), and cons (spelled "::"). The former alternative carries no data, whereas the latter carries an ‘a*list<‘a>. Thus you frequently write code like
| [] -> printfn "do something in nil case"
| h :: t -> printfn "do something else in cons case"
in F#. If "l" was a list<int>, then "h" would be an int (the head of the list – that is, the first element), and "t" would be a list<int> (the tail of the list – that is, all the rest of the elements except the first one). The existence of pattern-matching for lists means you very rarely call functions like List.head, List.tail, and List.isEmpty (see the List module). Note that the code above has roughly the same meaning as this C# code:
{
Console.WriteLine("do something in nil case");
}
else
{
var h = l.Head;
var t = l.Tail;
Console.WriteLine("do something else in cons case");
}
In essence, pattern matching is simultaneously both a control construct (like an if-then-else or switch statement) and a binding construct (a "let" that binds values to names). It’s hard to appreciate just how useful and elegant pattern-matching is until you’ve used it a bit in practice. (I had read about pattern matching in ML before, years ago, but I just shrugged it off as a cute little bit of syntax sugar. But now that I’m using it in F#, it really is very handy, and I finally "get" why the ML folks always tout this language feature.)
The option<‘a> type
Apart from list<‘a>, the other most-commonly-encountered discriminated union type in F# is option<‘a>. Its definition is very simple:
| Some of ‘a
| None
This type is mostly often used for functions that may or may not return a result. For example, if we’re trying to find an element in a list that matches some predicate, the list might or might not contain such an element. Thus, List.tryfind returns an option. Here is a contrived example:
let answer = List.tryFind (fun (s : String) -> s.StartsWith("M")) l
match answer with
| Some(s) -> printfn "%s" s
| None -> printfn "list had no strings starting with M"
PrintFirstStartsWithM ["Sunday"; "Monday"; "Tuesday"] // Monday
PrintFirstStartsWithM ["one"; "two"; "three"] // list had no strings starting with M
If you’re familiar with the method TryGetValue in System.Collections.Generic.Dictionary, then it should be clear how the option<‘a> type solves the same problem as the signature of TryGetValue (or more generally, the "TryParse" design pattern as described briefly here).
When to use discriminated unions
Use discriminated unions where a type has a finite number of alternative representations, and you want to leverage pattern-matching. This means that you can often express what would otherwise be a small class hierarchy as a discriminated union. For example, consider the "PrettyString" code from a previous blog entry. Originally I wrote it using a small class hierarchy; here it is again using a discriminated union instead. (I preserved the class code in the "#if CLASSES" portion.)
open System.Text
open Microsoft.FSharp.Collections
#if CLASSES
/// PrettyStrings are strings that support vertical and horizontal concatenation
/// for creating grids of text.
[<AbstractClass>]
type PrettyString() =
/// The number of lines in this PrettyString
abstract Height : int
/// The width of this PrettyString (width of the longest line)
abstract Width : int
/// Get the nth line. If n is not in the range [0..Height), then return the empty string.
abstract Line : int -> string
override this.ToString() =
let sb = new StringBuilder()
for i in 0 .. this.Height do
sb.Append(this.Line i) |> ignore
sb.Append("\n") |> ignore
sb.ToString()
type StringLiteral(s : String) =
inherit PrettyString()
// TODO: if the input string contains newline characters,
// things will be ugly. Ignoring that issue for now.
override this.Height = 1
override this.Width = s.Length
override this.Line n = if n <> 0 then "" else s
type Vertical(top : PrettyString, bottom : PrettyString) =
inherit PrettyString ()
override this.Height = top.Height + bottom.Height
override this.Width = Math.Max(top.Width, bottom.Width)
override this.Line n =
if n < 0 || n >= this.Height
then ""
else if n < top.Height
then top.Line n
else bottom.Line (n – top.Height)
type Horizontal(left : PrettyString, right : PrettyString) =
inherit PrettyString()
override this.Height = Math.Max(left.Height, right.Height)
override this.Width = left.Width + right.Width
override this.Line n =
String.Concat(left.Line(n).PadRight(left.Width),
right.Line(n))
let pretty s = new StringLiteral(s) :> PrettyString
let (%%) x y = new Vertical(x,y) :> PrettyString
let (++) x y = new Horizontal(x,y) :> PrettyString
| StringLiteral of String
| Vertical of PrettyString * PrettyString
| Horizontal of PrettyString * PrettyString
let rec Height ps =
match ps with
| StringLiteral(_) -> 1
| Vertical(top, bottom) -> (Height top) + (Height bottom)
| Horizontal(left, right) -> max (Height left) (Height right)
let rec Width ps =
match ps with
| StringLiteral(s) -> s.Length
| Vertical(top, bottom) -> max (Width top) (Width bottom)
| Horizontal(left, right) -> (Width left) + (Width right)
let rec Line ps n =
match ps with
| StringLiteral(s) -> if n <> 0 then "" else s
| Vertical(top, bottom) ->
if n < 0 || n >= Height ps
then ""
else if n < Height top
then Line top n
else Line bottom (n – Height top)
| Horizontal(left, right) ->
String.Concat((Line left n).PadRight(Width left),
Line right n)
let ToString ps =
let sb = new StringBuilder()
for i in 0 .. Height ps do
sb.Append(Line ps i) |> ignore
sb.Append("\n") |> ignore
sb.ToString()
let pretty s = StringLiteral(s)
let (%%) x y = Vertical(x,y)
let (++) x y = Horizontal(x,y)
#endif
let blank = pretty " "
let calendar year month =
let maxDays = DateTime.DaysInMonth(year, month)
// make the column that starts with day i (e.g. 1, 8, 15, 22, 29)
let makeColumn i =
let prettyNum (i:int) = pretty(i.ToString().PadLeft(2))
let mutable r = prettyNum i
let mutable j = i + 7
while j <= maxDays do
r <- r %% prettyNum j
j <- j + 7
r
let firstOfMonth = new DateTime(year, month, 1)
let firstDayOfWeek = int firstOfMonth.DayOfWeek
// create all the columns for this month’s calendar, with Sundays in columns[0]
let columns = Array.create 7 blank
for i in 0 .. 6 do
columns.[(i + firstDayOfWeek) % 7] <- makeColumn (i+1)
// if, for example, the first of the month is a Tuesday, then we need Sunday and Monday
// to have a blank in the first row of the calendar
if firstDayOfWeek <> 0 then
for i in 0 .. firstDayOfWeek-1 do
columns.[i] <- blank %% columns.[i]
// put the weekday headers at the top of each column
let dayAbbrs = [| "Su"; "Mo"; "Tu"; "We"; "Th"; "Fr"; "Sa" |]
for i in 0 .. 6 do
columns.[i] <- pretty(dayAbbrs.[i]) %% columns.[i]
// Horizontally concatenate all of the columns together, with blank space between columns
let calendarBody = Array.reduceBack (fun x y -> x ++ blank ++ y) columns
// Surely there must be a .NET call that turns a month number into its name,
// but I couldn’t find it when I was typing this up.
let monthNames = [| "January" ; "February"; "March"; "April"; "May"; "June";
"July"; "August"; "September"; "October"; "November"; "December" |]
let titleBar = pretty(sprintf "%s %d" monthNames.[month-1] year)
titleBar %% calendarBody
let c = calendar 2008 4
#if CLASSES
printfn "%s" (c.ToString())
#else
printfn "%s" (ToString c)
#endif
The PrettyString abstract class became a discriminated union type, and each of its subclasses became one alternative of the discriminated union. The methods on the abstract class became top-level functions that took a PrettyString as an argument. Apart from that, little else changes. Hopefully this example will help you draw the analogy between discriminated unions and class hierarchies.
Whereas a class hierarchy is "open", in that someone else can come along later and add a new subclass, discriminated unions are "closed", in that the author of the type specifies all the alternatives once-and-for-all (analogy: imagine a "sealed" class hierarchy). This is often the main factor to consider when trying to decide between a class hierarchy and a discriminated union.
That’s it for today; I’ve already had a number of blog posts that took discriminated unions and pattern matching for granted, so it’s about time I stopped to explain them a little, eh? :)
Karl said
Hi Brian,
many thanks for your help in getting into this strange functional world…
one question to the above: you write about list<\’a> as a discriminated union with one alternative being acons (::) of type \’a*list<\’a>, meaning a tuple? Why?
because of the definition of a list being h::t?
That is a value of type \’a and a list of type \’a
(i think definition is the wrong term here, right?)
In my naiveness i would say this is still type list<\’a>.
But it well may be that i miss something….
Please can you enlighten me.
Thank you,
Karl
PS please continue your excellent work, it is really the best "coming into F#" i could found.
Brian said
Consider this code:
#light
type MyList<\’a> = | Nil | Cons of \’a * MyList<\’a>
let li = Cons(1, Cons(2, Cons(3, Nil)))
let rec PrintList(l : MyList<\’a>) = match l with | Nil -> () | Cons(h,t) -> printfn "%A" h PrintList t
PrintList li
The user-defined type "MyList" is just like the F# type "list", except that it uses the names "Nil" and "Cons" whereas the F# builtin list type uses the names "[]" and "::" and has more special syntax support. Does it make sense?
Karl said
OK, got it.
that was like: back to the roots of functional definition what a list is.
I am not yet really into it, but it is getting better ;)
Thanks, Brian