(* 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 calc_option (f: 'a->'a->'a) (x: 'a option) (y: 'a option) : 'a option = failwith "unimplemented";;

(* 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 = failwith "unimplemented";;


let max_option (x: int option) (y: int option) : int option = failwith "unimplemented";;

(* 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 = failwith "unimplemented";;


let or_option (x:bool option) (y: bool option) : bool option = failwith "unimplemented";;


(* 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 = failwith "unimplemented";;



(* 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 = failwith "unimplemented";;




(* 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 = failwith "unimplemented";;




(* 1d. Rewrite times_3 in terms of times_x. 
 * This should take very little code. *)
let times_3_shorter = failwith "unimplemented";;

    
(* 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 = failwith "unimplemented";;




(* 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 = failwith "unimplemented";;




(* 1g. Do the same as above, with OR.
 * Assume or_list [] is FALSE. *)
let or_list (lst: bool list) : bool = failwith "unimplemented";;



(* 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 = failwith "unimplemented";;



(* You may use a function you wrote earlier in Precept 2 (or Exercise 0), 
 * 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 = failwith "unimplemented";;




	
(* 1j. Return the max of a list, or None if the list is empty. *)
let max_of_list (lst:int list) : int option = failwith "unimplemented";;




(* 1k. Return the min and max of a list, or None if the list is empty. *)
let bounds (lst:int list) : (int option * int option) = 
  failwith "unimplemented";;



(* 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
;;

(* Simple tests *)

let eg1 = [1;2;3;4];;
let eg2 = [];;

(* Challenges *)

(* 2a. Write reduce from lecture in terms of a fold operation *)
let reduce f base xs = failwith "unimplemented";;
		 
(* 2b. Takes a list and returns the same list: use a fold *)
let id xs = failwith "unimplemented";;

(* 2c. takes a list and returns the reverse: use a fold *)
let reverse xs = failwith "unimplemented";;

(* 2d. write the polymorphic map from lecture using fold *)
let map f xs = failwith "unimplemented";;
 
(* 2e. write a function that maps f across a list and reverses the result *)
let map_rev f xs = failwith "unimplemented";;

(* 2f. Write a function that concats two lists into a single list *)

(* With recursion *)
let rec concat xs ys = failwith "unimplemented";;

(* Without recursion, using fold *)
let concatF xs ys = failwith "unimplemented";;