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.