### Pattern matching review implement xor let xorb a b = match a with |true -> not b |_ -> b;; Pattern matching detects missed cases. let f l = match l with x::(y::_) -> x + y ;; Warning 8: this pattern-matching is not exhaustive. Here is an example of a case that is not matched: (_::[]|[]) val f : int list -> int = <fun> f [1;2;3;4];; - : int = 3 f [];; Exception: Match_failure Pattern matching also detecs unused cases. Following example adds two integer list into one list. let rec add_list a b = match (a,b) with ((h1::t1),(h2::t2))->h1+h2 :: (add_list t1 t2) |[],x ->x |x,[] -> x |_->[] ;; Warning 11: this match case is unused. val add_list : int list -> int list -> int list = <fun> Because it never reaches the catch all case, pattern matching gives warnings. Removing the last catch all case will fix it. let rec add_list a b = match (a,b) with ((h1::t1),(h2::t2))->h1+h2 :: (add_list t1 t2) |[],x ->x |x,[] -> x ;; val add_list : int list -> int list -> int list = <fun> add_list [1;2;3] [4;5;6;7;8];; - : int list = [5; 7; 9; 7; 8] ### Mutual recursion There are no "forward prototypes" in OCaml. But there is a special syntax for defining a set of two or more mutually recursive functions. We can write mutually recursive functions by putting them togeterh with a "and" keyword. You can also use similar syntax for writing mutually recursive class definitions and modules. Here is an example: let rec even n = match n with | 0 -> true | x -> odd (x-1) and odd n = match n with | 0 -> false | x -> even (x-1) ;; val even : int -> bool = <fun> val odd : int -> bool = <fun> Here is the another version that handles negative numers: let rec even n = if n < 0 then failwith "Argument Error" else match n with | 0 -> true | x -> odd (x-1) and odd n = if n < 0 then failwith "Argument Error" else match n with | 0 -> false | x -> even (x-1) ;; val even : int -> bool = <fun> val odd : int -> bool = <fun> ### Tuples OCaml tuple is like a fixed lengthlist. But elements of a tuple can have different types. The type of an n-tuple is written as an ordered sequence of n types, separated by *. We construct a tuple by listing the elements in (e1,.....en) format and deconstruct using pattern matching. (1,2,3);; - : int * int * int = (1, 2, 3) Tuples can be heterogeneous (1,3.5,"hello");; - : int * float * string = (1, 3.5, "hello") Functions can take tuples as arguments let plusthree (x,y,z) = x + y + z let sum (a,b) = a + b let addone (x,y,z) = (x+1,y+1,z+1) Tuple List [(1,1);(2,3);(1,5)] [(1,"alice");(2,"bob")] ### Polymorphic types Some functions work for any data type. Examples of polymorphic functions: let tl (_::t) = t let swap (x,y) = (y,x) let tls(_::xs, _::ys) = (xs, ys) let eq(x,y) = x = y (* how do you parse this? *) ### Anonymous functions An anonymous function is a function that is declared without being named. The fun expression creates an anonymous function. (fun x->x*2) 10 returns 20 bind anonymous functions to a variable let add = (fun x->x+1) More examples let plus3 x = x+3;; let twice f x = f (f x);; let t f x = f (f (f x));; add x y = x + y ((add x) y ) let add x y = x+y let add = (fun x->(fun y->x+y)) ### Higher order functions What do these functions have in common? let rec neg x = match x with [] -> [] | h::t -> (-h)::(neg t) ;; let rec add1 x = match x with [] -> [] | h::t -> (h+1)::(add1 t) ;; They both create a new list whose elements are a function of the corresponding elements in the old list. We can write this pattern as its own function, map. map f [a;b;c;d] will generate a list [f a; f b; f c; f d] map takes a function and a list as arguments, and generate a new list by applying the function to each memeber of the list. (* equivalent to List.map *) let rec map f x = match x with [] -> [] | h::t -> (f h)::(map f t) ;; map (fun x->x*2) [10;20;30;40];; - : int list = [20; 40; 60; 80] let halve x = x / 2;; map halve [10;20;30;40];; - : int list = [5; 10; 15; 20] More Examples let neg' x = (* the same as neg *) let negate y = -y in map negate x ;; let add1' x = (* the same as add1 *) let addone y = y + 1 in map addone x;; neg [1;2;3] = neg' [1;2;3];; add1 [1;2;3] = add1' [1;2;3];;