(* Solution set for Homework 1 *)

(*************** Programming style ************************)

let abc (x:bool) (y:bool) (z:bool) : bool =
  x && ( y || z )

let t (b:bool) (x:float) : float =
  let v = if b then sin x +. 1.0 else cos x in 
	 v *. v 

let danQuayle 
  (((a,b),c):(float*float)*float)
  (((d,e),f):(float*float)*float) : float*float*float =
	( b*.f -. c*.e, 
	  c*.d -. a*.f, 
	  a*.e -. b*.d)

(* finds the largest element in a list, given 
   a default value. *)
let rec max (l: int list) (curr:int)  : int = 
  match l with 
		[] -> curr
	 | (hd :: tl) -> 
		  if hd > curr then max tl hd
		  else max tl curr

(* Reverses the order of elements in a list *)
let reverse (l:int list) : int list  = 
  let rec reverse_aux (l: int list) (acc: int list) : int list = 
	 match l with 
		  [] -> acc
		| (hd :: tl) -> reverse_aux tl (hd :: acc) 
  in 
	 reverse_aux l [] 

(************ Programming Language Syntax *****************)

(* let x = 3 is not syntactically correct because there is 
 * no body to the let expression. *)

(* let add (x:int) (y:int) = x + y in add 2 is not 
 *	correct because the function is not annotated with its 
 *	return type. This is different than O'Caml where the 
 *	return type is optional. *)

(* 3 + 4 * 5 is syntactically correct *)

(* let count (x:int) :int = 
	  if x = 0 then 0 else count 1 + (x - 1)
   in count 3 
	
 *	is not syntactically correct for one reason:
 * - I ommitted equality (=) from the list of binary operators.
 * There is another problem with this function, it is 
 * recursive, so there should be a rec after let, however, 
 * according to just the rules of the grammar, it is ok to omit the rec.  
 *)

(********* More programming language syntax ***************)

(* The ML expression: 

  let x = 3 in 
  let y z = x in 
    if true 
    then (y 4) + (y 5) 
    else y 6
*)

(* Would be written as the following in Scheme:
 *
 * (let (x 3) 
 *	  (let (y (lambda (z) x))
 *		  (if #t
 * 			(+ (y 4) (y 5))
 *			   (y 6))))
 *)

(* Assuming that variables are distinguishable from the keywords 
 * (if, lambda, let, letrec) and the operators, then the grammar 
 *	is not ambiguous. 

 * An arbitrary expression could be a variable, a boolean value, 
 * a number or somthing in parentheses. We can tell all of these 
 * cases apart easily. If it is something in parentheses, we can also 
 * tell what sort of expression it is by looking at the first token. 
 * Either the first word is one of the keywords (if, lambda, let, letrec)
 * or it is a binary or prefix operator or it isn't any of the above, 
 * in which case it must be an application expression.
 *)

(*************  ML Programming from EOPL ******************)

(* duple n x returns a list containing n copies of x 
 * for example:
 *  duple 2 3  return [3;3]
 *  duple 4 ("ho","ho") returns 
 *      [ ("ho","ho"); ("ho","ho"); ("ho","ho"); ("ho","ho")] *)

let rec duple (n: int) (x:'a) : ('a * 'a) list = 
	 if n = 0 then []
	 else (x,x) :: (duple (n-1) x)

let d1 = duple 2 2
let d2 = duple 0 1 

(* 
	val d1 : (int * int) list = [(2, 2); (2, 2)]
	val d2 : (int * int) list = []
*)


(* invert lst, returns a list with each pair reversed. 
 * for example:
 *   invert [("a",1);("a",2)] returns [(1,"a"),(2,"a")] *)

let rec invert (lst : ('a * 'b) list) : ('b * 'a) list = 
  match lst with 
		[] -> []
	 | ((x,y) :: tl)  -> (y,x) :: invert tl

let i1 = invert [("a",1);("a",2)]

(* val i1 : (int * string) list = [(1, "a"); (2, "a")] *) 

(* filter pred lst returns the list of those elements in 
 * list that satisfy pred.
 * for example:
 *    filter odd [0;1;2;3;4] return [1;3]
 *)

let rec filter (pred: 'a -> bool) (lst: 'a list) : 'a list = 
  match lst with 
		[] -> []
	 | (hd :: tl) -> 
		  if (pred hd) then hd :: (filter pred tl)
		  else (filter pred tl)

let odd (x:int) = x mod 2 = 1 
let f1 = filter odd [0;1;2;3;4] 
(* val f1 : int list = [1; 3] *)

(* find pred lst returns the first element of the list that 
	satisfies the predicate. Because no element may do so, the 
	answer is returned in an option.
*)

let rec find (pred:'a -> bool) (lst:'a list) = 
  match lst with 
		[] -> None
	 | (hd :: tl) -> 
		  if pred hd then Some hd 
		  else find pred tl

let f2 = find odd [0;1;2]
let f3 = find odd []

(* 
	val f2 : int option = Some 1
	val f3 : int option = None
*)



(* every pred lst returns false if any element of lst 
 * fails to satisfy pred.
 *)
let rec every (pred: 'a -> bool) (lst: 'a list) : bool =
  match lst with 
		[] -> true
	 | (hd::tl) -> pred hd && every pred tl

let e1 = every odd [1;2;3]
let e2 = every odd [1;3;5]

(* list_set lst n x returns a list like lst, except that 
 *	the nth element (using zero-based indexing) is x. 
 * for example:
 *   list_set [1;2;3;4] 2 8 returns  [1;2;8;4]
 *   list_set [1;2;3] 5 10 returns [1;2;3]
 * You can assume n will be >= 0.
 *)

(* 
	val e1 : bool = false
	val e2 : bool = true
*)

let rec list_set (lst:'a list) (n:int) (x:'a) = 
  match lst with 
		[] -> []
	 | (hd::tl) -> if n=0 then x :: tl
		else hd :: list_set tl (n - 1) x

let l1 =  list_set [1;2;3;4] 2 8 
let l2 =  list_set [1;2;3] 5 10 

(* 
	val l1 : int list = [1; 2; 8; 4]
	val l2 : int list = [1; 2; 3]
*)


(* merge lon1 lon2, where lon1 and lon2 are lists of numbers sorted in
 *	ascending order, returns a sorted list of all the numbers in lon1 and
 *	lon2. For example:
 *  merge [1;4] [1;2;8] returns [1;1;2;4;8] 
 *)

let rec merge (lon1:int list) (lon2:int list) : int list = 
  match lon1,lon2 with 
		[],_ -> lon2
	 | _,[] -> lon1
	 | (hd1::tl1),(hd2::tl2) -> 
		  if hd1 < hd2 then hd1 :: merge tl1 lon2
		  else hd2 :: merge lon1 tl2

let m1 = merge 
			  [35; 62; 81; 90; 91] 
			  [3; 83; 85; 90]

let m2 = merge [1;4] [1;2;8] 

(*
  val m1 : int list = [3; 35; 62; 81; 83; 85; 90; 90; 91]
  val m2 : int list = [1; 1; 2; 4; 8]
*)


(* bst is the representation of a binary search tree.  In a node of
	this tree, the numbers contained in the left subtree are smaller than
	the int at the node, and the numbers in the right subtree are
	greater. *)
type bst = N of int * bst * bst | L 

type dir = Left | Right

(* path n bst returns a list of Lefts and Rights, showing how to find
	the node containing n. If n is found at the root, return [].
	You may assume that the number exists in the tree. Use the 
	"failwith" function for the case that cannot happen.

   for example:
    path 17 (N (14, N(7, L, N(12, L, L))
	 				     N(26, N(20, N(17, L,L), L)
							     N(31,L,L))))
	 returns Some [Right; Left; Left]
*)
let rec path (n:int) (bst:bst) : dir list = 
  match bst with 
		L -> failwith "Impossible"
	 | N (i, left, right) ->
		  if i = n then []
		  else if i < n then 
			 Right :: (path n right)
		  else Left :: (path n left)
			 
let p1 =  path 17 (N (14, 
							 N(7, L, N(12, L, L)),
	 						 N(26, 
								N(20, N(17, L,L), L),
								N(31,L,L))))
(* 
	val p1 : dir list = [Right; Left; Left]
*)