Cornell cs3110 - Chapter3 Exercises

(* Exercise: list expressions *)
let list1 = [1; 2; 3; 4; 5];;
let list2 = 1 :: 2 :: 3 :: 4 :: 5 :: [];;
let list3 = [1] @ [2; 3; 4;] @ [5];;

(* Exercise: product *)
let rec product l =
  match l with 
  | [] -> 1
  | h :: t -> h * product t;;

(* Exercise: concat *)
let rec concat l =
  match l with 
  | [] -> ""
  | h :: t -> h ^ concat t;;

(* Exercise: product test *)
let product_test = product [1; 2; 3; 4; 5] = 120;;

(* Exercise: concat test *)
let concat_test = concat ["a"; "b"; "c"; "d"; "e"] = "abcde";;

(* Exercise: patterns *)
let pattern_match_1 = function
  | h :: t -> if h = "bigred" then true else false 
  | _ -> false;;

let rec pattern_match_2 l depth = 
  match l with
  | [] -> if depth = 2 || depth = 4 then true else false 
  | h :: t -> pattern_match_2 t (depth + 1);;

let pattern_match_3 = function 
  | h1 :: h2 :: t -> if h1 = h2 then true else false
  | _ -> false;;

(* Exercise: library *)
let library_func_1 l = 
  if List.length l < 5 then 0 
  else List.nth l 4;;

let library_func_2 l =
  List.sort compare l |> List.rev;;

(* Exercise: library test *)
let library_test_1 = library_func_1 [1; 2; 3; 4; 5; 6; 7; 8; 9; 10] = 5;;

let library_test_2 = library_func_2 [1; 2; 3; 4; 5; 6; 7; 8; 9; 10] = [10; 9; 8; 7; 6; 5; 4; 3; 2; 1];;

(* Exercise: library puzzle *)
let library_puzzle_1 l =
  if List.length l = 0 then None
  else Some ((List.length l - 1) |> List.nth l);;

let any_zeros l =
  List.exists (fun x -> x = 0) l;;

(* Exercise: take drop *)
let rec take n l = 
  match l with 
  | [] -> []
  | h :: t -> if n = 0 then [] else h :: take (n - 1) t;;

let rec drop n l = 
  match l with 
  | [] -> []
  | h :: t -> if n = 0 then l else drop (n - 1) t;;

(* Exercise take drop tail *)
let rec take n l1 l2 =
  match l1 with
  | [] -> []
  | h :: t -> if n = 0 then l2 else take (n - 1) t (l2 @ [h]);;

(* Exercise: unimodal *)
let rec is_unimodal l direction = 
  match l with 
  | [] -> true
  | h :: [] -> true
  | h1 :: h2 :: t -> 
    if direction = 0 then 
      if h1 < h2 then is_unimodal (h2 :: t) 1
      else if h1 > h2 then is_unimodal (h2 :: t) 2
      else false
    else if direction = 1 then 
      if h1 < h2 then is_unimodal (h2 :: t) 1
      else if h1 > h2 then is_unimodal (h2 :: t) 0
      else is_unimodal (h2 :: t) 0
    else 
      if h1 < h2 then false
      else if h1 > h2 then is_unimodal (h2 :: t) 2
      else is_unimodal (h2 :: t) 0;;

(* Exercise: powerest *)
let rec powerest = function 
  | [] -> [[]]
  | h :: t -> (powerest t) @ (List.map (fun x -> h :: x) (powerest t));;

(* Exercise: print int list rec*)
let rec print_int_list l = 
  match l with 
  | [] -> ()
  | h :: t -> print_int h; print_string "\n"; print_int_list t;;

(* Exercise: print int list iter *)
let print_int_list_iter l = 
  List.iter (fun x -> print_int x; print_string "\n") l;;

(* Exercise: student *)
type student = {first_name: string; last_name: string; gpa: float};;

let stu1 : student = {first_name = "John"; last_name = "Doe"; gpa = 3.5};;

let get_name s = s.first_name ^ " " ^ s.last_name;;

let get_record s =  s.first_name ^ " " ^ s.last_name ^ " " ^ string_of_float s.gpa;;

(* Exercise: pokerrecord *)
type pokertype = Normal | Fire | Water;;

type pokerman = {
  name: string;
  hp: int;
  ptype: pokertype
};;

let charizard = {name = "Charizard"; hp = 78; ptype = Fire};;

let squirtle = {name = "Squirtle"; hp = 44; ptype = Water};;

(* Exercise: safe hd and tl *)
let safe_hd l = 
  match l with 
  | [] -> None
  | h :: t -> Some h;;

let safe_tl l =
  match l with 
  | [] -> None
  | h :: t -> Some t;;

(* Exercise: pokefun *)
let rec max_hp = function 
  | [] -> None 
  | h :: [] -> Some h.hp
  | h :: t -> if h.hp > (max_hp t |> Option.get) then Some h.hp else max_hp t;;

(* Exercise: date before *)
type date = int * int * int;;

let is_before d1 d2 = 
  match d1, d2 with 
  | (y1, m1, d1), (y2, m2, d2) -> 
    if y1 < y2 then true
    else if y1 = y2 then 
      if m1 < m2 then true
      else if m1 = m2 then 
        if d1 < d2 then true
        else false
      else false
    else false;;

(* Exercise: earliest date *)
let rec earliest = function 
  | [] -> None
  | h :: [] -> Some h
  | h :: t -> if is_before h (earliest t |> Option.get) then Some h else earliest t;;

(* Exercise: assoc list *)
let insert k v lst = (k, v) :: lst;;

let assoc_list = [] |> insert "a" 1 |> insert "b" 2 |> insert "c" 3;;

(* Exercise: quadrant *)

type quad = I | II | III | IV;;

type sign = Neg | Zero | Pos;;

let sign (x : int) : sign = 
  if x < 0 then Neg
  else if x = 0 then Zero
  else Pos;;

let quadrant : int * int -> quad option = fun (x, y) ->
  match sign x, sign y with
  | Pos, Pos -> Some I
  | Neg, Pos -> Some II
  | Neg, Neg -> Some III
  | Pos, Neg -> Some IV
  | _, _ -> None;;

(* Exercise: quadrant when *)
let quadrant_when : int * int -> quad option = function
  | (x, y) when x > 0 && y > 0 -> Some I
  | (x, y) when x < 0 && y > 0 -> Some II
  | (x, y) when x < 0 && y < 0 -> Some III
  | (x, y) when x > 0 && y < 0 -> Some IV
  | _ -> None;;

(* Exercise: depth *)
type 'a tree = Leaf | Node of 'a * 'a tree * 'a tree;;

let rec depth = function 
  | Leaf -> 0
  | Node (_, l, r) -> max (depth l) (depth r) + 1;;


(* Exercise: shape *)
let rec shape t1 t2 = 
  match t1, t2 with 
  | Leaf, Leaf -> true 
  | Node (_, l1, r1), Node (_, l2, r2) -> shape l1 l2 && shape r1 r2
  | _, _ -> false;;

(* Exercise: list max exn *)
let rec list_max_exn = function 
  | [] -> raise (Failure "empty list")
  | h :: [] -> h
  | h :: t -> max h (list_max_exn t);;

(* Exercise: is_bst *)
let rec is_bst = function 
  | Leaf -> true
  | Node (v, Leaf, Leaf) -> true
  | Node (v, Leaf, Node (rv, _, _)) -> v < rv && is_bst (Node (rv, Leaf, Leaf))
  | Node (v, Node (lv, _, _), Leaf) -> v > lv && is_bst (Node (lv, Leaf, Leaf))
  | Node (v, Node (lv, _, _), Node (rv, _, _)) -> v > lv && v < rv && is_bst (Node (lv, Leaf, Leaf)) && is_bst (Node (rv, Leaf, Leaf))
  | _, _ -> false;;