Inside F#

Brian's thoughts on F# and .NET

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:

type ADiscriminatedUnionType =
    | 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 du1  // x is 42, s is life
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

match l with
| [] -> 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:

if (l.IsEmpty)
{
    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:

type option<’a> =
    | 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 PrintFirstStartsWithM l =
    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 
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
     
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

#else
type 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?  :)

About these ads

3 Responses to “Discriminated unions in F#”

  1. 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.
     
     

  2. 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?

  3. 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 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
Follow

Get every new post delivered to your Inbox.

Join 30 other followers

%d bloggers like this: