Many functional languages have the construct of ‘pattern matching’ baked in to the language.
OCaml, F#, and Haskell all use it as a concise, expressive, and safe (we’ll get to that later) way to handle flow control or even to define entire functions.
In F# it looks like this:
let login user =
match user with
| "hypermush" -> printfn "Hello, Martin"
| "admin" -> printfn "Hello, Sir"
| x -> printfn "Hello, %s" x;;
This may look simple, but there is a lot going on here.
Using the match syntax we take the value (in this case ‘name’) and test if it matches any of the patterns (the expressions on the left hand side of the ‘->’).
The first pattern to match executes the statement on the right hand side of the arrow. We then leave the statement.
The first thing to notice is that the first two patterns match string literals while the last actually binds the value name to x and uses that value in the continuation function.
The second thing to notice is that these continuation functions may have side effects and call other functions (or recurse), which allows us to write nontrivial functions that consist entirely of a pattern match. It’s not hard to see how pattern matching is concise and expressive compared to a bunch of if/else blocks, but how is it ‘safe’?
Well, in a strongly typed language like F# with fancy type-inference the compiler can give you warnings that let you reason about the correctness of a program. When you use pattern matching you are being explicit with your intent to dispatch and this can be powerful.
For example, if your patterns are incomplete (ie. there is a case for which you have not specified a continuation), the F# compiler will warn you:
let who l = match l with
| 'Me' -> 1
| 'You' -> 2;;
FS0025: Incomplete pattern matches on this expression. For example, the value '' '' may indicate a case not covered by the pattern(s).
Let’s say you ignore the warning and continue on. At runtime, failure to match a pattern will cause an exception to be thrown:
Microsoft.FSharp.Core.MatchFailureException: The match cases were incomplete
This stands in stark contrast to a bunch of if..else statements where one can ‘fall out’ and potentially leave the program in an unknown state.
Speaking of state… The match construct also frees us from having to manage our match state manually.
No temporary variables are created by the programmer – we don’t even explicitly store the value we’re matching!
Let’s say we have this C# code:
if(predicate1)
{
if(predicate2)
{
predicate1and2action();
}
else
{
predicate1action();
}
}
else if(predicate2)
{
predicate2action();
}
That is a lot to think about and in complicated cases it can difficult to get this right.
We have multiple exit points far apart in the function and it can be difficult to reason about the program just by looking at it. Compare with pattern matching:
let orFunc x y = match x, y with
| true, true -> true
| true, false -> true
| false, true -> true
| false, false -> false;;
The inline predicates and lack of nesting make clear the purpose and result of the function for all the possible inputs.
Pattern matching is also a nice way to encapsulate behaviour for injection into other parts of a program. The flow control including any side effects is captured and can be passed around as an object into a higher-order dispatcher (perhaps another matcher!). Because the continuations are only executed when the pattern is matched, passing around the matcher is efficient as the evaluation of the continuations is lazy.
F# and Haskell have really nice syntax for pattern matching and when combined with strong type inference, pattern matching becomes a standard way to express behaviours in a functional program.
For those of us using C#, C# 3.0 gives us the nicer ‘lambda’ syntax for anonymous methods and so makes it feasible to implement a simple pattern matching class.
That’s exactly what I have done.
The source is available on GitHub here.
You can match literals:
Matcher<int>
.Match(5)
.With(5,x=>System.Console.WriteLine("5!"))
.Go();
Here, 5 is the pattern being matched and x=>System.Console.WriteLine(“5!”) is the continuation function.
Matcher will throw an Exception if provided a value that matches no pattern.
(The implementation uses .Equals() to determine object equality, so if you want to use literal matching in C#, you should use it only with a proper immutable data type that overrides .Equals())
If you want to create a ‘catch all’ pattern, you can use Else(). This pattern will be checked only after all other defined patterns have been examined.
Matcher<int>
.Match(5)
.With(5,x => System.Console.WriteLine("5!"))
.Else(x => System.Console.WriteLine("Not 5!"))
.Go();
These are all well and good, but the continuation functions all have side effects. What if we want to be purely functional? We would need to return a value from our matcher…
bool result = Matcher<int,bool>
.Match(6)
.With(5,x => true)
.Else(x=>false)
.Go();
Now we can at least use a matcher as the entire body of a method. However, we’re still matching literals, both in how we retrieve the value, and our pattern for matching it.
This isn’t necessary at all – in fact this is all just sugar. Both the value accessor and pattern match predicate are functions themselves, the type signatures tell the story:
public static Matcher<T,TReturn> Match(Func<T> accessor)
public Matcher<T,TReturn> With(Func<T,bool> predicate,Func<T,TReturn> continuation)
At least now we can do this:
public int RecursiveFunction(int y)
{
return Matcher<int,int>
.Match(y)
.With(x=> x > 0, x=> RecursiveFunction(x - 1))
.Else(x=> x)
.Go();
}
Now we’re talking!
Check out the unit test project for some more code samples.
(This blog post was written on the plane from San Francisco to Melbourne but I didn’t get a chance to post it until Christmas Day, so Merry Christmas everyone!).
