let product lst =
  let rec product_tr acc = function 
    | [] -> acc 
    | h::t when h!=0 -> product_tr (h*acc) t
    | _ -> 0 
  in
  product_tr 1 lst
;;

let concat lst =
  let rec concat_tr acc = function
    |[] -> acc
    |h::t -> concat_tr (acc ^ h) t 
  in 
  concat_tr "" lst
;;

open OUnit2
open Product

let test_product = "test_product" >::: [
    "empty list" >:: (fun _ -> assert_equal 1 (product []) ) ;
    "one element" >:: (fun _ -> assert_equal 4 (product [4]) );
    "two elelemts" >:: (fun _ -> assert_equal 30 (product [5;6]) ) ;
    "contains zero" >:: (fun _ -> assert_equal 0 (product [0;34;54;12;1;3;5;6;] )  );
  ]


let _ = run_test_tt_main test_product

open Fifth
open OUnit2

let make_fifth_testcase name expect lst =
  name >:: (fun _ -> assert_equal  expect (fifth lst) )
;;

let fifth_test = "test suite of fifth" >::: [
    make_fifth_testcase "empty list" 0 [] ;
    make_fifth_testcase "lewer than five elements" 0 [1;3;4;5] ;
    make_fifth_testcase "exactly five elements" 5 [1;2;3;4;5] ;
    make_fifth_testcase "more then five elements" 5 [1;2;3;4;5;6] 
  ]

let _  = run_test_tt_main fifth_test 

open OUnit2
open Descend

let make_descend_testcase name expect lst =
  name >:: (fun _ -> assert_equal expect (descend lst) ) 
;;

let descend_test_suite = "test descend" >::: [
    make_descend_testcase "empty list" [] [] ;
    make_descend_testcase "one element" [3] [3] ;
    make_descend_testcase "ascending list" [3;2;1] [1;2;3] 

  ]

let _ = run_test_tt_main descend_test_suite

let ( -- ) s e = 
  let rec from acc i j =
    if i > j then acc
    else  from  (j::acc) i (j-1)
  in
  from [] s e
;;

let longlist = 1 -- 1000000 ;; 

let  is_unimodal  lst =
  let rec impl  is_ascend_seg  l =
    match l with
    |[] -> true
    |[_] -> true
    (*下面的list模式表示 至少包含两个元素：*)
    |h::m::t when h=m  -> impl is_ascend_seg (m::t)  
    |h::m::t when h<m  -> if is_ascend_seg then impl true (m::t) else false
    |h::m::t (* when h>m *)-> impl false (m::t)
  in
  impl true lst
;;

let rec add_element acc e = function
  |[] -> acc
  |h::t ->  add_element ((e::h)::acc)  e t
;;

let rec powerset = function
  |[] -> [ [] ]
  |h::t -> let s = powerset t in (add_element [] h s ) @ s
;;

let rec print_int_list = function
| [] -> ()
| h :: t -> (* fill in here *); print_int_list t

let rec print_int_list = function
  | [] -> ()
  | h :: t ->  print_endline (string_of_int h); print_int_list t
;;

let print_int_list' lst =
  List.iter (fun x -> (*fill in here*)  )  lst
;;

let print_int_list' lst =
  List.iter (fun x ->  print_endline (string_of_int x)  )  lst
;;

type student = {first_name : string ;last_name:string ;gpa :float}
;;

type poketype = Normal | Fire | Water ;;

type pokemon = { name:string; hp:int; ptype:poketype } ;;

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

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

let safe_hd = function
  | [] -> None
  | h::t -> Some h
;;

let rec safe_tl = function
  | [] -> None
  | [x]-> Some x 
  | _::t ->  safe_tl t
;;;

let max_hp_poke acc s =
 match (acc,s) with
   |(None, a) -> a
   |(a,None) -> a
   |(Some x,Some y) -> if x.hp>y.hp then Some x else Some y
;;

let max_hp lst =
  let rec impl acc  = function
  | [] -> acc 
  | h::t -> impl (max_hp_poke acc (Some h)) t  
  in
  impl None lst
;;

type date_like = int*int*int 

let is_leap_year y =
  if y mod 100 !=0 && y mod 4=0 then true
  else if y mod 400 = 0 then true
  else false


let is_valid_date  = function
  | (y,m,d)  when y <= 0 -> false  
  | (y,m,d) when m>12 || m<1 ->false
  | (y,m,d) when d>31 || d<1 ->false
  | (y,m,d) when  (is_leap_year y) && m = 2 && d >29  -> false 
  | (y,m,d) when  not (is_leap_year y) && m = 2 && d >28  ->false
  | (y,m,d) when  m mod 2=0 && d > 30  -> false
  | _ -> true


let is_before d1 d2 =
  if not (is_valid_date d1) || not (is_valid_date d2) then failwith "invalid date"
  else 
    match (d1,d2) with
    | ((y,m,d),(y1,m1,d1)) when y<y1 -> true
    | ((y,m,d),(y1,m1,d1)) when y=y1 && m<m1 -> true
    | ((y,m,d),(y1,m1,d1)) when y=y1 && m=m1 && d < d1 -> true
    | _ -> false
;;

let earlier d1 d2 =
  match (d1,d2) with
  | (None,x) -> x
  |(x,None) -> x
  |(Some a,Some b)-> if is_before a b then Some a else Some b



 let rec earliest lst  =
   let rec impl acc = function
   |[] -> acc
   |h::t -> impl (earlier (Some h) acc) t  
   in
   impl None lst
 ;;

let insert k v lst = (k,v)::lst

let rec lookup key = function
  | [] -> None
  | (k,v)::t -> if k = key then v else lookup key t
;;

let numlist = [] ;;

insert 1 "one" numlist;;
insert 2 "two" numlist;;
insert 3 "three" numlist;;

lookup 2 ;;
lookup 4 ;;

type suit = Clubs | Diamonds | Hearts | Spades ;; (*花色*)

type rank =
  One | Two | Three | Four | Five | Six |Seven | Eight |Nine |Ten |Jack | Queen| King|Ace
;; (* 点数 *)

type card =
  { suit:suit ; rank:rank} ;;

{ suit = Clubs ; rank=Ace } ;;
{ suit = Hearts; rank=Queen};;
{ suit = Diamonds; rank= Two};;
{ suit = Spades ; rank = Seven};;

[None; Some 1] ;;

[Some 2110;None] ;;

[None;Some 2];;

[Some 1 ] ;;

  type quad = I | II | III | IV
  type sign = Neg | Zero | Pos
;;
  let sign (x:int) : sign =
    ...

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

let sign (x:int) :sign =
  match x with
  |i when i> 0 -> Pos
  |i when i<0 -> Neg
  | _ -> Zero


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

let quadrant' : int*int -> quad option = fun (x,y)  ->
   match (x , y) with
     |(a,b) when a>0&& b>0 -> Some I
     |(a,b) when a<0&& b>0 -> Some II
     |(a,b) when a<0&& b<0 -> Some III
     |(a,b) when a>0 && b<0 -> Some IV
     |_-> None
;;

type 'a tree = Leaf | Node of 'a * 'a tree * 'a tree ;;

let rec depth = function
  | Leaf -> 0
  | Node (v,left,right) -> 1 + (max (depth left) (depth right) )
;;

let rec  same_shape (ta:'a) (tb:'b) : bool = match (ta,tb) with
  |(Leaf,Leaf) -> true 
  |( (Node(_,la,ra)) ,(Node(_,lb,rb))) ->  (same_shape la lb) &&( same_shape ra rb)
  | _ -> false
;;

let ta = Node(2,Node(1,Leaf,Leaf) ,Node(3,Leaf,Leaf) ) 
let tb = Node (2. ,Node(1.,Leaf,Leaf) ,Node (3.,Leaf,Leaf) ) ;;

same_shape ta tb ;;
- : bool = true

  let rec list_max = function 
      |[x] -> x
      |h::t -> max h (list_max t)
      | _ -> failwith "list_max" 
;;

let list_max_string : int list -> string = fun lst ->
  try string_of_int (list_max lst) with
  |_ -> "empty"
;;

open OUnit2

let rec list_max = function 
  | [x] -> x 
  | h::t -> max h (list_max t) 
  | _ -> failwith "list_max"
;;


let test_list_max = "list_max" >::: [
    "empty list" >:: (fun _ -> assert_raises (Failure "list_max") (fun () -> list_max []) ) ;
    "nonempty list" >:: (fun _ -> assert_equal 3 (list_max [1;2;3;1] )) 
  ]

let _ = run_test_tt_main test_list_max ;;

let d = 
  Node((2,"two"), 
    Node((1,"one"),Leaf,Leaf),
    Node((3,"three"),Leaf,Leaf)
  )

val sign : int -> [> `Neg | `Pos | `Zero ]
val quadrant : int * int -> [> `I | `II | `III | `IV ] option

let sign = function
  |i when i>0 -> `Pos
  |i when i=0 -> `Zero
  |_ -> `Neg
;;

let quadrant (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 
;;