« May 2010 | Main | August 2010 »

July 25, 2010

F# pattern matching for beginners: index

This post provides links for the F# pattern matching for beginners series.

1. Getting started with the F# match keyword and some seemingly trivial but important patterns.

2. Decomposition of tuples and discriminated unions to pick out the interesting bits of data in each case

3. Guards allow you to inject custom logic into match cases

4. Lists and recursion using patterns

5. More useful patterns

6. Active patterns, a way to extend the pattern system with your own encapsulated reusable abstractions

The complete F# patterns documentation is here.

July 25, 2010 | Permalink | Comments (1) | TrackBack

F# pattern matching for beginners, part 6: active patterns

I talked earlier about how you could incorporate custom logic into patterns by using guard clauses.  Guards are fine for picking out special cases from a more general match, but they have a few limitations.

First, as I noted, guards are opaque to F#.  So if you’re matching integers and have one guard for picking out odd numbers and one for even numbers, you still need a fallthrough case.  You know that the odd and even guards are exhaustive, but the F# compiler can’t prove it, so it demands a useless “any other” pattern.

Second, guards aren’t reusable.  If you’ve got some classifying logic that you want to use in more than one place, you’re going to end up with duplicate guards.

Third, guards are simple predicates: they don’t perform any decomposition the way that patterns do.  So if you guard checks for a particular piece of information, and you want to use that piece of information in the result expression, you end up duplicating the logic to extract that piece of information.

To address these issues, F# provides a way for you to define your own extensions to the pattern system.

Active patterns

An active pattern is a reusable function that can classify and/or decompose its input.  Matching against an active pattern runs the classification logic, and makes the results of the decomposition available for further pattern matching.

That sounds a bit abstract, so let’s look at a simple example.  Here’s another take on the hotpo function from part 3:

let hotpo n =
  match n with
  | Even -> n / 2
  | Odd -> 3 * n + 1

This is pretty self-explanatory, but where did those Even and Odd patterns come from?  They look a bit like a discriminated union pattern, but that can’t be right, because n is an integer, and an integer wouldn’t be matching against a discriminated union.  Rather, they are partitions of an active pattern defined as follows:

let (|Even|Odd|) n =
  if n % 2 = 0 then Even else Odd

The syntax of an active pattern is like that of a function, except that instead of a name, the active pattern has a list of partition names, separated by | characters and enclosed in banana brackets (the (| |) construct).  The body of the active pattern is just like a normal F# function, and must return one of the partitions.

Active patterns can be decomposing

In the example above, the even/odd pattern just classifies its input.  One of the nice things about pattern matching, though, is the way that patterns can decompose their input, extracting data that is useful to a result expression.

We can extend the even/odd pattern, for example, to extract the halved value of the even case.  (This is a rather silly example for simplicity; we’ll see a better one in a moment.)  To do this, we just pass the desired extracted value to the partition constructor:

let (|Twice|Odd|) n =
  if n % 2 = 0 then Twice (n / 2) else Odd

Note how the Twice case takes n / 2 as an argument.  This enables a Twice pattern to get at that halved value:

let hotpo n =
  match n with
  | Twice m -> m
  | Odd -> 3 * n + 1

How about a more realistic example?  The following active pattern matches .NET Type objects, and classifies them according to whether they are nullable types (in which it case it extracts the underlying type), generic types (in which case it extracts the generic type definition and the type parameters) or anything else.

let (|Nullable|Generic|Simple|) (t : Type) =
  if (t.IsGenericType) then
    match Nullable.GetUnderlyingType(t) with
    | null -> Generic (t.GetGenericTypeDefinition(), t.GetGenericArguments())
    | ut -> Nullable ut
  else
    Simple

We can use this pattern to crack open type definitions and format them in different ways:

let rec csharpString typ =
  match typ with
  | Nullable t -> t.Name + "?"
  | Generic (g, typeParams) -> 
      sprintf "%s<%s>" 
        g.Name
        (Array.reduce (fun s1 s2 -> s1 + ", " + s2) (Array.map csharpString typeParams))
  | Simple -> typ.Name

Active patterns don’t have to classify

An interesting use of active patterns is to decompose a composite type without classifying it.  You can use a different active pattern depending on which way of decomposing the data is useful in the case at hand.

Consider the case of complex numbers.  A complex number can be represented in two ways: as real and imaginary parts, or as a modulus and angle.  The first representation is easier to work with when you want to add complex numbers; the second is easier when you want to multiply them.  By using active patterns, we can crack open complex numbers in different ways for different operations.

type Complex = { Re : float; Im : float }


// assume complexFromRect and complexFromPolar utility functions

let (|Rect|) c =
  match c with
  | { Complex.Re = re; Complex.Im = im } -> (re, im)

let (|Polar|) c =
  match c with
  | { Complex.Re = re; Complex.Im = im } -> (sqrt(re * re + im * im), atan2 im re)

let sum c1 c2 =
  match (c1, c2) with
  | (Rect (re1, im1), Rect (re2, im2)) –> complexFromRect (re1 + re2, im1 + im2)

let product c1 c2 =
  match (c1, c2) with
  | (Polar (r1, theta1), Polar (r2, theta2)) –> complexFromPolar (r1 * r2, theta1 + theta2)

The Rect and Polar active patterns don’t classify complex numbers into different partitions, but they do decompose complex numbers into values that are useful for different scenarios.  A similar example might be decomposing colours into RGB or HSB values depending on what you want to do with them.

Notice that an active pattern that doesn’t classify doesn’t need to return a discriminated type.  Rect and Polar both return tuples: we don’t have to prefix the return values with the case names the way we did in the Twice|Odd and Nullable|Generic|Simple examples.

Partial active patterns

Sometimes an active pattern doesn’t want to match every possible input.  A pattern which recognises and parses numbers from strings might match strings of the form “123” but not “xyzzy.”  You can create such a partial active pattern by specifying a wildcard (_) as part of the pattern name.

A partial active pattern can have only one non-wildcard partition, so it can only classify into “matches” or “doesn’t match.”  It represents the result as a F# option type, i.e. Some or None, rather than using the partition name.  Here’s an example:

let (|Integer|_|) s =
  match Int32.TryParse(s) with
  | (true, n) -> Some n
  | _ -> None

If you need multiple tests, you just have to create multiple partial patterns:

let (|Float|_|) s =
  match Double.TryParse(s) with
  | (true, d) -> Some d
  | _ -> None

And use them in the right order if they overlap:

let describeNumber s =
  match s with
  | Integer n -> sprintf "%d : int" n
  | Float d -> sprintf "%f : float" d
  | _ -> "call that a number? cos I don't"
> describeNumber "123";; 
val it : string = "123 : int" 
> describeNumber "456.78";; 
val it : string = "456.780000 : float" 
> describeNumber "bob";; 
val it : string = "call that a number? cos I don't" 

Parameterised active patterns

I described an active pattern as a function that classifies and optionally decomposes its input.  But what if your classification function needs inputs other than the value to be classified?  Our even/odd active pattern works fine for detecting multiples of two, but sometimes one needs to detect multiples of other numbers.  Of course, we could write similar active patterns for those other numbers, but these will be identical to the even/odd pattern except for a “multiple of what” parameter.  What we’d prefer is a way to parameterise the active pattern with that “multiple of what” value, so that we can write the active pattern once and just reuse it with different parameters.

We can do this by simply supplying additional parameters to the active pattern before the matchable input:

let (|MultipleOf|_|) (multiplicand : int) (n : int) =
  Some (n / multiplicand, n % multiplicand)

To use the parameterised active pattern, place the parameter before the pattern that is going to receive the match result – i.e. parameters go in the same order as in the pattern definition:

let toqpo n =
  match n with
  | MultipleOf 3 (m, 0) -> m
  | MultipleOf 3 (_, r) -> 4 * n + (3 - r)
  | _ -> 0
> toqpo 3;; 
val it : int = 1 
> toqpo 4;; 
val it : int = 18 
> toqpo 5;; 
val it : int = 21

Parameterised active patterns must always be partial (and consequently do not classify).  This is because an evil match expression could change parameters between cases, so that none of the supposedly exhaustive classifications ended up matching:

let (|ExactMultiple|RemainderedMultiple|) (multiplicand : int) (n : int) =
  if (n % multiplicand = 0) then
    ExactMultiple (n / multiplicand)
  else
    RemainderedMultiple ((n / multiplicand), (n % multiplicand))

// what happens when n = 6?
let ohNoes n =
  match n with
  | ExactMultiple 4 m -> m
  | RemainderedMultiple 3 (m, r) -> 4 * m + r

Rather annoyingly, the compiler will not complain when you define a non-partial parameterised active pattern; instead, it will emit a rather cryptic error when you use it.

Summary

Active patterns come in four related varieties:

  • Multi-case, like our Even|Odd and Nullable|Generic|Simple patterns.  A multi-case pattern partitions the entire input space, and optionally decomposes it.  Different partitions can be decomposed in different ways.
  • Single-case, like our Rect and Polar patterns.  A single-case pattern doesn’t classify the input, but typically decomposes it in a useful way.
  • Partial, like our Integer and Float patterns.  A partial pattern matches a chunk of the input space, and optionally decomposes inputs in that chunk.  It doesn’t classify any further within that chunk.
  • Parameterised, like our MultipleOf pattern.  A parameterised pattern does the same job as a partial pattern, but is, well, parameterised so you can reuse the pattern logic with different settings.

I’ve tried to keep things simple in this overview, but I’d recommend Chris Smith’s articles on active patterns if you want to see more in-depth examples of where active patterns really start to pull their weight.

July 25, 2010 in Software | Permalink | Comments (1) | TrackBack

July 24, 2010

Report on planet three

Perigo Minas: “The dominant life form is a sedentary plant group called ‘Grass’. The group comprises a number of individual species, who largely live separately in their own ethnic groups… While the presence of colonies across the planet indicate that in the past the Civilised Grasses have been willing to wage war on each other, most aggression has been directed at the Uncivilised Grass. In this, the Civilised species use their Human slaves to further manage beasts of war. Our Observers have recorded the use of large quadrupeds of a number of species, but mostly of the kind known as ‘Cattle’, to attack Grass in a most barbaric way.”

Yeah, I get this way too after reading The Extended Phenotype.

July 24, 2010 | Permalink | Comments (0) | TrackBack

F# pattern matching for beginners, part 5: more useful patterns

In this part, I want to briefly mention some useful patterns that I haven’t covered in the previous instalments.  I’m not going to cover everything, but if you want to know more, the F# documentation contains a full list of patterns with examples.

Record patterns

In addition to tuples, F# supports record types, which have named members like C# or Visual Basic classes.  A record pattern is like a tuple pattern, but identifies members by name instead of by position.  It uses curly brace syntax, with semicolon separators if multiple fields are involved in the pattern.

type Person = {
  Name : string;
  Age : int
  }

let isBob person =
  match person with
  | { Person.Name = "bob" } -> true
  | _ -> false
> isBob { Name = "bob"; Age = 40 };; 
val it : bool = true 
> isBob { Name = "alice"; Age = 50 };; 
val it : bool = false

Obviously, you’re not restricted to a constant expression: you can use a variable expression to capture the decomposed values:

let getAgeIfBob person =
  match person with
  | { Person.Name = "bob"; Person.Age = age } -> Some age
  | _ -> None

Type testing

A type test pattern is like the C# is operator: it matches if the matched item is an instance of the specified type.  Its syntax is :? followed by the type name.  The result of a successful match is strongly-typed to the specified type, and you can use an as pattern to capture this strongly-typed value into a variable so you can access type-specific members.

let sizeof (obj : Object) =
  match obj with
  | :? int -> Some 4
  | :? string as s -> Some s.Length
  | _ -> None
> sizeof 123;; 
val it : int option = Some 4 
> sizeof "hibble bibble";; 
val it : int option = Some 13 
> sizeof DateTime.Now;; 
val it : int option = None

Note we could not have called Length on obj directly, because the F# compiler would complain that Object doesn’t have a Length property.  Hence the need to capture the result of the :? string pattern: the F# compiler knows that this is of type string, so it is safe to access the Length property.

Other patterns

For other patterns defined by F#, see the Patterns topic in the documentation.

But what if you have classification and decomposition logic that can’t be readily expressed using the compiler-defined patterns?  In the final part of this series, we’ll look at how you can extend the F# pattern system with your own active patterns.

July 24, 2010 in Software | Permalink | Comments (0) | TrackBack

July 19, 2010

Many worlds

John Gravois: “Google maintains thirty-two different region-specific versions of its Maps tool for different countries around the world that each abide by the respective local laws. Thus on India’s version of Google Maps, for example, all of Kashmir appears as an integral and undisputed part of the country—because Indian law sees it that way. Similarly, ‘Arunachal Pradesh’ is nowhere to be found on ditu.google.cn. What you find instead are all the same Chinese place-names that caused the uproar of Google Maps in August.”

July 19, 2010 in Current Affairs, Web | Permalink | Comments (0) | TrackBack

Pass the crop circle palmistride, please

Crispian Jago: The Periodic Table of Irrational Nonsense.  Major groups include Dipshits, Fucktards and New Age Bollocks.  (Via Ian Randall.)

July 19, 2010 in Science | Permalink | Comments (2) | TrackBack

July 18, 2010

F# pattern matching for beginners, part 4: lists and recursion

We looked in part two at structural patterns and how you could use them to decompose a tuple or discriminated union, extracting the values of interest into variables on a case-by-case basis.

The limitation of tuples and discriminated unions is that their structure is fixed.  A 2-tuple (pair) is a different type from a 3-tuple (triple): you’d have to write different patterns to match them.  What if you wanted a pattern to decompose a collection that might be of arbitrary size?

List and array patterns

List and array patterns match lists and arrays respectively, with a pattern for each element of the list or array.  A list pattern looks eerily like a F# list literal, with square brackets around it and semicolons separating the element patterns:

let listingTroll list =
  match list with
  | [] -> "empty"
  | [a] -> sprintf "just %A" a
  | [a; _] -> sprintf "two elements beginning with %A" a
  | _ -> "lots of elements"
> listingTroll ["alice"; "bob"];; 
val it : string = "two elements beginning with "alice"" 
> listingTroll [1; 2; 3];; 
val it : string = "lots of elements" 
> listingTroll [1];; 
val it : string = "just 1" 
> listingTroll [];; 
val it : string = "empty"

An array pattern looks similar, except that it uses pipe characters inside the square brackets ([| … |]).

As always, we can use whatever patterns we like in each slot of the list or array pattern – wildcard, variable, literal, tuple, discriminated union, list, array, whatever.

The trouble with the list and array patterns is that they perform slot-by-slot matching, so although you can now have patterns for different numbers of slots, you still have to anticipate the number of slots at compile time.  The list and array patterns don’t let you write a pattern match to handle lists or arrays of unknown length.

The cons pattern

The oddly named cons pattern provides a way to match on the head and tail of a list – that is, the first element and the remaining elements.  Its syntax is two slots separated by a double colon: head :: tail.

(The name is for symmetry with the cons operator, which is also a double colon.  The cons operator constructs a list from a head and a tail.  For example, 1 :: [2; 3] evaluates to [1; 2; 3].)

The important thing about the cons pattern is that it doesn’t care how long the tail is, or even if the tail is empty: it just checks that there is a head element, splits that off, and deems everything else to be the tail.

Initially, this may seem a bit restrictive, because cons only lets you get at the first (head) element, and everything else remains in a list:

let consTroll list =
  match list with
  | [] -> "empty"
  | head :: _ -> sprintf "starts with %A" head

This may seem unhelpful, because if we know the size of the tail list in advance, then we haven’t really gained anything by using the cons pattern, and if we don’t know the size of the tail list in advance, the only way we can work with it is by using the cons pattern again.

Wait.  Can you hear singing?

Enter recursion

If you’ve been programming for longer than about three minutes, you’ll be familiar with recursion.  The essence of recursion is that you reduce a problem to a similar but simpler or smaller problem, which is then either trivial or susceptible to the same kind of reduction.

What does this have to do with list processing using the cons pattern?  The cons pattern decomposes a list into a single element and a shorter list.  And a shorter list is a smaller problem; it might even be so short that it’s empty, which gives you a trivial problem that can be handled by the fixed-length list pattern.  So the cons pattern enables you to pattern match recursively, splitting off one head element at each stage.  Combined with the trivial case of the empty list, this allows you to use pattern matching to create recursive functions that work on lists of unknown length.

This may sound a bit theoretical, so let’s look at a simple example.

let rec length list =
  match list with
  | [] -> 0
  | _ :: tail -> 1 + length tail

You can guess what this does.  Yes, you can.

> length [1; 2; 4; 8];; 
val it : int = 4 

But how does it do it?

Let’s dispose quickly of a tangential but important detail.  The length function is declared not using let, but let rec.  F# requires the rec wart when a function calls itself: if you don’t provide it, F# will complain on the last line that the length function isn’t defined yet.

Now, on to the pattern matching.  The length function defines two cases.

The first case is a list pattern.  You can recognise this by the square brackets.  Since there are no other patterns inside the square brackets, this will match only the empty list.  And an empty list surely has a length of 0.

The second case is a cons pattern.  This will match any list with a head that matches the wildcard pattern – that is, any head at all – and any tail.  In effect, the second case matches any non-empty list.  (Remember, the cons pattern allows an empty tail.  So even if the list has only one element, the cons pattern still matches.)  But the second case captures the tail of the list – that is, everything except the head – into the variable tail, and calls the length function on that.  In the second case, the length of the list is the length of the head, which is always 1, plus the length of the tail, whatever that might be.

This is an obvious case of recursion.  The length function either reduces its argument to a simpler case – a shorter list – or detects a trivial case and returns immediately – the empty list.

Here are a couple of less trivial examples:

let rec doAll f list =
  match list with
  | [] -> []
  | head :: tail -> f head :: doAll f tail
> doAll (fun n -> n * n) [1; 2; 3];; 
val it : int list = [1; 4; 9] 
let rec aggregate f seed list =
  match list with
  | [] -> seed
  | head :: tail -> aggregate f (f seed head) tail
> aggregate (fun m n -> m + n) 0 [1; 2; 3; 4];; 
val it : int = 10 

The doAll and aggregate functions take a function and a list and apply that function across the list.  You’ll recognise them as the LINQ Select and Aggregate methods.  They work by matching the cons pattern to recurse from a list to a shorter list, and bottoming out the recursion by matching the empty list.  They really differ only in the way that they combine intermediate results to make the final one and in the base case result.  For example, doAll combines the intermediate results by consing them up into a new list, and its base case is the empty list (because applying a function to all members of an empty list would surely result in an equally empty list).

So doAll does its work like this:

  • doAll square [2; 3]: cons pattern matches with head = 2 and tail = [3], so the value will be 4 :: doAll square [3].  (4 is square 2.)
    • doAll square [3]: cons pattern matches with head = 3 and tail = [], so the value will be 9 :: doAll square [].
      • doAll square []: empty list pattern matches, so the value is [].
    • 9 :: [] evaluates to [9].


  • 4 :: [9] evaluates to [4; 9] and this is the result of the entire match expression.

aggregate does its work in a similar way, but returning the seed value in the empty case, and combining results using the aggregation function instead of by consing.

So the cons pattern allows us to recursively decompose a list, and use the result expression to recursively stitch the decomposed list back together again.

What I have just told you is wrong

I’ve tried to present the use of the cons pattern and recursion in as simple a way as possible.  However, naive recursion doesn’t work with very long lists, because the stack overflows.  In reality, therefore, F# prefers to transform recursive expressions so it can use tail recursion, which is basically a kind of recursion that doesn’t require stack frames.  Unfortunately, this transformation makes the code rather more complicated, and distracts from the pattern matching side of things, so I’ve chosen to skip it for now.  If you’re writing F# code to operate on moderately large data sets, though, it’s something you’ll need to know about.

Enough with these new-fangled lists.  What about arrays of unknown length?

You are stuffed.  But on the positive side, I hear Visual Basic has really good support for arrays.  Check it out!

July 18, 2010 in Software | Permalink | Comments (3) | TrackBack

July 15, 2010

I write like everybody in the whole world, ever

I succumbed to the I Write Like fad that’s going around at the moment, and tried pasting in various bits from a project I’m tinkering with.  Apparently my style is rather uneven, since I was told from successive fragments that I write like Douglas Adams, Margaret Atwood, Stephen Kind, Chuck Palahniuk, Vladimir Nabokov and James Joyce.

Most awesome of all, however, was when I pasted in one of the articles on F# pattern matching, and was told that it was a dead ringer for… Dan Brown.  Yes.  That Dan Brown.

I am not sure whether this says more about my writing style, or about Dan Brown’s.

July 15, 2010 | Permalink | Comments (11) | TrackBack

July 13, 2010

Fiction has to make sense

It looks like world + dog has already linked to this, but whatever: World War II as a badly scripted TV story arc.  (Via Ken MacLeod.)

July 13, 2010 | Permalink | Comments (0) | TrackBack

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 | Comments (0) | TrackBack