« A milestone of meta | Main | F# pattern matching for beginners, part 2: decomposition »

July 10, 2010

F# pattern matching for beginners, part 1: getting started

Pattern matching is idiomatic in functional programming, and F# is no exception.  Pattern matching provides a concise but clear and highly expressive way of writing conditional logic, because it combines the conditional flow with the ability to extract values of interest.  So if you’re just starting out in F# it’s important to know your way around patterns and pattern matching.

The match expression

To get started, we’ll look at a truly trivial example of pattern matching.  Here’s how to do the equivalent of a C# switch or Visual Basic Select Case statement using F# pattern matching:

let troll n = 
  match n with
  | 1 -> "one"
  | 2 -> "two"
  | _ -> "uh, many"

Even if you’ve never had the pleasure of meeting a troll, you can guess what this function does:

> troll 1;;
val it : string = "one"
> troll 2;; 
val it : string = "two"
> troll 3;; 
val it : string = "uh, many"

Let’s quickly labour the obvious.  The match expression is introduced by the keyword match, followed by the expression to be matched (in our case, n), followed by with keyword with.  Each condition then follows on a separate line, beginning with | (the pipe character) and indented at least as far as the match keyword.  (Conventionally, the pipe characters are lined up under the ‘m’ of match.)

Another thing you can see from the example is that the ‘match anything’ case is indicated by an underscore.  This is sort of analogous to default in C# or Case Else in Visual Basic: as we’ll see, however, ‘match anything’ takes on a bigger role when we start looking at more complicated expressions.

A match expression is an expression

Unlike switch or Select Case, match is an expression, not a statement.  That means that rather than doing something, it has a value.  This has a couple of consequences:

  • Every condition is an expression, and has a value.  For example, the clause | 1 -> "one" means that when the input to the match expression is 1, the value of the match expression is “one”.  Furthermore, because F# is statically typed, the match expression as a whole must have a well-defined data type, so every clause must return the same type of data.  For example, if our second clause were | 2 -> 3, then F# would complain that the expression (3) was expected to have type string but actually had type int.
  • You have to have a clause for every possible input.  Suppose we left out the underscore (match anything) clause in the trivial example.  Then, if the input was 3, the match expression wouldn’t have a value.  F# can’t stomach the idea of an expression not having a value, and will refuse to compile a match expression that doesn’t cover every possible case.  Contrast this with a switch statement, where it’s perfectly legitimate to leave out cases where you don’t want to do anything; it’s more like the way the C# compiler complains if you declare a function and not all of your code paths return a value.

What is match matching?

The trivial example above puts the focus on the syntax of the match expression at the expense of the match conditions.  With the match keyword syntax out of the way, we can now zero in on the match conditions.

In the trivial example, the match conditions were simple values.  Although this is the familiar case for C# and Visual Basic programmers, it turns out that in F# this is an extremely special case.

In F#, the match conditions are not values: they are patterns.  A constant value like 1 or 2 is a particularly simple pattern, but there are lots of other kinds of patterns, and we can use them in the match conditions as well.  In fact, we’ve already seen another kind of pattern: the wildcard pattern, represented by the underscore.

So when the match expression is evaluated, it doesn’t – as the trivial example might imply – run through the list of conditions checking if the argument is equal to the given value.  It runs through the list of conditions checking the argument matches the given pattern.  It just so happened that in the trivial example we were using constant patterns that matched only if the argument was equal to the given value.  But we could have used other patterns.

Let’s look at another trivial example:

let smartTroll n = 
  match n with
  | 1 -> "one"
  | 2 -> "two"
  | (3 | 4) -> "some"
  | _ -> "uh, many"

Here the pattern 3 | 4 matches either the value 3 or the value 4.  (Don’t confuse the pipe character indicating “or” with the pipe character introducing a clause.  I’ve added parentheses to emphasise this, though they’re not syntactically required.)

Patterns can capture values

So far, pattern matching still looks like a fancy version of the switch statement.  But there’s another kind of pattern which the switch statement can’t replicate: the variable pattern.  A variable pattern looks like the name of a variable – that is, a F# identifier.  Like the wildcard, it matches anything.  The difference is that it captures the matched value into the variable.

Again, let’s look at a simple example.

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

Here, the fallthrough clause uses a variable pattern (the identifier a) instead of a wildcard pattern.  The effect of this is that we can use the variable a in the result expression, and it will contain the value that was matched.  Effectively, F# sets a to the matched value.  The result is what you’d expect:

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

Attack of the destructuring binds

Looking at this example, you may notice that capturing the matched value into a doesn’t seem to be gaining us anything.  After all, we already know the matched value: it’s n.  Surely we could just write:

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

This works great as long as we’re only interested in the matched value as a whole.  In the real world, however, many functions return multiple pieces of data: a familiar example is Dictionary.TryGetValue, which returns both whether the key was present and the associated value if it was.  Other examples, less familiar to C# and Visual Basic programmers, include lists and discriminated unions.

It’s in these multipart cases that pattern matching really starts to flex its muscles.  By combining variable patterns with patterns for these multipart types, we can handle these multiple pieces of data in a far more concise and convenient way than we could with a switch or if statement.  It’s so concise and convenient, in fact, that it becomes a general part of the F# language, not just restricted to match expressions.  In the next part of this series, we’ll see how this seemingly abstruse feature translates into compact, readable code.

July 10, 2010 in Software | Permalink

TrackBack

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

Listed below are links to weblogs that reference F# pattern matching for beginners, part 1: getting started:

Comments

What a simple and excellently written article on F# pattern matching. I am learning f# and this helps, thanks!

Flatlander is a reference to Larry Niven coinage? I am a fan too.

Posted by: Cyril Gupta at Oct 22, 2010 7:17:42 AM