« F# pattern matching for beginners, part 1: getting started | Main | Bracing »

July 11, 2010

F# pattern matching for beginners, part 2: decomposition

At the end of the last instalment, I showed a simple example of a variable pattern in F#.

let selfAwareTroll n = 
  match n with
  | 1 -> "one"
  | 2 -> "two"
  | a -> sprintf "i can't count to %d" a

Here the pattern a matches anything, just like the wildcard (underscore) pattern, but also makes the variable a available on the right hand side of the arrow, with its value set to whatever the variable pattern matched:

> selfAwareTroll 3;; 
val it : string = "i can't count to 3" 
> selfAwareTroll 4;; 
val it : string = "i can't count to 4"

I commented that in this simple example, the variable pattern wasn’t very useful, because we already had the matched value available as n.

However, F# also supports a number of patterns which decompose their input: that is, they match not only on values but also on the structure of the input.  Once you start combining variable patterns with structural patterns, the use of variable patterns becomes a lot clearer.

Matching multiple pieces of data

In F#, you can bundle up multiple pieces of data into a tuple by enclosing them in parentheses.  So if a function wants to return multiple pieces of data, it can do so by returning a tuple rather than messing around with C#-style out parameters.

let squareAndCube n = (n * n, n * n * n)
> squareAndCube 3;; 
val it : int * int = (9, 27)

In fact, F# even goes so far as to translate .NET APIs with out parameters into functions which return tuples.  For example, the Int32.TryParse function, which in C# returns a boolean and has an integer out parameters, in F# returns a pair of a boolean and an integer:

> Int32.TryParse("123");; 
val it : bool * int = (true, 123) 
> Int32.TryParse("bob");; 
val it : bool * int = (false, 0)

How does this fit in with pattern matching?  Well, if you write a pattern using the parentheses and comma syntax, it will match a tuple with the appropriate number of slots.  What’s more, it will crack open the tuple and check for a match on each element of the pattern.  This is easier to see than to describe:

let isInt s =
  match Int32.TryParse(s) with
  | (false, _) -> false
  | (true, _) -> true

The first pattern cracks open the tuple returned by Int32.TryParse, and matches if the first element matches the constant false pattern and the second element matches the wildcard pattern.

> isInt "123";; 
val it : bool = true 
> isInt "bob";; 
val it : bool = false 

Now it should be clear where variable patterns fit in.  Instead of using a wildcard pattern inside the tuple pattern, we can use a variable pattern.  And then the variable will get bound just to that element of the tuple.

let parse s =
  match Int32.TryParse(s) with
  | (false, _) -> -1
  | (true, n) -> n
> parse "123";; 
val it : int = 123 
> parse "bob";; 
val it : int = -1 

Here, in the second clause, n contains the second element of the tuple returned by Int32.Parse.  We don’t need to write explicit code to extract the second member from the tuple, and consequently we haven’t had to clutter the code up with a temporary variable to store the tuple while we run through the various conditions on it.  The pattern has decomposed the tuple for us, and assigned its elements to variables where we’ve used variable patterns.

Decomposition patterns aren’t just for match expressions

Tuple patterns also illustrate that F# patterns aren’t restricted to match expressions.  You can use a tuple pattern in a simple assignment:

> let (didParse, value) = Int32.TryParse("123");; 
val value : int = 123 
val didParse : bool = true 
> value;; 
val it : int = 123 
> didParse;; 
val it : bool = true

Here we’re using a tuple pattern with two variable patterns, both of which get assigned.  If we only cared about whether the string was parseable, we could use a wildcard pattern for the second element:

> let (didParse, _) = Int32.TryParse("bob");; 
val didParse : bool = false 

It’s important to realise that using let with a decomposing pattern isn’t a special case, or in any way different from familiar singular examples such as let x = 2.  The singular case just happens to be using a variable pattern (x) instead of a decomposing pattern, but it’s still using a pattern.  It just happens to look like a conventional imperative assignment!

Decomposing discriminated unions

Another important F# idiom is discriminated unions.  A discriminated union is basically a type which can contain different kinds of data depending on a discriminator.  A very common example is the built-in option type, which can be roughly described as “nullable types done right.”  An option can be either None (in which case it has no data) or Some (in which case it has one piece of data):

type 'a option =
  | None
  | Some of 'a

F# provides a pattern syntax for matching the different cases of a discriminated union, consisting of the discriminator and a pattern for the data in that case (if any):

let isSome opt =
  match opt with
  | None -> false
  | Some _ -> true

Here we’re using the wildcard pattern in the Some case, but we can use any other pattern to match or capture the Some value:

let optionalTroll opt =
  match opt with
  | None -> "nuffink"
  | Some 1 -> "one"
  | Some 2 -> "two"
  | Some n -> sprintf "i can't count to %d" n

Here we’re using constant and variable patterns to match the contents of the Some case.

Decomposing patterns compose

We’ve seen patterns for breaking apart discriminated unions and for breaking apart tuples.  (And there are plenty more decomposing patterns: stay tuned.)  And we’ve noted that each ‘slot’ in a decomposing pattern is another pattern.  So what happens if we use a tuple pattern inside a discriminated union pattern, or vice versa?  Good things happen, that’s what.

type SearchResult =
  | NoHit
  | Hit of string * int

let formatResult sr =
  match sr with
  | NoHit -> "no record found"
  | Hit (_, 0) -> "no good match found"
  | Hit (str, score) -> sprintf "found %s with score %d" str score

The Hit patterns in the formatResult function not only break out the data from the Hit case, but also break open the tuple so that we can match on and capture the elements of that tuple.

> formatResult NoHit;;
val it : string = "no record found" 
> formatResult (Hit("bob", 0));; 
val it : string = "no good match found" 
> formatResult (Hit("alice", 123));; 
val it : string = "found alice with score 123"

Similarly, a slot pattern within a tuple pattern can be a discriminated union pattern, another tuple pattern, or any other kind of pattern.  Here’s a match expression that first cracks open a tuple, then cracks open an option to extract the sweet sweet data within:

let formatTwo pair =
  match pair with
  | (n, None) -> sprintf "%d" n
  | (n, Some 0) -> sprintf "%d and zero" n
  | (n, Some m) -> sprintf "%d and %d" n m

In short, you can compose decomposing patterns to match structures within structures: F# will keep on decomposing as long as you keep asking it to.

July 11, 2010 in Software | Permalink

TrackBack

TrackBack URL for this entry:
http://www.typepad.com/services/trackback/6a00d8341c5c9b53ef0133f23323ce970b

Listed below are links to weblogs that reference F# pattern matching for beginners, part 2: decomposition:

Comments