| Brian's profileInside F#BlogGuestbookNetwork |  Tools  Help |
|
|
April 07 Discriminated unions in F#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> typeOne 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.hd, List.tl, and List.nonempty (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> typeApart 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 unionsUse 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.) #light 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 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 #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 = Enum.to_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.fold1_right (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? :) Comments (3)
TrackbacksWeblogs that reference this entry
|
|
|
