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 [1];;
	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

get a head of a list

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

get the last element of a list

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)
	;;