Pattern matching

Pattern matching in OCaml can break apart data structures and do pattern matching on the data. Here is the syntax:

match e with
p1 -> e1
| p2 -> e2
| p3 -> e3

pattern matching will detect:

- missed cases
- unused case

wild card for catch all. Be careful when you use it.

Type Checking rules

If e and p1, ..., pn each have type ta and e1, ..., en each have type tb, then entire match expression has type tb

Pattern matching examples:

match 1+2 with
3 -> true
| _ -> false;;

Check if a value is odd or not

let is_odd x =
match x mod 2 with
0 -> false
| 1 -> true
| _ -> raise (Invalid_argument "is_odd");;    (* why do we need this? *)

Negate a value

let neg b =
match b with
| true -> false
| false -> true;;
val neg : bool -> bool = <fun>

neg true;;
- : bool = false
neg (10 >20);;
- : bool = true

Logical implication

let imply v = match v with
(true,true)   -> true
| (true,false)  -> false
| (false,true)  -> true
| (false,false) -> true;;

val imply : bool * bool -> bool = <fun>

let imply v = match v with
(true,x)  -> x
| (false,x) -> true;;

val imply : bool * bool -> bool = <fun>

For characters, OCaml also recognizes the range patterns in the form of 'c1' .. 'cn' as shorthand for any ASCII character in the range.

let is_vowel = function
('a' | 'e' | 'i' | 'o' | 'u') -> true
| _ -> false;;

let is_upper = function
'A' .. 'Z' -> true
| _ -> false;;

Abbreviated pattern matching

let f p = e

is the same as

let f x = match x with p -> e

Examples:

let hd (h::_) = h

let f(x::y::_) = x + y

let g [x; y] = x + y

Pattern matching with lists

let x = [1;2];;
match x with
[]  -> print_string "x is an empty list\n"
| _   -> print_string "x is anything but an empty list\n";;

You probably won't do things quite like the following, but...

let addFirsts ((x::_) :: (y::_) :: _) = x + y;;

addFirsts [ [1;2;3]; [4;5]; [7;8;9] ];;

Will the following work?

addFirsts [ [1;2;3]; [4;5]; [7;8;9]; [10;11;12] ];;

We can read data out of a list using a pttern matching.

let is_empty ls =
match ls with
[] -> true
| (h::t) -> false;;

is_empty [];;
is_empty [1;2];;
is_empty ;;
is_empty [ [] ];;

Get the head of the list

let hd ls = match ls with (h::_) -> h;;
hd [];;

More examples:

let f ls = match ls with (h1::(h2::_)) -> h1 + h2;;

f [2;4;8];;
- : int = 6

let g ls = match ls with [h1; h2] -> h1 + h2;;
g [1;2];;
- : int = 3

g [1;2;3];;
Exception: Match_failure

Lists and Recursive Funcions

let hd l =
match l with
[]->[]
|h::t-> [h]
;;

let rec last l=
match l with
[]->[]
|[x]->[x]
|_::t->last t
;;

Or

let rec last l=
match l with
[]->None
|[x]->Some x
|_::t->last t
;;

calculate the length of a list

let rec length lst =
match lst with
|[]->0
|_::t->1 + length t
;;

calculate the sum of a int list

let rec sum lst=
match lst with
|[]->0
|h::t->h + sum t
;;

check if x is member of a list

let rec member lst x=
match lst with
|[]->false
|h::t->if h = x then true else member t x
;;

append list b to list a

let rec append a b=
match a with
|[]->b
|h::t-> h::append t b
;;

insertion sort

let rec insert x l=
match l with
|[]->[x]
|h::t->if x < h then x::h::t
else h::insert x t
;;

let rec sort l =
match l with
[]->[]
|[x]->[x]
|h::t->insert h (sort t)
;;

QuickSort

let rec qsort = function
| [] -> []
| pivot :: rest ->
let left, right = List.partition (fun x-> x < pivot) rest in
qsort left @ [pivot] @ qsort right
;;

MergeSort

(** split list a into two even parts *)
let split a =
let rec aux lst b c =
match lst with
[] -> (b, c)
| hd :: tail -> aux tail c (hd :: b)
in aux a [] []
;;

(* merge lists xs and ys )

(* two empty lists merge into an empty list *)
(** an empty list merges with a non-empty list yielding the latter, unchanged *)
(** two non-empty lists compare first elements, and prepend the smaller of the two to the result of the recursive merge *)

(** let rec merge (cmp: 'a->'a->bool) (xs:'a list) (ys:'a list) : 'a list = *)

let rec merge cmp xs ys =
match (xs, ys) with
([], []) -> []
| (_, []) -> xs
| ([], _) -> ys
| (xhd :: xtail, yhd :: ytail) ->
if (cmp xhd yhd) then
xhd :: (merge cmp xtail ys)
else
yhd :: (merge cmp xs ytail)
;;

(* Sort original list os using function cmp *)
(* an empty list is already sorted *)
(* a one-element list is already sorted *)
(* a multi-element list should be split
* and recursively sorted, then merged *)

(* let rec mergesort (cmp: 'a->'a->bool) (os:'a list) : 'a list  = *)

let rec mergesort cmp os  =
match os with
[] -> []
| [x] -> [x]
| _ ->
let (ls, rs) = split os in
merge cmp (mergesort cmp ls) (mergesort cmp rs)
;;