(* Goal for today: more practice with OCaml. In particular, we'll be starting to see the power of higher order functions. Agenda: * Map and reduce * fold_left, fold_right *) (* Exercise 0 : Some auxiliary functions we may use later from precept 2 * If you did them last week, then you can just copy them over. Otherwise, * it'll be good review practice. *) (* 0a. Write a higher-order function for binary operations on options. * If both arguments are None, return None. If one argument is (Some x) * and the other argument is None, function should return (Some x) *) (* What is calc_option's function signature? *) let co_sig:string = "('a -> 'a -> 'a) -> 'a option -> 'a option -> 'a option" let calc_option (f: 'a->'a->'a) (x: 'a option) (y: 'a option) : 'a option = match x,y with | None, None -> None | _, None -> x | None, _ -> y | Some a, Some b -> Some (f a b) (* 0b. Now rewrite the following functions using the above * higher-order function. Write a function to return the smaller of * two int options, or None if both are None. If exactly one argument * is None, return the other. *) let min_option (x: int option) (y: int option) : int option = let min a b = if a < b then a else b in calc_option min x y let max_option (x: int option) (y: int option) : int option = let max a b = if a > b then a else b in calc_option max x y (* 0c. Write a function to return the boolean AND/OR of two bool options, * or None if both are None. If exactly one is None, return the other. *) let and_option (x:bool option) (y: bool option) : bool option = calc_option (&&) x y let or_option (x:bool option) (y: bool option) : bool option = calc_option (||) x y (* Exercise 1 *) (* Map and reduce are the functions we've seen before, with * arguments in a sane order to be partially defined *) let rec reduce (f:'a -> 'b -> 'b) (u:'b) (xs:'a list) : 'b = match xs with | [] -> u | hd::tl -> f hd (reduce f u tl) let rec map (f:'a -> 'b) (xs: 'a list) : 'b list = match xs with | [] -> [] | hd::tl -> (f hd) :: (map f tl) (* 1a. Implement length in terms of reduce. * length lst returns the length of lst. length [] = 0. *) let length (lst: int list) : int = reduce (fun _ len -> len + 1) 0 lst (* 1b. Write a function that takes an int list and multiplies every int by 3. * Use map. *) let times_3 (lst: int list): int list = map (fun x -> x*3) lst (* 1c. Write a function that takes an int list and an int and multiplies every * entry in the list by the int. Use map. *) let times_x (x: int) (lst: int list) : int list = map (fun y -> y*x) lst (* 1d. Rewrite times_3 in terms of times_x. * This should take very little code. *) let times_3_shorter = times_x 3 (* 1e. Write a function that takes an int list and generates a "multiplication * table", a list of int lists showing the product of any two entries in the * list. e.g. mult_table [1;2;3] => [[1; 2; 3]; [2; 4; 6]; [3; 6; 9]] *) let mult_table (lst: int list) : int list list = map (fun x -> times_x x lst) lst (* 1f. Write a function that takes a list of boolean values * [x1; x2; ... ; xn] and returns x1 AND x2 AND ... AND xn. * For simplicity, assume and_list [] is TRUE. Use reduce. *) let and_list (lst: bool list) : bool = reduce (fun v a -> v && a ) true lst (* 1g. Do the same as above, with OR. * Assume or_list [] is FALSE. *) let or_list (lst: bool list) : bool = reduce (fun v a -> v || a) false lst (* 1h. Write a function that takes a bool list list and returns * its value as a boolean expression in conjunctive normal form (CNF). * A CNF expression is represented as a series of OR expressions joined * together by AND. * e.g. transform this: [ [x1; x2]; [x3; x4; x5]; [x6] ] in to this: (x1 OR x2) AND (x3 OR x4 OR x5) AND (x6). * Use map and/or reduce. * You may find it helpful to use and_list and or_list. *) let cnf_list (lst: bool list list) : bool = and_list (map or_list lst) (* You may use a function you wrote above to solve questions 1i to 1k. *) (* 1i. Write and_list to return a bool option, * where the empty list yields None. Use map and/or reduce. *) let and_list_smarter (lst: bool list) : bool option = reduce and_option None (map (fun x -> Some x) lst) (* 1j. Return the max of a list, or None if the list is empty. *) let max_of_list (lst:int list) : int option = reduce max_option None (map (fun x -> Some x) lst) (* 1k. Return the min and max of a list, or (None,None) if the list is empty. *) let bounds (lst:int list) : (int option * int option) = reduce (fun v a -> (min_option v (fst a),max_option v (snd a))) (None,None) (map (fun x -> Some x) lst) (* Exercise 2 : Folds *) (* equivalent to List.fold_right in the List module *) let rec fold_right (f:'a -> 'b -> 'b) (xs:'a list) (base:'b) : 'b = match xs with [] -> base | hd::tail -> f hd (fold_right f tail base) (* equivalent to List.fold_left in the List module *) (* more efficient than fold_right (tail recursive) *) let rec fold_left (f:'b -> 'a -> 'b) (base:'b) (xs:'a list) : 'b = match xs with [] -> base | hd::tail -> fold_left f (f base hd) tail (* 2a. Write reduce from lecture in terms of a fold operation *) let reduce f base xs = fold_right f xs base (* 2b. Takes a list and returns the same list: use a fold *) let id xs = fold_right (fun x acc -> x::acc) xs [] (* 2c. takes a list and returns the reverse: use a fold *) let reverse xs = fold_left (fun acc x -> x::acc) [] xs (* 2d. write the polymorphic map from lecture using fold *) let map f xs = fold_right (fun x acc -> f x::acc) xs [] (* 2e. write a function that maps f across a list and reverses the result *) let map_rev f xs = fold_left (fun acc x -> f x::acc) [] xs (* 2f. Write a function that concats two lists into a single list *) (* With recursion *) let rec concat xs ys = match xs with | [] -> ys | hd::tail -> hd::concat tail ys (* Without recursion, using fold *) let concatF xs ys = fold_right (fun x ys -> x::ys) xs ys