Tuesday, February 19, 2008
Greetings fellow F#-philes! Today we're looking at another reason that I am completely infatuated with the F# language—pattern matching.

Pattern matching is a simple idea. Essentially, a pattern match takes an input and a set of rules. Each rule tests the input against a pattern and returns a result if they match.

The following naive implementation of the tired, old Fibonacci function shows simple pattern matching at work.

#light

let rec fib n =
  match n with
  | 0 -> 0
  | 1 -> 1
  | _ -> fib(n - 1) + fib(n - 2)

Pattern matching syntax is simple and clear. It should be readable by any programmer worth their salt. In fact, the above match .. with block is completely equivalent to the following C# switch statement:

static int Fib(int n)
{
  switch (n)
  {
    case 0:
      return 0;
    case 1:
      return 1;
    default:
      return Fib(n - 1) + Fib(n - 2);
  }
}

That's pretty unimpressive. I mean, if pattern matching were identical to standard switch statements, there really would be nothing exciting about them. Fortunately, there are some enormous differences that demote switch statements to a very distant cousin.

The first difference is subtle but profound: pattern matches return values. A pattern match is very much like a function that takes an argument and returns a value. Consider the following rewrite of our F# fib function:

#light

let rec fib n =
  let result = match n with
               | 0 -> 0
               | 1 -> 1
               | _ -> fib(n - 1) + fib(n - 2)
  result

The above example might be a bit contrived, but it illustrates the point. Simulating that with a switch statement is awkward.

static int Fib(int n)
{
  int result;
  switch (n)
  {
    case 0:
      result = 0;
      break;
    case 1:
      result = 1;
      break;
    default:
      result = Fib(n - 1) + Fib(n - 2);
      break;
  }
  return result;
}

Switch statements don't return values, so we can't assign a switch statement to a variable. Instead, we must use mutable state and pepper the cases with break statements. In essence, a pattern match is like a function while a switch statement is like a big GOTO.

In addition, pattern matching supports a wealth of features that truly set it apart from standard imperative switch statements.

Patterns can:

  1. Contain guard rules (e.g. match x but only when x is less than zero).
  2. Bind values to names.
  3. Decompose type structures.

Let's examine each of these in turn.

First, consider our original fib function with an additional pattern containing a guard rule:

#light

let rec fib n =
  match n with
  | _ when n < 0 -> failwith "value cannot be less than 0."
  | 0 -> 0
  | 1 -> 1
  | _ -> fib(n - 1) + fib(n - 2)

Now that's a bit more interesting! In C# or Visual Basic, we would have to introduce an if-statement at the beginning of the function to test for an invalid argument. In F#, the guard is inserted directly as a pattern rule.

Another indispensible feature of F# pattern matching is the ability to bind values to names.

So far, we've used the match .. with syntax to define pattern matches. This time, we'll use an alternative syntax that, although it is not required, easily demonstrates how values can be bound to names within pattern rules.

The alternative syntax can be used in the case where a function is defined with one argument and simply returns the result of a pattern match on that argument. In this syntax, the argument is not specified, and the keyword function is inserted. The match .. with statement needs to reference the argument name, but because the argument is unspecified, it has no name. Consequently, the match .. with statement must be removed, leaving us with a function that is defined entirely in terms of pattern matching rules. Because the argument is unnamed, values must be bound to names within the pattern rules.

A code sample is worth a thousand words.

#light

let rec fib = function
  | x when x < 0 -> failwith "value cannot be less than 0."
  | 0 | 1 as x -> x
  | x -> fib(x - 1) + fib(x - 2)

In the above code, we bind the name x in each pattern to make up for the fact that the argument is unspecified. In addition, the rules for 0 and 1 and have been combined using an "or" (or "union") pattern. Note that there are two different ways to bind a value to a name within a pattern rule. First, a name can simply be explicitly specified, substituted within the pattern. The other way is to use the as keyword. Both ways are demonstrated above.

The last feature of pattern matching that we'll look at is its capability to decompose type structures.

Recently, we saw that F# would automatically convert the result of Dictionary<TKey, TValue>.TryGetValue to a tuple if a variable isn't specified for the out parameter. In a comment to that article, Derek Slager presented a helper function that returns a default value if TryGetValue returns false. This helper function is an excellent practical example of a pattern match that decomposes a tuple value.

#light

open System.Collections.Generic

let getValueOrDefault (dict : #IDictionary<'a,'b>) key defaultValue =
  match dict.TryGetValue key with
  | true, value -> value
  | _ -> defaultValue

In addition to the tuple decomposition, the first rule elegantly binds the second part of the tuple to the name value. Sweet!

Because pattern matching is intrinsic to F# programming, we'll see more of it in upcoming articles. As features supporting pattern matching are introduced in this series, we'll build on the basics presented here.

Next up: the option type. See you then!

posted on Tuesday, February 19, 2008 7:39:00 AM (Pacific Standard Time, UTC-08:00)  #    Comments [5]

kick it on DotNetKicks.com