Navigate / search

Active Patterns: Pattern Matching

This entry is part 1 of 8 in the series Active Patterns

After two posts here, and here complaining about the Single Case Active Pattern, it’s time to write the posts I’ve been trying to write all along about how active patterns are amazing.

This post will lay the groundwork by covering pattern matching, and introducing the concept of active patterns. Subsequent posts will cover the various types of active pattern in detail.

Destructuring Assignment
Thanks to Miles McGuire for setting me straight on the name.

FSharp is full of little nice ideas that you appreciate when you come from a C# background, and destructuring assignment is one of them. Take a look at the following.

let date = (21, 8, 2014)

let d, m, y = date
val y : int = 2014
val m : int = 8
val d : int = 21

let _, month, year = date
val year : int = 2014
val month : int = 8

That’s a tuple representing a date. To extract values from the tuple and assign them to the three variables d, m and y we can do a single assignment. The tuple gets deconstructed (think constructor in reverse).

In the second assignment we use the _ to indicate that we don’t care about the first value in the tuple. It will create two variables month and year.

That alone is pretty nice, but it gets better.

Pattern Matching
Destructuring assignment is really a form of Pattern Matching, which is common in Functional Programming languages. In FSharp the match expression allows us to match against quite elaborate data structures.

First let’s take a look at a match expression that does little more than the assignment above.

let patternMatch date =
    match date with
    | d, m, y -> sprintf "Day [%d], Month [%d], Year [%d]" d m y   

With Pattern matching we can deconstruct the date just as we did in the assignment. The match expression allows us to create multiple match clauses, with the value of the overall expression being decided by the first clause that matches.

let partialPatternMatch date =
    match date with
    | _, _, y when y < 1960 -> "Nothing before the 60's matters"
    | _, m, 1960 -> sprintf "Ah the month was %d, the 60's were just beginning" m
    | _, 12, y -> sprintf "It was Christmas, %d" y
    | d, m, y -> sprintf "Day [%d], Month [%d], Year [%d]" d m y

Clauses can match based on a ‘when’ guard as in the first example above. We can also insert literal values into the pattern as with the year 1960 in the second case and the month 12 in the third. In both of those examples we match with any day because we use the underscore to indicate that we don’t care what the day is. Also in those examples we match the month and year respectively to variables (m and y) which can be used in the results.

In the final clause we are guaranteed to match any date that fails to match on any of the first three clauses. There are no literal values or when guards that could cause the last case to fail, we just get the day month and year, whatever they may be and can use them in the result.

Match Against Abstractions
As exciting as all that is, you’ll notice that like the assignment earlier, the pattern matching in a match expression really only matches against and/or extracts data that’s already there. We’re matching here on the raw numbers that are the underlying representation of the date. It would be nice to match on things like

  • May
  • First Quarter
  • Summer
  • Month End
  • Saturday
  • Holiday

These are all abstractions that should be independent of how the date is implemented. Active Patterns allow us to pattern match against these kinds of abstraction, rather than the underlying data.

Active Patterns
What we need is the matching and extracting of pattern matching, but with the added ability to transform the data we’re working with.

We already have a really good general purpose way of transforming data, namely functions, so it shouldn’t come as any surprise that Active Patterns are special kind of function with some extra powers that make them useful in pattern matching.

Active Patterns come in a few varieties so, the next couple of posts will describe the various options. Don’t worry too much about the notation below. All will become clear as you read through the examples.

OK, I haven’t explained what Total and Partial means yet. All in good time, but if you’re a little OCD like me you’ll notice that list doesn’t look quite complete, there is no “Multiple Partial”. The reason for that is very simple, the language designers haven’t added them yet, and may not add them at all.

“For completeness our specification includes structured names with multiple cases, e.g, (|ParseInt|ParseFloat|_|). However we have yet to detect any practical benefit in doing so.”[1]

We’re getting ahead of ourselves. Next Post (at last) an explanation of the Single Case Total Active Pattern, with an example I can stand over.

Active Patterns: Single Total (|A|)

This entry is part 2 of 8 in the series Active Patterns

Part 1 of this series was mainly sharpening the axe by covering some basics like Pattern matching. I also gave a general sense of what active patterns are (functions that can be used when pattern matching, such as in match expressions). Now it’s time to dig into the details.

As I mentioned previously there are arguably 5 variations of active patterns. This post will cover the first of those, the Single Total Active Pattern.

When we looked at plain old pattern matching we extracted and matched against values that were already there, by which I mean matching against a tuple like (21, 8, 2014) allowed us to match on the values 21, 8 and 2014 or any combination of them, but we couldn’t match against a values like ‘August’ or ‘Leap Year’.

Active Patterns allow us to do just that, we can take an input, transform it in some way and then match against the result of that transformation.

Let’s try a simple example.

let (|UpperCaseCount|) (str: string) =
    str.ToCharArray()
    |> Array.filter (fun c -> c.ToString() = c.ToString().ToUpper())
    |> Array.length

let UseThePatternLuke (str: string) =
    match str with
    | UpperCaseCount 4 -> "Bingo 4 is the magic number"
    | UpperCaseCount u -> sprintf "Nah %d upper case characters is no good" u

Active Recognizers
The first thing to note is the highlighted line. In particular those funny parenthesis around (|UpperCaseCount|). Those (|…|) are “banana clips” and they denote a special kind of function known as an ‘Active Recognizer’. These functions do the heavy lifting for Active Patterns. They accept the source data, break it up, transform it and output it in a form that can be matched against.

From the perspective of match expressions and assignments the pattern matching works exactly like the plain old pattern matching we saw in the last post. The difference with Active Patterns is that the Active Recognizer function has gotten in and transformed the data before the matching happens.

The”banana clips” above only enclose one value so this is a Single Total Active Pattern.

The significance of this will become more apparent when we look at the remaining kinds in subsequent posts.

We’re matching against a string, but the property of the string we’re interested in is the number of upper case characters. So, we define an active recognizer that takes a string, and returns the number of upper case characters.

Apart from those Banana Clips it looks like an ordinary function. I’ve mentioned in previous posts that the Single Total Active Pattern can be a little hard to explain because simply using a function almost always seems like a better idea. If you’re skeptical, stay with me (I’ve been there).

For simple pattern matching, there’s just the “match x with” code, or the destructuring assignment. For Active Patterns you define the active recognizer separate from the pattern match. Basically you pull some logic out into it’s own function. Nothing magical.

Here’s the same code with some scribbles to try and convey the relationship between the active recognizer and the pattern matching.

And here, after much head-scratching is an attempt at an example which is simple enough for anyone to understand, but where just using functions might not have been as clean.

let (|IsPalindrome|) (str: string) =
    str = String(str.ToCharArray() |> Array.rev)

let (|UpperCaseCount|) (str: string) =
    str.ToCharArray()
    |> Array.filter (fun c -> c.ToString() = c.ToString().ToUpper())
    |> Array.length

let (|LowerCaseCount|) (str: string) =
    str.ToCharArray()
    |> Array.filter (fun c -> c.ToString() = c.ToString().ToLower())
    |> Array.length

let (|SpecialCharacterCount|) (str: string) =
    let specialCharacters = "!£$%^"
    str.ToCharArray()
    |> Array.filter (fun c -> specialCharacters.Contains(c.ToString()))
    |> Array.length


let (|IsValid|) (str: string) =
    match str with
    | UpperCaseCount 0 -> (false, "Must have at least 1 upper case character")
    | LowerCaseCount 0 -> (false, "Must have at least 1 lower case character")
    | SpecialCharacterCount 0 -> (false, "Must have at least 1 of !£$%^")
    | IsPalindrome true -> (false, "A palindrome for a password? What are you thinking?")
    | UpperCaseCount u & LowerCaseCount l & SpecialCharacterCount s -> (true, sprintf "Not a Palindrome, %d upper case, %d lower case and %d special characters. You're good to go!!!" u l s)

I’ve actually defined a couple of different Active Recognizers, each of which transform the string in different ways. The pattern match can then use any combination of the four patterns.

We can match against literal values like true and 0, or we can match against variables as in the last case.

The highlighted line shows one of the real advantages of active patterns over simple functions. We call three functions, store the returned values and use them, all in one line.

Actually I was a little cheeky, even my IsValid “function” is actually an Active Recognizer, I can use it as follows

let checkPassword (password: string) =
    match password with
    | IsValid (true, _) -> "OK"
    | IsValid (false, reason) -> reason

This would also work

let checkPassword (password: string) =
    match password with
    | IsValid (false, reason) -> reason
    | _ -> "OK"

One final quirk of the Single Total Active Pattern is that you can use it like this.

> let (IsValid result) = "$TArAT$";;

val result : bool * string =
  (false, "A palindrome for a password? What are you thinking?")

The value on the right of what looks like an assignment is sent to the Active Recognizer, and the result of the Active Recognizer is then bound to the variable ‘result’.

What’s going on here is simply the same Destructuring Assignment we saw in the first post, but using an Active Pattern instead of simple Pattern Matching. For more on this, and on the Single Total Active Pattern I strongly recommend Luke Sandell’s excellent (and concise) blog post.

Don’t get too hung up the Single Total Active Pattern. In many cases a simple function will work and be as clear or maybe even clearer than the Active Pattern equivalent.

That said, understanding what’s going on with this type of Active Pattern will make it very easy to grasp the rest, and once you know how to use a new tool, it becomes easier to see places where it can work.

Active Patterns: Single Total With Params (|A|) x

This entry is part 3 of 8 in the series Active Patterns

We move on to the next in our series on Active Patterns, but this time we’re really just covering a slight modification to the Single Total pattern that we covered in the last post.

All the same rules apply, we’re just adding the ability to add parameters to the Active Pattern.

I say ‘parameters’ but in reality I mean ‘additional parameters’. Every Active Pattern has at least one parameter. The ‘x’ in ‘match x with’ has to go somewhere.

Remember the Active Patterns we’ve seen so far are just functions. If you take away the banana clips they are identical to functions. Additional parameters are supported exactly the same way they are with regular functions.

All you need to remember is that the ‘x’ in ‘match x with’ will be passed to the last parameter of the Active Pattern. The other parameters are set by the individual lines in the Pattern Match expression.

An example might help.

Here’s the Active Pattern we used in the last post to count special characters in a string.

let (|SpecialCharacterCount|) (str: string) =
    let specialCharacters = "!£$%^"
    str.ToCharArray()
    |> Array.filter (fun c -> specialCharacters.Contains(c.ToString()))
    |> Array.length

Note the special characters are hard coded. This being a function it’s simple to turn that into a parameter.

let (|SpecialCharacterCount|) (characters: string) (str: string) =
    str.ToCharArray()
    |> Array.filter (fun c -> characters.Contains(c.ToString()))
    |> Array.length

You can add multiple parameters but it’s important to know how they map to the pattern matching expression that will use the Active Pattern.

Here’s code that would match against the old ‘non-parameterized’ Active Pattern

let UseThePattern (str: string) =
    match str with
    | SpecialCharacterCount c -> sprintf "That was %d special characters" c

By contrast here’s the code that uses the parameterized version

let UseThePattern (str: string) =
    match str with
    | SpecialCharacterCount "!£$%^" c -> sprintf "That was %d special characters" c

The ‘str’ in the match expression still gets passed to the last parameter of the Active Pattern, and the return value of the Active Pattern still gets assigned to ‘c’. In place of c you can still use literals just as in the last post.

The only real difference is that the extra arguments are placed between the name of the Active Pattern and the variable or literal value that we match against.

Here’s another sketch to try and hammer this home.

Apologies for spelling this out in such tedious detail but if you get what’s happening here, everything else about Active Patterns will be very simple.

Oh, and that little assignment trick we saw in the last post still works, just pass the arguments needed by the Active Pattern.

let (SpecialCharacterCount "!£$%^" c) = "ABC!"
val c : int = 1

That’s it for this post and for my nemesis the Single Total Active Pattern. Next up we discover the wonders of Partial Active Patterns. We get to rope in another interesting piece of F#, Option Types.

Active Patterns: Partial Application

This entry is part 4 of 8 in the series Active Patterns

This post was supposed to be about Partial Active Patterns, but before we get to that, I want to take a small diversion to cover Partial Application of Active Patterns (which is a completely different thing). Confused? Don’t worry. Read on.

Partial Application
I’ve described Partial Application in detail here and here, so I’m going to assume that you know how it works for regular functions. Please read those two posts if you are in any doubt.

Partial Application was raised in a question from Shawn Martin regarding this post.

what might be the best way(s) to turn SpecialCharacterCount in this post into the hard-coded SpecialCharacterCount from the previous post? In other words, do partial application.

Coincidentally Anthony Brown (@bruinbrown93) had tweeted on the same topic.

You can also partially apply your active patterns. E.g. let (|ExclamationMarkCount|) = (|SpecialCharacterCount|) “!”

So, let’s cover partial application of active patterns.

Recall our active pattern for counting occurrences of characters in a string.

let (|SpecialCharacterCount|) (characters: string) (str: string) =
    str.ToCharArray()
    |> Array.filter (fun c -> characters.Contains(c.ToString()))
    |> Array.length

In addition to the parameter ‘str’ for the string that we’ll search, we have a parameter ‘characters’ containing the characters that we’ll search for. We can use this, and the magic of partial application to create other Active Patterns that have the characters baked in, so we don’t need to provide them as an extra argument.

let (|CountDollars|) = (|SpecialCharacterCount|) “$”

We can use CountDollars just like any Active Pattern, but it’s hardwired to search for the ‘$’.

let describeString (s: string) =
    match s with
    | CountDollars d when d > 5 -> "%d is more than 5 Bucks" 
    | CountDollars 4 -> "That's 4 Bucks" 
    | CountDollars d -> "Just %d Dollars" d 

Creating more patterns that search for different characters is trivial

let (|CountStars|) = (|SpecialCharacterCount|) "*"

Now instead of counting dollars, we’ll be counting stars.
Yeah, I went there. Don’t judge me.

And, of course the argument to the original Active Pattern can contain multiple characters, and that still applies.

let (|CountCurrencies|) = (|SpecialCharacterCount|) "£$"

We can mix and match our original and newly minted patterns.

let describeString (str: string) =
    match str with
    | CountCurrency c when c > 3 -> "More than three currency symbols"
    | CountDollars d when d > 0 -> "There's at least one Dollar"
    | CountStars 2 -> "There are exactly two Stars "
    | SpecialCharacterCount "!%^&" s -> sprintf "I found %d special characters" s
    | _ -> str 

Patterns
The second topic I wanted to touch on before moving forward is Patterns. In the first post in the series I gave an introduction to Pattern Matching which has served us well in understanding the examples. It was however just the briefest of introductions, let’s dig a little deeper.

In the (|IsValid|) active pattern in this post I quietly slipped in something a little unusual. I used multiple Patterns within the same clause.

  | UpperCaseCount u & LowerCaseCount l & SpecialCharacterCount s -> ...

For that clause to match all three of those patterns need to match. This makes sense, the ‘&’ represents ‘and’.

All of the patterns that you can use are described here so I won’t go into each in detail. I will briefly mention the ‘or’ pattern denoted by the ‘|’ operator, to give you a sense of what these patterns can do.

Take a look at this function.

let describeString (str: string) =
    match str with
    | CountDollars c | CountStars c when c > 5 -> sprintf "%d is more than 5 Dollars or Stars" c
    | _ -> str 

If either CountDollars or CountStars returns a count of more than 5 then the first clause will match. If CountDollars returns more than 5 then c will hold it’s value. If not then there’s still the chance that CountStars will set the value of c. If neither are above 5 the clause in it’s entirety will fail. Note we’re not talking about the total of Dollars and Stars exceeding 5. Either Dollars or Stars must exceed 5 in it’s own right.

Literals can be used on both sides of the ‘|’ operator, but if a variable is used, it must be the same on both sides.

let describeString (str: string) =
    match str with
    | CountDollars c | CountStars c when c > 5 -> sprintf "%d Dollars or Stars, that's more than 5" c
    | CountDollars 2 | CountStars 10 -> "2 Dollars and 10 Stars"
    | _ -> str 

The following is not valid for the ‘or’ pattern.

   | CountDollars 2 | CountStars s -> sprintf "2 Dollars and %s Stars" s

I’ll leave you to play with the other patterns. In the next post we’ll get back to describing the different forms of Active Pattern.

Active Patterns: Single Partial (|A|_|)

This entry is part 5 of 8 in the series Active Patterns

I’ve referred to all of the Active Patterns we have seen so far in this series as ‘Single Total’. It’s time to look at the distinction between ‘Total’ and ‘Partial’ Active Patterns.

To understand Partial Active Patterns you need to have some understanding of Option Types’. If they are new to you, I’d encourage you to read up on them before continuing. A great place for reading about this, and F# generally is FSharpForFunAndProfit.

When we write a function to count the upper case characters in a string, there is always an answer, even if that answer is 0. Not all functions are so clear cut. If we write a function to parse a string into a number, it is possible to provide strings that simply can’t be parsed.

ParseNumber(“21”) // OK
ParseNumber(“Tango Foxtrot”) // What can we do with this?

All of the examples we’ve seen so far have involved Active Patterns that are just transformation functions. The match expression uses guards, literal values, variables and wildcards to decide how it will match on the returned value.

Partial Active Patterns take back some of that control. A ParseNumber active pattern can decide that it won’t match a value regardless of how the match expression is constructed. It does this by returning an Option Type. When it returns ‘Some Value’ the match expression will deal with that value just as before, but if the Active Expression returns ‘None’ then there is no match and the value falls through and must be handled by a different pattern.

Since we’ve been talking about parsing numbers, let’s look at an example.

let (|Number|_|) (str: string) =
    match Int32.TryParse(str) with
    | (true, n) -> Some(n)
    | false, _ -> None

The Active Pattern name now includes an extra component. The underscore (wildcard) indicates that this is a partial Active Pattern. Not every string that is passed to this pattern can be turned into a Number. We can use this in a match expression as follows.

let IsItANumber (str: string) =
    match str with
    | Number n -> sprintf "That was number %d" n
    | _ -> sprintf "Not a number"

Option Types are still valid types. You can return an option from a SingleTotal active pattern.

let (|Number|) (str: string) =
    match Int32.TryParse(str) with
    | (true, n) -> Some(n)
    | false, _ -> None

let IsItANumber (str: string) =
    match str with
    | Number (Some n) -> sprintf "That was number %d" n
    | _ -> sprintf "Not a number"

The remainder of the Active Pattern is identical, but, because we used the SingleTotal form of the Active Pattern we have to unpack the value n from the option type using the ‘Some’ keyword. By using the Partial Form of the active pattern we get that for free.

I’ll be honest I find that a little confusing because the signatures of both forms of the pattern are the same (string -> int option). Don’t worry too much about it (I don’t), if you are writing Single case Active Patterns that can’t match all possible inputs then use the Partial form.

The Infamous FizzBuzz
Let’s take another example of a Total Active Pattern and convert it to a Partial, and see what happens. Here is the infamous FizzBuzz

let (|Multiple|) m n =
    if n%m=0 then true
    else false

let (|Fizz|) = (|Multiple|) 3
let (|Buzz|) = (|Multiple|) 5

let FizzBuzz n =
    match n with
    | Fizz true & Buzz true -> "FizzBuzz"
    | Fizz true -> "Fizz"
    | Buzz true -> "Buzz"
    | _ -> n.ToString()

The Active Pattern (|Multiple|) returns a boolean indicating whether parameter ‘n’ is a multiple of ‘m’. Because it returns true or false, our match expression needs to specify those literals in order to catch the various cases.

Here’s the same code rewritten using Partials

let (|Multiple|_|) m n =
    if n%m=0 then Some Multiple
    else None

let (|Fizz|_|) = (|Multiple|_|) 3
let (|Buzz|_|) = (|Multiple|_|) 5

let FizzBuzz n =
    match n with
    | Fizz & Buzz -> "FizzBuzz"
    | Fizz -> "Fizz"
    | Buzz -> "Buzz"
    | _ -> n.ToString()

The booleans are gone, the Active Patterns now return Multiple, Fizz, Buzz and None leading to a cleaner match expression. Both those examples also use Currying and the ‘&’ pattern from the last post.

An Expression Evaluator
Let’s finish this post with one last example, a little more ambitious this time. We’ll start with a match expression and see if we can figure out the Active Patterns to make the magic happen.

let rec Eval str =
    match str with
    | Number x -> x
    | Addition (l, r) -> Eval(l) + Eval(r)
    | Subtraction (l, r) -> Eval(l) - Eval(r)
    | _ -> raise (System.ArgumentException("Invalid Expression " + str))

This function evaluates expressions. It seems to only handle Numbers, Addition and Subtraction so we’ll need Active Patterns for each of those.

It looks like the expression is represented as a string, but the pattern matching would be basically identical even if expression were represented in another way. That’s one of the perks at coding at a higher level of abstraction.

Number looks like the example we’ve already seen, let’s do that first.

let (|Number|_|) (str: string) =
    match Int32.TryParse(str) with
    | (true, n) -> Some(n)
    | false, _ -> None

Incidentally if that syntax for the TryParse function is throwing you a little, have a look at this post.

Both Addition and Subtraction accept strings and return what look like tuples representing the left and right subexpressions.

let (|Addition|_|) (str: string) =
    let SplitAt (op: string) (str: string) =
        let pos = (str.IndexOf op)
        (str.Substring(0, pos),str.Substring(pos + 1, str.Length - pos - 1))

    if str.Contains("+") then 
        Some (SplitAt "+" str)
    else
        None

let (|Subtraction|_|) (str: string) =
    let SplitAt (op: string) (str: string) =
        let pos = (str.IndexOf op)
        (str.Substring(0, pos),str.Substring(pos + 1, str.Length - pos - 1))

    if str.Contains("-") then 
        Some (SplitAt "-" str)
    else
        None

Some code duplication there, but it will work. Both patterns check the incoming string. If it contains the right operator the patterns split the string and returns either side as the elements of a tuple. The Eval function then takes those two subexpressions, recursively evaluates them and applies the right operator to bring the two expressions back together.

The next post will be very short and will show how to use parameters with Partial Active Patterns. This won’t need much explaining because it’s the same process as adding parameters to Total Active Patterns which you’ve already seen. We’ll use parameters to rewrite this expression evaluator and get rid of the duplicated code.

Active Patterns: Single Partial With Params (|A|_|) x

This entry is part 6 of 8 in the series Active Patterns

We close out the discussion of Single Active Patterns by adding parameters to the partial active pattern. If you’ve read the post on adding parameters to the Single Total Active Pattern then there is absolutely nothing new here, it works in exactly the same way.

For that reason I’m not going to use this post to explain how to do it, I’m just going to work through an example and leave it at that.

In the last post I created some active patterns that we could use to evaluate a rudimentary arithmetic expression. There was a lot of duplicated code between the Addition and Subtraction cases.

Here’s a first stab at eliminating some of that by extracting the underlying behavior and using Partial Application. This has all been covered already in this post.

Parsing numbers is handled just like it was before, no change here.

let (|Number|_|) (str: string) =
    match Int32.TryParse(str) with
    | (true, n) -> Some(n)
    | false, _ -> None

Now instead of fully implementing Addition and Subtraction independently of each other, we have a more general purpose pattern called (|BinaryOp|_|). Note that the operator (the text to look for in the expression) is an argument to this function.

let (|BinaryOp|_|) operator (str: string) =
    let SplitAt (op: string) (str: string) =
        let pos = (str.IndexOf op)
        (str.Substring(0, pos),str.Substring(pos + 1, str.Length - pos - 1))

    if str.Contains(operator) then 
        Some (SplitAt operator str)
    else
        None

Now creating our Addition and Subtraction patterns is simple.

let (|Addition|_|) = (|BinaryOp|_|) "+"
let (|Subtraction|_|) = (|BinaryOp|_|) "-"

And the Match works just like it did before, no change here.

let rec Eval str =
    match str with
    | Number x -> x
    | Addition (l, r) -> Eval(l) + Eval(r)
    | Subtraction (l, r) -> Eval(l) - Eval(r)
    | _ -> raise (System.ArgumentException("Invalid Expression " + str))

That’s all fine, but notice how our match expression needs to know how to respond to the Addition and Subtraction cases, this isn’t ideal.

    | Addition (l, r) -> Eval(l) + Eval(r)
    | Subtraction (l, r) -> Eval(l) - Eval(r)

We could do the following.

type Operator = string * (int->int->int)

The type ‘Operator’ consists of a string (the token) and a function int->int->int (I’m keeping things simple here, int only). Now our underlying BinaryOp pattern just doesn’t take a string to search for, it also takes a function to perform when that string is found.

let (|BinaryOp|_|) (operator: Operator) (str: string) =
    let token, operatorFunction = operator
    let SplitAt (op: string) (str: string) =
        let pos = (str.IndexOf op)
        (operatorFunction, str.Substring(0, pos),str.Substring(pos + 1, str.Length - pos - 1))

    if str.Contains(token) then 
        Some (SplitAt token str)
    else
        None

We use destructuring assignment to extract the token and the function from operator. The token is used to split the string, but the function is simply passed back from the pattern so that the calling match expression can use it.

Defining the Addition and Subtraction patterns is now slightly different, we need to include both the token and the function.

let (|Addition|_|) = (|BinaryOp|_|) ("+", (+))
let (|Subtraction|_|) = (|BinaryOp|_|) ("-", (-))

As mentioned above our match expression needs to be modified to get the function back from the active pattern so that it can apply it to the left and right subexpressions. Now that both Addition and Subtraction are handled identically, we can combine them using an or ‘|’ pattern.

let rec Eval str =
    match str with
    | Number x -> x
    | Addition (f, l, r) | Subtraction (f, l, r)
    		-> f (Eval(l)) (Eval(r))
    | _ -> raise (System.ArgumentException("Invalid Expression " + str))

And that’s it for Single Case Active Pattern both the Total and Partial variety. We’ve covered a lot of ground. In the next post we’ll move on the Active Patterns that have Multiple results. If you’ve managed to stay with me this far nothing that remains will phase you.

Active Patterns: Multi-Case (|A|B|)

This entry is part 7 of 8 in the series Active Patterns

Playing Cards are a commonly used example of discriminated unions in FSharp. I’m not presuming that you already understand Discriminated Unions, but I’m also not going to explain them. You should be able to follow along and get a sense of how they work. If you’d like to read up on them try here.

A Rank is something that can have one of 13 values Ace through King. A Suit can have one of 4 values Hearts, Clubs, Diamonds or Spades. A Card can be represented as a Tuple of Rank and Suit.

type Rank = Ace|Two|Three|Four|Five|Six|Seven|Eight|Nine|Ten|Jack|Queen|King
type Suit = Hearts|Clubs|Diamonds|Spades
type Card = Rank * Suit

As a brief aside take a look at the ‘*’ which indicates a tuple. Tuples are known as ‘product types’ their range of values are the product of the ranges of values of the types that make them up.

Let me try that again in English. 13 Ranks * 4 Suits = 52 Cards. I’ll pretend Jokers don’t exist, this series is long enough already.

(Two, Clubs)
(Queen, Hearts)
(Ace, Spades)

Cards have an interesting characteristic, every single one of them is either Red or Black. So, here’s a little challenge. Using what you’ve learned so far, write a function takes a card and returns a message like the following

(Two, Clubs) -> "The Two of Clubs is Black"
(Queen, Hearts) -> "The Queen of Hearts is Red"
(Ace, Spades) -> "The Ace of Spades is Black"

If you’re having trouble with that the following easier version will get you a passing grade.

(Two, Clubs) -> "Black"
(Queen, Hearts) -> "Red"
(Ace, Spades) -> "Black"

There are lots of ways we can approach this using the Single Active Patterns (both the Total and Partial varieties). All have drawbacks of one kind or another.

Single Total

Here’s how we could do it with a Single Total Active Pattern

let (|Red|) (card: Card) =
    match card with
    | (_, Hearts) | (_, Diamonds) -> true
    | _ -> false

let DescribeCard (card: Card) =
    match card with
    | Red true -> sprintf "Red" 
    | Red false -> sprintf "Black"

That’ll get us the passing grade but it’s pretty lousy. Black has vanished as a concept, all we have is “Not Red”, and within our match expression we’ve lost the details of the card, all we have is the boolean that tells us if it’s Red or not.

Partials
We can do better with two partials.

let (|Black|_|) (card: Card) =
    match card with
    | (_, Clubs) | (_, Spades) -> Some card
    | _ -> None

let (|Red|_|) (card: Card) =
    match card with
    | (_, Hearts) | (_, Diamonds) -> Some card
    | _ -> None

let DescribeCard (card: Card) =
    match card with
    | Black (rank, suit) -> sprintf "The %A of %A is Black" rank suit 
    | Red (rank, suit) -> sprintf "The %A of %A is Red" rank suit 

That’s better, but if you try that example you’ll see FSharp throws a warning in the DescribeCard function. It claims that we have an incomplete match pattern. FSharp is concerned that a card might come along that doesn’t match either Black or Red.

We know we’ve got our bases covered, but the use of Partials hides that fact from FSharp. What happens if a card comes along that gets ‘None’ from both (|Black|) and (|Red|). I knew those damn Jokers would bite us in the ass.

We could throw in a dummy catch all case that would get rid of the warning, but where’s the fun in that?

This, as it happens is an ideal scenario for a Multi-Case Active Pattern. We know that the full range of possible values for a card (i.e. all 52 cards) must map to one of a small set of possibilities (Red and Black). We can make that fact explicit using a Multi-Case active pattern and kill off a compiler warning in the process.

Multiple

let (|Red|Black|) (card: Card) =
    match card with
    | _,Hearts|_,Diamonds -> Red card
    | _ -> Black card

let DescribeCard (card: Card) =
    match card with
    | Red (rank, suit) -> sprintf "The %A of %A is Red" rank suit
    | Black (rank, suit) -> sprintf "The %A of %A is Black" rank suit

The partials are gone. There’s no more ‘Some card’ or ‘None’. Every card is classified as either a ‘Black card’ or a ‘Red card’. Our match expression doesn’t throw a warning any more because FSharp can understand that Red and Black are the Only possibilities for cards, and we handle them both.

Bringing It All Together
Let’s finish with a nice meaty example that brings together the various types of pattern we’ve covered. We’ll use Single and Multiple Active Patterns to pattern match and describe a hand of Blackjack cards. To keep things simple Ace will count as 11 only, it won’t also count as 1.

The points attached to each card are determined by the Rank. We’ll start with a function that scores a card.

let CardScore (card: Card ) = 
    match fst card with
    | Two -> 2
    | Three -> 3
    | Four -> 4
    | Five -> 5
    | Six -> 6
    | Seven -> 7
    | Eight -> 8
    | Nine -> 9
    | Ten | Jack | Queen | King-> 10
    | Ace -> 11

Our Active Patterns are going to look at hands and tell us something about them. Every hand has a Score so (|Score|) can be a Single Total Active Pattern. And, it’s really easy to write.

let (|Score|) (hand: Card List) =
    hand
    |> List.sumBy CardScore

The number of cards is also a Single Total Active Pattern, and a useful piece of information, as we’ll see in a moment.

let (|Cards|) (hand: Card List) =
    List.length hand

We now have everything we need to fit a hand of cards into one of five possibilities. A Multiple Active Pattern will work. Notice how the code is about as close to a description of the rules as you can get. We literally list the various types of hands. Blackjack is when we have 2 cards with a combined score of 21, A Pair is when we have two cards with the same Rank and we don’t care about the Suits.

let (|Bust|Blackjack|TwentyOne|Pair|Under|) (hand: Card List) =
    match hand with
    | Score s when s > 21 -> Bust
    | Cards 2 & Score 21 -> Blackjack
    | Score 21 -> TwentyOne
    | [(r1,_); (r2,_)] when r1 = r2 -> Pair r1
    | Score s -> Under s

Some of the cases simply identify the type of hand Bust, Blackjack, TwentyOne. Others package some information with the hand type. Pair tells us the Rank of the pair. Under tells us the score. This Multi-Case active pattern is working with Single Case Active Patterns, and together they make the following function really easy to write.

let DescribeHand (hand: Card List) = 
    match hand with
    | Bust -> "You're over 21, you're bust"
    | Blackjack -> "BLACKJACK!!! Yeah!!!"
    | TwentyOne -> "TwentyOne, you should probably stick"
    | Pair r -> sprintf "A pair of %As You can split" r
    | Score s -> sprintf "You have %d, want me to hit you?" s

And here’s where it gets really fun, if for any reason someone goes and adds a new value to the Active Pattern, a new type of hand, then our DescribeHand function will fail to compile. We would no longer be covering all of the possibilities.

You don’t get that kind of protection when you use partials and catch-alls.

Caveats
There are one or two things to note about Multi-Case active pattern.

  • They can have a maximum of 7 values. Our example above had only 5, but there are 10 named Poker Hands, so for Poker we’d need take a slightly different approach. Typically if you are looking at a lot of values putting them in separate Single Partial Active Patterns may make more sense, despite the concerns expressed above.
  • They can not be Partial. Multi-Case Patterns exist precisely to give the exhaustive pattern matching. If you are going to require catch all clauses then you might as well use Single Partial Patterns.
  • They can not have additional arguments beyond the one argument that they match on. You can define a multi case active pattern function with additional arguments but you will receive an error if you attempt to use it. That may seem odd, but as we’ll see in the next (and final) post, you can partially apply a Multi-Case pattern to create one that accepts one argument, and that can then be used.

We’ve now covered all of the different types of Active Patterns, we’ve also touched on a number of other areas within FSharp from Option Types to Currying, Tuples to Discriminated unions. If you’ve stayed with me then you should feel like you “get” active patterns, and you may have picked up some extra FSharp along the way.

Active Patterns are incredibly flexible, we haven’t even scratched the surface of all the way’s they can be used. That’s down to you.

There is one more post to go, it will cover some strange and wonderful things you can do with what you’ve learned. We’ll partially apply the Multi-Case patterns, and we’ll nest active patterns to match over complex hierarchical data structures.

Active Patterns : Choices and Nesting

This entry is part 8 of 8 in the series Active Patterns

And so, we arrive at the last post of the series. I’ll show you the F# ‘Choice’ type and show how it relates to active patterns. I’ll explain how to add additional parameters to a multi-case active pattern, and introduce some complex pattern matching using nested active patterns.

Look Ma! No Params
In the previous post I mentioned that Multi-Case active patterns can’t accept additional arguments beyond the one that all active patterns must accept. Here’s what the code might look like if they could.

let (|Smaller|Equal|Bigger|) (compareWith: int) (n: int) =
    if n < compareWith then Smaller
    elif n > compareWith then Bigger
    else Equal

let DescribeNumber (n: int) =
    match n with
    | Smaller 10 -> "Small"
    | Bigger 10 -> "Bigger"
    | Equal 10 -> "Equal"

On the face of it that looks like reasonable code. To see why it’s invalid, let’s change the DescribeNumber function slightly.

let DescribeNumber (n: int) =
    match n with
    | Smaller 5 -> "Small"
    | Bigger 10 -> "Bigger"
    | Equal 10 -> "Equal"

Assuming we could do this, what should happen if we pass the number 7 to DescribeNumber?

The first clause won’t match, because 7 is not smaller than 5. The second and third clauses won’t match either because 7 isn’t bigger than or equal to 10. So, we’ve taken a multi-case pattern, where they whole point is the completeness of the pattern matching, and we’ve broken that completeness by parameterizing each clause separately.

If you try this code out you’ll find that the error isn’t in the Pattern Recognizer, it’s in DescribeNumber. In other words, it’s fine to define a multi-case active pattern, as long as you don’t try to pattern match on it. That offers us a clue as to how to proceed.

let (|SmallerThan10|EqualTo10|BiggerThan10|) = (|Smaller|Equal|Bigger|) 10

If we partially apply the Active Pattern, locking in a value for the additional parameter, we’re back to a multi-case active pattern with one parameter. And our pattern match now looks like this.

let DescribeNumber (n: int) =
    match n with
    | SmallerThan10 -> "Small"
    | BiggerThan10 -> "Bigger"
    | EqualTo10 -> "Equal"

The original function has the values Smaller, Equal and Bigger and the partially applied version has SmallerThan10, EqualTo10 and BiggerThan10. Which begs the question, how does one map to the other? Is it just their positions?

Well, yes, that’s exactly how it works, but for an interesting reason that explains a lot about Multi-Case Active Patterns. Go back and take a look at the signature of the original active pattern.

val (|Smaller|Equal|Bigger|) :
  compareWith:int -> n:int -> Choice<unit,unit,unit>

It returns a Choice

Give me Choice
Just as the Option type allowed us to write functions that can return either ‘Some value’ or ‘None’. The Choice type allows us to return one of up to seven values (remember that seven item limit on multi-case active patterns?).

Forget about Active Patterns for a moment and look at this plain old function.

let Divide (by: int) (this: int) =
    if by = 0 then Choice1Of3 "You can't divide by zero, are you mad?"
    elif this % by = 0 then Choice2Of3 (this/by)
    else Choice3Of3 (decimal this/decimal by)

It’s type is as follows

val Divide : by:int -> this:int -> Choice<string,int,decimal>

Depending on the numbers you try to divide, this function will return one of three choices. A string (an error message for divide by zero), an int (numbers divide evenly), or a decimal (doesn’t divide evenly.)
We can pattern match on this function just like we do with Multi-Choice Active Patterns.

let DescribeDivide (this: int) (by: int) =
    match Divide this by with
    | Choice1Of3 error -> error
    | Choice2Of3 n -> sprintf "%d divides evenly by %d and the result is %d" this by n
    | Choice3Of3 n -> sprintf "%d doesn't divide evenly by %d and the result is %f" this by n

It may be starting to dawn on you now that the Multi-Case Active Pattern is a way of assigning names to those choices. In fact, if you take any function that takes a single argument and returns a Choice you can turn it into a Multi-Case Active Pattern, and call the various possibilities anything you like.

The following example partially applies the Divide function, the result is a Choice which can be turned into a multi-choice active pattern, and used immediately in a pattern match, all within a single function.

let DescribeDivide (by: int) (this: int) =
    let (|ByZero|Evenly|NotEvenly|) = Divide by
    match this with
    | ByZero error -> error
    | Evenly n -> sprintf "%d divides evenly by %d and the result is %d" this by n
    | NotEvenly n -> sprintf "%d doesn't divide evenly by %d and the result is %f" this by n

With all that in mind look again at the partially applied Multi-Case Active Pattern from above.

let (|SmallerThan10|EqualTo10|BiggerThan10|) = (|Smaller|Equal|Bigger|) 10

The signature of the original Active Pattern is

compareWith:int -> n:int -> Choice<unit,unit,unit>

Partially applying it we get a new function with the following signature

int -> Choice<unit,unit,unit>

One input parameter, and the out put is a Choice Of 3, so we can assign this to any Multi-Case Active Pattern name as long as it has 3 cases, in our example (|SmallerThan10|EqualTo10|BiggerThan10|).

Code Quotations
For this final example I need a reasonably elaborate domain model. Instead of creating a phony one, I’m going to use F# itself. Code Quotations provide a model for working with F# code as Data. The point of this example is to convey that even after 8 posts explaining Active Patterns in detail, there is still enormous scope to combine and use Active Patterns in interesting ways.

let model = <@ fun (x: int) -> x * x @>
val model : Expr<(int -> int)> = Lambda (x, Call (None, op_Multiply, [x, x]))

The quoted expression is a lambda that takes an integer x and squares it. The quotation determines that we have an int->int expression. Without getting too bogged down in the syntax, you should be able to see that it’s a Lambda that accepts a variable x and calls a multiply operation, passing two arguments, both of which are x.

OK, now you’re up to speed on Code Quotations, or as up to speed as you’re going to get from this post. It might be worth having a quick read of this page before continuing.

Here are some Namespaces we’ll make use of.

open Microsoft.FSharp.Quotations
open Microsoft.FSharp.Quotations.Patterns
open System.Reflection

That Patterns namespace will come in handy. Code Quotations come with a set of ready made Active Patterns. The following example uses two supplied patterns. ‘Call’ matches method calls, and ‘Value’ matches values. Both are Single Partial Active Patterns.

let rec Describe (expr: Expr) =
    match expr with
    | Call (_,f, left :: right :: []) -> sprintf "%s %s %s" (Describe left) f.Name (Describe right)
    | Value (v, t) when t.Name = "Int32" -> sprintf "%A" v
    | _ -> "?"

This function matches on method calls and values. It will fail to match on any other expression. The Call active pattern returns a three part tuple. We don’t care about the first part, the second part is the function that is called, which we bind to the name f. The third part of the tuple contains the list of arguments. We’ll match on calls that have exactly two arguments, and we bind them to the names left and right.

We’ll also match on values. The Value Active Pattern returns a tuple containing the value and the type. We bind the names v and t to those respectively, and we’ll only match if the type is ‘Int32’.

We add printing of the results and we get the following.

let desc = Describe <@ 2 - 1 * 5 - 3 @>
val desc : string = "2 op_Subtraction 1 op_Multiply 5 op_Subtraction 3"

OK, it ain’t pretty, but hopefully you can see how the Active Patterns are working. If we throw something other than integers at it, we won’t match the values.

let desc = Describe <@ 2.0 - 1.0 * 5.0 - 3.0 @>

val desc : string = "? op_Subtraction ? op_Multiply ? op_Subtraction ?"

Nesting
Now let’s have some fun. We’ll need to create two Active Patterns.

let (|MethodWithName|_|) (s:string) (m: MethodInfo) =
    if s = m.Name then Some() else None

let (|TypeWithName|_|) (s:string) (t: System.Type) =
    if s = t.Name then Some() else None

The first pattern accepts a string and a MethodInfo and matches if the method has the name we provide. The second does the same, but with the name of a Type.

Here’s where things get interesting, the second element of the Tuple returned by the Call Active Pattern is a MethodInfo, which means we can pass it to this new Active Pattern. Like this.

let rec Describe (expr: Expr) =
    match expr with
    | Call (_,MethodWithName "op_Multiply", [left; right]) -> sprintf "%s %s %s" (Describe left) "*" (Describe right)
    | Call (_,MethodWithName "op_Subtraction", [left; right]) -> sprintf "%s %s %s" (Describe left) "-" (Describe right)
    | Value (v, TypeWithName "Int32") -> sprintf "%A" v
    | _ -> "?"

We’ve nested a match on specific method names within matches on method Calls. This will now only match on calls to op_Multiply and op_Subtract. Knowing this we can describe the methods with their operators ‘*’ and ‘-‘ rather than the ugly full method names.

I did the same with the ‘TypeWithName’ active pattern and removed the ‘When’ clause in the process.
Let that sink in. You can use an active pattern to match on values returned from another active pattern. You don’t need a whole separate ‘match .. with’ expression.

I’ve only scratched the surface of nested types, for a much more detailed discussion this talk by Ross McKinlay is heavy going in places but really showcases the power of Active Patterns.

That’s all folks
That’s it for this series. I hope you found it worthwhile. We’ve covered an enormous amount of information. If you’ve managed to work through the entire series of posts you should be fully comfortable with Active Patterns. All that remains is the put them to good use.

Thanks for reading.