Matching

[mkorman]

I have been learning OCaml lately, and I have come across this pattern matching that everyone always seems to be raving about. Isn't this essentially the same thing as a switch statement in C, or is there something I'm missing?

[GnuVince]

It's more powerful. For example, here's how you could write a factorial function using pattern matching:


let rec fact n =
match n with
0 -> 1
| m -> m * fact (m - 1);;


What does this do? If n is equal to 0, return 1. In all other cases (called default case), the value of n will be put in m And we will multiply m with the factorial of m-1. Pattern matching is also quite useful with lists.


let rec map f l =
match l with
[] -> []
| h::t -> f h::map f t;;


This is a map function. Lists in O'Caml look like this: 1::2::3::[]. The function stops when it reaches the end of the list ([]). h::t is used to match any other list. h is for head and t is for tail (we could've used anything, these are just variables). What's head and tail? Look at this:


# List.hd mylist;;
- : int = 1
# List.tl mylist;;
- : int list = [2; 3]


The head of the list is the first element of the list. The tail is the list with the head removed.

Pattern matching is also used a lot with types, but I haven't worked with those yet. Maybe Jeremy or PrBacterio can you help there.

And there's one cool thing about pattern matching: it will warn you if all cases can not be matched. Consider this:


let to_letters n =
match n with
0 -> "Zero"
| 1 -> "One"
| 2 -> "Two";;



This works only when n is either 0, 1 or 2. What if it was 3? O'Caml warns us about that possibility:

Warning: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
3


It tells us that not all case can be matched, and gives us an example. So you must add a default case to match all other possibilities:


let to_letters n =
match n with
0 -> "Zero"
| 1 -> "One"
| 2 -> "Two"
| _ -> string_of_int n;;


Now, when n is not 0, 1 or 2, it will just convert the integer to a string and return it.

[jemfinch]

Switch statements in C can use only chars, ints, or enumerated constants. ML match/case statements can use any type (well, in SML you can only use equality types, but either way... :))

ML match/case statements can decompose algebraic datatypes into their constituent parts and match on that, giving you far more power than a simple C switch statement.

Jeremy

[PrBacterio]

I think the following simple symbolic derivation example should nicely demonstrate the advantages of functional style pattern-matching. Consider, in particular, the simplify function defined here; one could add as many additional rules of this form as one likes to that function to make it more powerful:
type expr =
| E_add of (expr * expr)
| E_sub of (expr * expr)
| E_mul of (expr * expr)
| E_div of (expr * expr)
| E_fapply of (string * expr)
| E_const of (float)
| E_var

let rec derivative = function
| E_add (u,v) -> E_add (derivative u, derivative v)
| E_sub (u,v) -> E_sub (derivative u, derivative v)
| E_mul (u,v) ->
E_add (E_mul (derivative u, v),
E_mul (u, derivative v))
| E_div (u,v) ->
E_div (E_sub (E_mul (u, derivative v),
E_mul (derivative u, v)),
E_mul (v, v))
| E_fapply (f, x) ->
E_mul (derivative x,
E_fapply (f ^ "'", x))
| E_const _ -> E_const (0.0)
| E_var -> E_const (1.0)

let rec simplify = function
| E_add (E_var, E_var) -> E_mul (E_const 2.0, E_var)
| E_mul (E_const k, x) when k = 0.0 -> E_const 0.0
| E_mul (x, E_const k) when k = 0.0 -> E_const 0.0
| E_mul (E_const k, x) when k = 1.0 -> simplify x
| E_mul (x, E_const k) when k = 1.0 -> simplify x
| E_add (E_const u, E_const v) -> E_const (u +. v)
| E_mul (E_const u, E_const v) -> E_const (u *. v)
| E_div (E_const u, E_const v) -> E_const (u /. v)
| E_sub (E_const u, E_const v) -> E_const (u -. v)
| E_add (E_const u, E_add (E_const v, x)) -> simplify (E_add (E_const (u +. v), x))
| E_add (E_mul (x, u), E_mul (y, v)) when x = y -> simplify (E_mul (x, E_add (u,v)))
| E_add (x, y) ->
let x' = simplify x and y' = simplify y in
if x' <> x || y' <> y then simplify (E_add (x', y'))
else E_add (x,y)
| E_mul (x, y) ->
let x' = simplify x and y' = simplify y in
if x' <> x || y' <> y then simplify (E_mul (x', y'))
else E_mul (x,y)
| E_div (x, y) ->
let x' = simplify x and y' = simplify y in
if x' <> x || y' <> y then simplify (E_div (x', y'))
else E_div (x,y)
| E_sub (x, y) ->
let x' = simplify x and y' = simplify y in
if x' <> x || y' <> y then simplify (E_sub (x', y'))
else E_sub (x,y)
| E_const k -> E_const k
| E_var -> E_var
| E_fapply (f, x) -> E_fapply (f, simplify x)

let ( +++ ) f g x = f (g x)

let sderivative = simplify +++ derivative

Example run:
# sderivative (E_add (E_mul (E_var, E_var), E_mul (E_const 2.0, E_var)));;
- : expr = E_add (E_mul (E_const 2, E_var), E_const 2)

Pattern matching is a concept way beyond C's simple switch statement. You can match data against complex (constructor) expressions, even containing variables which will then be filled in with the corresponding values when a match is found. Actually OCaml's pattern matching is still lacking in that it does not support several occurences of the same variable inside a pattern.

[mkorman]

Ah, that does seem more powerful. Thanks for your replies.