(**** PROBLEM 1 ****)

(** not tail recursive; more intuitive solution **)
let rec prod l = match l with
  | [] -> 1
  | h::t -> h * (prod t)

(** using type annotation **)
let rec prod_annot (l : int list) : int = match l with
  | [] -> 1
  | h::t -> h * (prod_annot t)

(** using an alternative syntax; simpler than using match **)
let rec prod_alt = function
  | [] -> 1
  | h::t -> h * (prod_alt t)

(** tail recursive - does not keep intermediate values around **)

(** helper function for tail-recursive prod **)
let rec prod_tailrec_helper acc l = match l with
  | [] -> acc * 1
  | h::t -> prod_tailrec_helper (acc * h) t

(** tail recursive prod **)
let prod_tailrec l = prod_tailrec_helper 1 l


(**** PROBLEM 2 ****)

(** not tail recursive **)
let rec addTail l e = match l with
  | [] -> [e]
  | h::t -> h::(addTail t e)

(** this buggy version (append) causes runtime type error; try [1;2;3] 4 **)
let rec addTail_buggy l e = match l with
  | [] -> e
  | h::t -> h::(addTail_buggy t e)

(** by inserting type annotations, we give *some* type information and find the
    error early**)
let rec addTail_annot (l : 'a list) (e : 'a) : 'a list = match l with
  | [] -> [e]
  | h::t -> h::(addTail_annot t e)


(**** PROBLEM 3 ****)

(** less intuitive solution but no helper function **)
let rec index l e = match l with
  | [] -> -1
  | h::t -> 
      let idx = index t e in
        if idx == -1 then (
          if h = e then 0
          else -1
        )
        else 1 + idx

(** more intuitive solution and more efficient **)
let rec index_tailrec_helper c i l e = match l with
  | [] -> i
  | h::t -> 
      if h = e then index_tailrec_helper (c+1) c t e
      else index_tailrec_helper (c+1) i t e

let index_tailrec l e = index_tailrec_helper 0 (-1) l e


(**** PROBLEM 4 ****)

let rec unzip_helper acc l = match acc, l with
  | _, [] -> acc
  | (f, s), (hf, hs)::t -> 
      unzip_helper (addTail f hf, addTail s hs) t

let unzip l = unzip_helper ([], []) l


(**** PROBLEM 5 ****)

let rec app_int f m n =
  if n < m then []
  else
    (f m)::(app_int f (m + 1) n)


(**** MORE PROBLEM ****)

(** opposite of unzip **)
let rec zip (a, b) = match a, b with
  | [], [] -> []
  | [], _ 
  | _, [] -> failwith "error"
  | fh::ft, sh::st -> (fh, sh)::(zip (ft, st))

(** non-tail recursive append; intuitive solution **)
let rec append l1 l2 = match l1 with
  | [] -> l2
  | h::t -> h::(append t l2)

(** tail recursive reverse **)
let rec reverse_helper acc l = match l with
  | [] -> acc
  | h::t -> reverse_helper (h::acc) t
let reverse l = reverse_helper [] l 

(** non-tail recursive reverse **)
let rec append_tailrec_helper acc l1 l2 = match l1, l2 with
  | [], [] -> reverse acc
  | [], h::t -> append_tailrec_helper (h::acc) [] t
  | h::t, _ -> append_tailrec_helper (h::acc) t l2

let rec append_tailrec l1 l2 = append_tailrec_helper [] l1 l2