While I was building the position heuristic function for Connect Four I ran into an interesting gotcha with F# pattern matching. Lets see if you see it before I tell you what it is:
let rec heuristic (positions: (int * int) list) (pos: int*int) =
match positions with
| [] -> 0
| position::_ -> 1 + (heuristic (List.tl positions) pos)
| _ -> heuristic (List.tl positions) pos
Looking at it, it seems the code should tell me how often value is in position, right? Well it doesn’t! And there is a good reason for it. When pattern matching you are capturing a new value instead of testing for one. So in line 4 this code defines pos to be the head of position, now matter what is in there. That’s the reason the compiler warns us that last rule will never match.
What we should have done is this:
let rec heuristic (positions: (int * int) list) (pos: int*int) =
match positions with
| [] -> 0
| position::_ when pos = position -> 1 + (heuristic (List.tl positions) pos)
| _ -> heuristic (List.tl positions) pos
But I have to say, this looks a little ugly compared to the first version. There is a blog post by Chris Smith about this, where he tells us to use the Literal attribute if we want it match against a value. Well this does not work for anything other then primitive types…
So how do we get our pattern matching code to look nice again? Active Patterns to the rescue! Active Patterns are a little hard to grasp at first, but they can save you a lot of code and make your designs much nicer, if used right. I always think of an Active Pattern as pattern matching against a function application.
Lets see what happens when we use them in our example:
let rec heuristic (positions: (int * int) list) (pos: int*int) =
let (|Same|Different|) position = if pos = position then Same else Different
match positions with
| [] -> 0
| Same ::_ -> 1 + (heuristic (List.tl positions) pos)
| Different ::_ -> (heuristic (List.tl positions) pos)
I think this code is a lot clearer then what the second version and works with any type you throw at it.
Active Patterns are good for a lot more then this but I’ll get into other applications of it some other time. Just remember this pattern matching gotcha so you don’t waste any time pulling out your hair;)
Update:
Just to complete this, here is the version that you should be using, if you want to copy paste this code. It uses tail recursion with an accumulator argument so that the stack doesn’t grow.
let rec heuristic (positions: (int * int) list) (pos: int*int) =
let (|Same|Different|) position = if pos = position then Same else Different
let rec loop positions acc =
match positions with
| [] -> acc
| Same :: _ -> (loop (List.tl positions) (acc + 1))
| Different :: _ -> (loop (List.tl positions) acc)
loop positions 0