Tuesday, April 22, 2008

F# Pattern Matching

After my last post on the sample F# test runner, I realized I missed a post on one of the critical constructs F# has to offer; pattern matching. Pattern matching does exactly what it sounds like, matches patterns.
let action x = 
     match x with
     | "Red" -> "Stop"
     | "Green" -> "Go"
     | _ -> "I don't know"
In this example, when I pass the colors Red or Green to the action function, it returns the matching value. If I were to pass blue to the function, I would get back "I don't know".
> action "Red";; val it : string = "Stop" > action "Blue";; val it : string = "I don't know"
Notice the "_" at the end, it is a wildcard and it makes this pattern match exhaustive. If I didn't include the _, F# would complain I had an incomplete match. You do have to be careful of where you put your wildcard character. The following function would create a scenario where the "Green" match statement would not be evaluated:
let action x = 
     match x with
     | "Red" -> "Stop"
     | _ -> "I don't know"
     | "Green"  -> "Go"
This control structure should seem very familiar to anyone coming from the C language family. Indeed, the action function could be written as an if..else statement or a switch statement in C#:
   public static string Action(string color)
        {
            if (color == "Red")
            {
                return "Stop";
            }
            else if( color == "Green")
            {
                return "Go";
            }
            else
            {
                return "I don't know";
            }
        }
You can include conditions within your matches, take the following function:
let isEven x =
     match x with
     | _ when x % 2 = 0 -> true
     | _ -> false
With conditions however, you need to have a catch all. If I were to change the above function to read like this:
let isEven x =
     match x with
     | _ when x % 2 = 0 -> true
     | _ when x % 3 = 0 -> false
the complier would complain of an incomplete pattern match. With pattern matching you can decompose structured values. This example breaks down the tuples for the match.
let isCubeEven x =
     match x with
     | _ when snd x % 2 = 0 -> (fst x,true)
     | _ -> (fst x,false)
This function returns the following in fsi:
> isCubeEven (3,9);; val it : int * bool = (3, false)
The example "isCubeEven" highlights two features of what makes F# exciting. First, notice that I didn't need to explicitly annotate any of my variables with types? The F# complier inferrs that x is a tuple because of the way I use it within my function. And second, the fst and snd functions that let me easily work with tuples to get the first and second values. Pattern matching becomes really powerful when you combine it with rec, the keyword for recursive functions. Take this function for adding up the numbers in a number:
let rec sumDigits x y =
    match x with
          | x when x = 0 ->  y
          | x -> sumDigits (x / 10) (x % 10) + y
This particular function I wrote to solve some of the Project Euler problems. With this function y accumulates the running summed value and x gets chopped up from right to left.
> sumDigits 123456789 0 val it : int = 45
When you combine the rec keyword and pattern matching, the possibilities are infinite. Take the fold_left function from the F# list namespace:
let rec fold_left f s l = 
     match l with 
     | [] -> s 
     | (h::t) -> fold_left f (f s h) t
The fold_left function takes a function f, a seed value s, and a list l. The match uses the list processing keys to get the first element h and remainder of the list t. Then calls itself with the same function, the result of the function applied to the seed value and the first element and the rest of the list. Pattern matching also works great on records, here's a great post on that by Mike Gold. Question and comments are welcome!

1 comment:

Anonymous said...

I just tried to write the sumDigits with no rec keyword and it work the same way, so I don't understand well the meaning of it, thanks. ik