Geeks With Blogs

News I have joined Anti-IF Campaign
Subscribe in a reader
Lukas Domagala

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

 

Posted on Thursday, June 25, 2009 10:18 PM .Net , F# | Back to top


Comments on this post: FSharp Pattern Matching gotcha and Active Patterns

# re: FSharp Pattern Matching gotcha and Active Patterns
Requesting Gravatar...
I guess you wanted to write
| pos::_ - 1 + (heuristic (List.tl positions) pos)
right? (The way you put it makes no sense)
I guess it's even petter to write
| phd::ptl when phd = position -> 1 + (heuristic ptl pos)
or take the rec to a inner function (then you can strip the pos argument for a closure and make the inner function tail recursive with a accumulator argument) but I see your point.
I don't think this is a major problem though - the only thing that freaks me with pattern matching from time to time is, that you can't do good matching over lists with a fixed item count)
Left by Carsten on Jun 26, 2009 6:18 AM

# re: FSharp Pattern Matching gotcha and Active Patterns
Requesting Gravatar...
hey carsten,
you are right, i could have used the matched value, but since the position = pos in that case it doesn't matter.
and yes this can be made tail recursive easily, but I think its easier to read this way so I kept it for the post. I guess I should post a tail recursive version at the end just so no one copy pasts this code
btw what do you mean by "pattern matching over lists with fixed item count"?
Left by Lukas Domagala on Jun 26, 2009 8:19 AM

# re: FSharp Pattern Matching gotcha and Active Patterns
Requesting Gravatar...
One thing to keep in mind as I mentioned on hubfs, is that although it doesn't need to, (|Same|Different|) will be called twice with the same argument in the case that |Same didn't match. (Hmm -- I know that it will get called up to N-1 time, but in your case N-1 is 1, so you may be ok, as it may be smart enought to realize that the last case is true if none of the others were.)
Left by thelazydogsback on Jun 26, 2009 7:11 PM

# re: FSharp Pattern Matching gotcha and Active Patterns
Requesting Gravatar...
thanks for the warning lazydog, but in this case its actually smart enough to only call it only once. if it wasnt smart enough you could just replace the last match with a catch all.
But I totally agree, its important to look out for that "feature":)
Left by Lukas Domagala on Jun 26, 2009 7:24 PM

# re: FSharp Pattern Matching gotcha and Active Patterns
Requesting Gravatar...
It looks like your problem is more that you are trying to do to much with the pattern matching. I think the following is a bit clearer. This way you are just trying to capture the variables and then make the descision in the body of the match.

let heuristic (positions: (int * int) list) (pos: int*int) =
let rec loop positions acc =
match positions with
| [] -> acc
| x::xs -> (loop xs (if pos = x then acc + 1 else acc))
loop positions 0

tbh in a simple example such as this you are probably better of just using the buildin list processing functions like

let heuristic (positions: (int * int) list) (pos: int*int) =
positions |> List.fold (fun acc item -> if pos = item then acc + 1 else acc) 0
Left by Lionel on Jun 30, 2009 6:47 PM

# re: FSharp Pattern Matching gotcha and Active Patterns
Requesting Gravatar...
thanks for the alternatives lionel.
actually my code is just a simple example, for the more general case of trying to match against a value. i kind of dislike using the when clause, so active patterns are a possible solution that is very clear about the intent of my code
Left by Lukas Domagala on Jun 30, 2009 9:05 PM

Your comment:
 (will show your gravatar)


Copyright © Domagala | Powered by: GeeksWithBlogs.net