« Bracing | Main | Fiction has to make sense »

July 13, 2010

F# pattern matching for beginners, part 3: guards

In the last instalment, we saw how F# patterns can pick apart structured data and match on the values within those structures.  For value matching, however, we managed to get away with only exact matches: for example, matching on the Boolean constant patterns true and false; or on the discriminator of a discriminated union, which is like matching on the values of an enum.  This invites the question: what if we want to differentiate between values, but can’t list all the values we want to give special handling to?  For example, what if we want to handle odd and even numbers differently, or positive and negative numbers?

Obviously, one solution is to bring out ye olde if keyword and bust expressions old skool:

let hotpo opt =
  match opt with
  | None -> None
  | Some n -> if isOdd n then
                Some (3 * n + 1)
              else
                Some (n / 2)

Although this works, it’s not the people’s choice, and it’s worth digressing briefly to discuss why.

The shape of things to avoid

The nice thing about pattern matching is that, in addition to decomposing structured data – that is, extracting values of interest – it concisely expresses the control flow around those values.  In essence, it allows you to quickly see the different cases that a function considers, and what data is relevant in each of those cases.  Take our integer parsing example from the last instalment:

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

Just by looking at the patterns, you can see that this function deals with two cases: where the first element of TryParse matches false, in which case nothing else matters, and where the first element of TryParse matches true, in which case the second element does matter.

Using an if expression in a result expression defeats this readable flow.  In the hotpo function, the Some case has its own internal control flow which is not obvious from the patterns alone: the patterns make it look like all Some values are handled in the same way.  Our control flow has been split across the pattern matching which marches down the left hand edge of the code and the code blocks that sit on the right hand side.

In fact, the very shape of the hotpo function on the page should make you a little queasy.  At the top, you have a nice compact block of code bunched up against the left margin.  But half way down, the code suddenly lurches to the right, leaving a great empty space on the left.  This visual discontinuity reflects a discontinuity in the code: from control flow through the pattern specifications to control flow within the pattern handler.

You keep using that word “brief.”  I do not think it means what you think it means.

To restore equilibrium, we need a way to move the control flow back into the patterns, while still retaining the additional flexibility that the if statement gives us over exact matches.

F# provides exactly this in the form of guards.  A guard is a condition that must be satisfied for the pattern to match, and is introduced by the when keyword.  The body of a guard is a boolean expression, just like the condition of an if statement.  Crucially, guards can use the values of variable patterns, and almost always do.

Once we have guards, the flow of the hotpo function becomes much clearer:

let hotpo opt =
  match opt with
  | None -> None
  | Some n when isOdd n -> Some (3 * n + 1)
  | Some n -> Some (n / 2)

In this version of hotpo, it’s obvious by scanning down the list of patterns that Some odd number is a different case from Some anything else.  You don’t need to dive into the result expression to realise that there’s additional logic at work.

Incidentally, note that we could not have got away with our third pattern being Some n when not (isOdd n).  As discussed in part one, a match statement has to cover every possible input – and F# has to be able to prove it.  And F# can’t drill into guards to make sure that the set of guards is comprehensive (can you say equivalent to the Halting Problem? I knew you could!).  So even if we had written a guard for the even case, we would still need a fallthrough Some _ case to satisfy the compiler, even if all it did was throw an exception.

When patterns aren’t enough

F# imposes some constraints on what you can express with patterns alone, and guards provide a way of getting around these constraints.

For example, suppose you want to match on a value, but you don’t know that value at compile time.  You might try something like this:

let anyEqual pair candidate =
  match pair with
  | (candidate, _) -> true

Rather surprisingly, this always matches.  To see why, bring on the old printf debugging:

let anyEqual pair candidate =
  match pair with
  | (candidate, _) -> printfn "%A" candidate; true
> anyEqual (1, 2) 3;; 
1 
val it : bool = true

So it seems that candidate is being interpreted as a variable pattern, which means that it matches anything – because that’s what variable patterns do – and introduces a new variable, which happens to shadow the candidate parameter.  F# doesn’t care that there’s already a value in scope called candidate: we might as well have called the variable pattern x or foo or bozo_the_clown.

How do we fix anyEqual up to check the tuple elements against the candidate parameter?  The answer is to use a guard:

let anyEqual2 pair candidate =
  match pair with
  | (a, _) when a = candidate -> true
  | (_, a) when a = candidate -> true
  | _ -> false

It’s not as concise as our first attempt, but it has the great benefit of actually working.

Another handy use for guards is to express relationships between matched values.  Suppose we want to determine whether a pair contains two equal values.  We might be tempted to get cute and put the same variable in both slots of a pair pattern:

let theSame_fail pair =
  match pair with
  | (a, a) -> true
  | _ -> false

Unfortunately this won’t even compile, failing with error FS0038, “If you want Prolog, buster, you know where to get it.”  F# isn’t going to try to unify the two a patterns for us.

Once again, guards come to the rescue.  We can express our intent using two different variable patterns and a guard which requires the variable values to be the same:

let theSame pair =
  match pair with
  | (a, b) when a = b -> true
  | _ -> false

And all is now well –

No, hang on, all is not well.  How come these functions only work on pairs?  What if I need to check triples?  Do I have to make a function for every number of slots?

In reality, you wouldn’t write functions like anyEqual and theSame to take tuples, precisely because a tuple has a fixed number of elements (in our implementations, two elements).  You’d want them to have the flexibility to handle any number of elements.  But that means the function input has to be a more flexible data structure like a list.  Can we decompose such a structure using patterns, or is it just a crazy dream?

If you picked ‘crazy dream,’ you might want to brush up on Rhetorical Questions 101.  Otherwise, stay tuned.


Acknowledgements: For assistance with the phrase “bust expressions old skool,” I am indebted to Mr J Story.

July 13, 2010 in Software | Permalink

TrackBack

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

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

Comments