Back to Questions
922
views3
comments
pattern matching -- what's the full story?
f#

i always feel with pattern matching that's there's more to it than i know about.

i know it can be used to compare with the structure of a list, and the type of a parameter... but i thought it could also compare with the value of a parameter or two. maybe it can't?

here's a problem i'm trying to re-express using pattern matching. Can you help?

first i have a simple function for adding the sum of all numbers from 0 to n. (this bit works)

1

let sum_to n = n * (n + 1.0 ) / 2.0

now i have a function for adding all numbers between a and b.

1
2
3
4
5
6
7

let sum_from a b = 

    if a = b then 0.0

    elif b > a then sum_to b - sum_to a

    else sum_from b a

(this works too).

But i thought i could re-write it to use pattern matching instead of if's. Am i misguided?

Maybe pattern matching is for looking at the structure and or type of the items, while if is for looking at the values...

Perhaps I need to see the EBNF for pattern matching. Unless that would make my head explode.

Also: why doesn't the sum_from function above require a 'rec' indicator?

cheers

lb (secretGeek.net)

.

For the most part, you have pattern matching down.

First, here is the grammar for pattern matching: [link:research.microsoft.com]. It's not that hard to understand, although you will have a better chance if you first write the pattern and see if it can be accepted by the grammar instead of the other way around.

To answer your question about rec, you do need it there. If you are not getting an error, it means that you have another function called sum_from already defined in the file/environment. So, the new sum_from is referencing the old one for its calculation (probably not what you want).

Basically, pattern-matching is more for decomposition than exact value comparison (although it can do that as well). As you mentioned, it is great for decomposing lists, arrays, records, etc. and working on the inner elements.

Here is your function written using pattern matching. Notice the use of guards to do value comparisons:

1
2
3
4
5

let rec sum_from2 a b =
  match a with // doesn't matter what you put here in this case, just put something
  | _ when a = b -> 0.0
  | _ when b > a -> sum_to b - sum_to a
  | _ -> sum_from2 b a

As you can see, it is very similar to the if-then-else version. Now, here is a version that doesn't use guards:

1
2
3
4
5
6

let rec sum_from2 a b =
  // this depends a lot on return values of compare, which are [-1;0;1] for int.
  match compare a b with
  | 0 -> 0.0
  | -1 -> sum_to b - sum_to a
  | 1 -> sum_from2 b a

As you saw, pattern matching can do some basic comparison with constants. Here's another example (classic fibonacci):

1
2
3
4

let rec fib n =
  match n with
  | 0 | 1 -> 1 // return 1 for fib 0 or fib 1
  | _ -> fib (n - 1) + fib (n - 2)

Overall, pattern matching work much better if you are working with a data structure recursively, if you are doing type comparisons, etc. If you are only doing value comparisons like in sum_from, if-then-else will look cleaner.

Regards,

z.

By on 1/27/2008 4:12 AM ()

thank you very much zakaluka. very much appreciated.

brilliant answer. Very well described. All bases covered.

By on 1/27/2008 5:09 AM ()

One thing I did forget to mention is that active patterns can be used to make pattern matching easier to digest for a variety of problems. Unfortunately, the amount of setup required for active patterns means that it is only worth it if you are going to be using those patterns in other places or it improves the readability of a convoluted piece of code.

Generally, I've used active patterns for easier decomposition of objects that are not intrinsically conducive to decomposition by F# (eg, classes). However, they have many other uses as well. This example is really ridiculous for active patterns, but it'll give you some small idea of what they can do.

For example:

1
2
3
4
5
6
7
8
9

//NOTE: I wouldn't use full active patterns in this case, but would go with partial patterns, as we don't want the 'false' variant to represent a matchable type (in this situation).
let sum_to n = n * (n + 1.0 ) / 2.0
let (|Eq|) (a: float, b: float) = if a = b then Eq(true) else Eq(false)
let (|LT|) (a: float, b: float) = if a < b then LT(true) else LT(false)
let rec sum_from a b =
  match (a,b) with
  | Eq(true) -> 0.0
  | LT(true) -> sum_to b - sum_to a
  | _ -> sum_from b a

And, with partial active patterns:

1
2
3
4
5
6
7
8

let sum_to n = n * (n + 1.0 ) / 2.0
let (|Eq|_|) (a: float, b: float) = if a = b then Some(a - b) else None // Notice how, instead of true like the above active pattern, I am returning the difference.  I can return anything in the option type, making life easier further in case I end up needing the difference.
let (|LT|_|) (a: float, b: float) = if a < b then Some(a - b) else None
let rec sum_from a b =
  match (a,b) with
  | Eq(diff) -> 0.0
  | LT(_) -> sum_to b - sum_to a // Since I don't use 'diff', I just use '_' to discard the value.
  | _ -> sum_from b a

If you do want to use Active patterns, I recommend starting with:

[link:blogs.msdn.com]
[link:tomasp.net]
[link:www.infoq.com]
[link:langexplr.blogspot.com]
[link:blogs.msdn.com] <-- actual paper on active patterns from Don Syme et al.

Regards,

z.

By on 1/28/2008 3:06 AM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper