How does pattern matching work behind the scenes in F#?

Question

Hello Everyone,

I am completely new to F# (and functional programming in general) but I see pattern matching used everywhere in sample code. I am wondering for example how pattern matching actually works? For example, I imagine it working the same as a for loop in other languages and checking for matches on each item in a collection. This is probably far from correct, how does it actually work behind the scenes?

Answer 1

No, it doesn't loop. If you have a pattern match like this

match x with
| Foo a b -> a + b
| Bar c -> c

this compiles down to something like this pseudo code:

if (x is a Foo)
  let a = (first element of x) in
  let b = (second element of x) in
  a+b
else if (x is a Bar)
  let c = (first element of x) in
  c

If Foo and Bar are constructors from an algebraic data type (i.e. a type defined like type FooBar = Foo int int | Bar int) the operations x is a Foo and x is a Bar are simple comparisons. If they are defined by an active pattern, the operations are defined by that pattern.

Answer 2

It depends on what kind of pattern matching do you mean - it is quite powerful construct and can be used in all sorts of ways. However, I'll try to explain how pattern matching works on lists. You can write for example these patterns:

match l with
| [1; 2; 3] ->  // specific list of 3 elements
| 1::rest ->    // list starting with 1 followed by more elements
| x::xs ->      // non-empty list with element 'x' followed by a list
| [] ->         // empty list (no elements)

The F# list is actually a discriminated union containing two cases - [] representing an empty list or x::xs representing a list with first element x followed by some other elements. In C#, this might be represented like this:

// Represents any list
abstract class List<T> { }
// Case '[]' representing an empty list
class EmptyList<T> : List<T> { }
// Case 'x::xs' representing list with element followed by other list
class ConsList<T> : List<T> {
  public T Value { get; set; } 
  public List<T> Rest { get; set; }
}

The patterns above would be compiled to the following (I'm using pseudo-code to make this simpler):

if (l is ConsList) && (l.Value == 1) &&
   (l.Rest is ConsList) && (l.Rest.Value == 2) &&
   (l.Rest.Rest is ConsList) && (l.Rest.Rest.Value == 3) &&
   (l.Rest.Rest.Rest is EmptyList) then
   // specific list of 3 elements
else if (l is ConsList) && (l.Value == 1) then
   var rest = l.Rest;
   // list starting with 1 followed by more elements
else if (l is ConsList) then
   var x = l.Value, xs = l.Rest;
   // non-empty list with element 'x' followed by a list
else if (l is EmptyList) then 
   // empty list (no elements)

As you can see, there is no looping involved. When processing lists in F#, you would use recursion to implement looping, but pattern matching is used on individual elements (ConsList) that together compose the entire list.

Pattern matching on lists is a specific case of discriminated union which is discussed by sepp2k. There are other constructs that may appear in pattern matching, but essentially all of them are compiled using some (complicated) if statement.

Answer 3

How does pattern matching actually work? The same as a for loop?

It is about as far from a for loop as you could imagine: instead of looping, a pattern match is compiled to an efficient automaton. There are two styles of automaton, which I call the "decision tree" and the "French style." Each style offers different advantages: the decision tree inspects the minimum number of values needed to make a decision, but a naive implementation may require exponential code space in the worst case. The French style offers a different time-space tradeoff, with good but not optimal guarantees for both.

But the absolutely definitive work on this problem is Luc Maranget's excellent paper "Compiling Pattern Matching to Good Decisions Trees from the 2008 ML Workshop. Luc's paper basically shows how to get the best of both worlds. If you want a treatment that may be slightly more accessible to the amateur, I humbly recommend my own offering When Do Match-Compilation Heuristics Matter?

Writing a pattern-match compiler is easy and fun!

Answer 4

If you compile your F# code to an .exe then take a look with Reflector you can see what the C# "equivalent" of the F# code.

I've used this method to look at F# examples quite a bit.