Functional C# - Pattern Matching
In the past, I've covered quite a bit of functional programming in C# 3.0 and how you can implement some of the basic constructs using the language. In preparation for the Richmond Code Camp coming up on October 4th, for which I'm planning to present "Functional C# -or- How I lost the foreach and learned to love LINQ", I'm revisiting some of the topics I've talked about in the past. One of those topics is pattern matching.
Pattern Matching
Earlier in my introduction to F# series, I covered pattern matching and how clear and concise it can make your programs. You can more program to your intent instead of needing to switch between if statements, case statements and so on. Basically, pattern matching is the way of checking for conditions on a given parameter with rigid specifications. Pattern matching is a strongly functional programming concept and is present in F#, OCaml, Haskell, Erlang, etc. Erlang is an interesting one here as you can define the patterns, which in turn will define the type. As Erlang is a dynamic language, you do not need to specify the type beforehand, so implementing patterns then define that type.
Pattern matching in F# is pretty flexible as it allows to match against explicit values, structures, lists, guarded ranges, .NET types, active patterns and so on. The basic syntax is match ... with ... expressions such as this.
| pattern_1 -> expression_1
| pattern_2 -> expression_2
| pattern_n -> expression_n
Similarly, I could use the function keyword should I create a function with the parameter to pattern match against instead of the above syntax, such as this.
| None -> 0
| Some n -> n
let value = get_value (Some 25)
As you may notice, F# has very flexible syntax for describing these, so let's look at a few more ideas before we move on.
Data Structure Matching
We can pattern match against data structures, such as lists quite easily. Lists are a special case as it allows you to match against the head and the tail of the given list. By using the head::tail notation allows us to specify that we will receive the head and tail values should they be present. Such an example might be to get the evens from a given list.
let rec even_list = function
| [] -> []
| h::t when h % 2 = 0 -> h::even_list t
| h::t -> even_list t
let evens = [1..20] |> even_list
Active Patterns
Pattern matching in F# is extremely flexible, as you can extend what you can pattern match. Through a mechanism called "Active Patterns", you can extend the syntax quite easily. Let's say for instance that we want to create a pattern to determine whether a given number is either a composite number, prime number or neither. We can define a pattern over that such as the following code:
let is_prime x =
let lim = int(sqrt(float(x)))
let rec check y =
y > lim or (x % y <> 0 && check(y + 1))
check 2
let (|Prime|Composite|Neither|) x =
if x < 2 then Neither
elif is_prime x then Prime
else Composite
let prime_or_composite x =
match x with
| Prime -> "prime"
| Composite -> "composite"
| Neither -> "neither composite nor prime"
printfn "%s" (prime_or_composite 3)
As you can see from above, we can define the pattern using the (|pattern name|) syntax and then define the behavior from this. Then I can use them in the pattern matching exercise below to print out whether my given number fit any of the patterns. That's how powerful pattern matching can be. But, can we have some of these features in C#?
Implementing in C# 3.0
I've had the idea to express some basic pattern matching in C# instead of having to decide whether things are a switch statement, if, else, etc. Instead, I'd rather have the ability to specify these matches through the use of predicates for determining success and then a given action should that one be selected. Unfortunately, that's a very limited subset of what pattern matching can achieve, but it's actually quite simple to implement in C# 3.0 through the use of extension methods and fluent interfaces.
Let's set up a simple scenario which takes in a nullable number and matches against whether it is even, odd or null. Below is a simple example of how that might look through the use of our extension methods and fluent interface.
{
return n != null ? n % 2 == 0 : false;
}
public static bool IsOdd(int? n)
{
return n != null ? !IsEven(n) : true;
}
int? n = 3;
var evenOdd = n.Match()
.With(IsEven, x => "Even number")
.With(IsOdd, x => "Odd number")
.Else(x => "Null")
.Do();
Console.WriteLine(evenOdd);
What this gives me is the ability to match against my current piece of data and determine the actions through my With methods and my default case with the Else method. Each takes a lambda function which passes in the value we're matching against, and then returns a string. The problem arises with C# though if we want our lambda to do nothing (aka void), as C# doesn't treat this as a proper return type, so you would have to switch between Func<T, TResult> and Func<T> which isn't really realistic. So, already our design is hobbled.
But, let's move on to what the implementation might look like. We need a way to capture all the cases and execute them in order to find the match, else throw a MatchNotFoundException should there be no match. Let's define that class below.
{
public MatchNotFoundException(string message) : base(message) { }
}
public class PatternMatch<T, TResult>
{
private readonly T value;
private readonly List<Tuple<Predicate<T>, Func<T, TResult>>> cases
= new List<Tuple<Predicate<T>, Func<T, TResult>>>();
private Func<T, TResult> elseFunc;
internal PatternMatch(T value)
{
this.value = value;
}
public PatternMatch<T, TResult> With(Predicate<T> condition, Func<T, TResult> result)
{
cases.Add(Tuple.New(condition, result));
return this;
}
public PatternMatch<T, TResult> Else(Func<T, TResult> result)
{
if (elseFunc != null)
throw new InvalidOperationException("Cannot have multiple else cases");
elseFunc = result;
return this;
}
public TResult Do()
{
if (elseFunc != null)
cases.Add(
Tuple.New<Predicate<T>, Func<T, TResult>>(x => true, elseFunc));
foreach (var item in cases)
if (item.Item1(value))
return item.Item2(value);
throw new MatchNotFoundException("Incomplete pattern match");
}
}
What we have defined is a holder for our cases. I'm using a Tuple<TArg1, TArg2> to hold my pairs of predicates and expressions to execute. I've defined that as part of my Functional C# library available on CodeGallery, which should be up to date with example of functional programming using C# 3.0. When you define an else function (or default function), we want to be able to add that to our collection as the last one to be fired, if ever, so we will define that in the Do method.
In order to stay away from the angle bracket tax, I've created a context class which will allow me to set up my first With statement and then include the PatternMatch<T, TResult>. This code takes in the value and then will have a With method which will return us a new instance of the PatternMatch<T, TResult>.
{
private readonly T value;
internal PatternMatchContext(T value)
{
this.value = value;
}
public PatternMatch<T, TResult> With<TResult>(
Predicate<T> condition,
Func<T, TResult> result)
{
var match = new PatternMatch<T, TResult>(value);
return match.With(condition, result);
}
}
Lastly, I'll define a simple extension method which will allow me to pattern match against any given data type. This will simply create a new instance of the PatternMatchContext<T> class and return it.
{
public static PatternMatchContext<T> Match<T>(this T value)
{
return new PatternMatchContext<T>(value);
}
}
Wrapping it Up
As you can see, it's clumsy and not the most ideal as it would be in an F# solution or any other more functional programming language. We quickly run into the limitations with the language such as dealing with Func<T, TResult> and Action<T> because C# does not treat System.Void as a type. Wes Dyer and the Microsoft Volta team have been working on some of those issues with library approaches as well. But, it's still interesting to try to extend C# into brave new territory.
I would like to see C# 4.0 and beyond continue to make inroads towards a more functional style, although I will caution that C# should stay with the object and class first approach with functional aspects, whereas leaving F# to be the functional programming first mentality. In order to do that, there are a few big hurdles to overcome...
As always, the sample code is available on CodeGallery at the Functional C# project.
