(* return the kth item in xs if it exists, otherwise None *)
let rec kth (k:int) (xs:'a list) : 'a option =
  match xs with
  | [] -> None
  | hd :: tl -> 
      if k = 0 then Some hd 
      else kth (k-1) tl

let _ = assert (kth 0 [1; 2; 3] = Some 1)
let _ = assert (kth 1 [1; 2; 3] = Some 2)
let _ = assert (kth 2 [1; 2; 3] = Some 3)
let _ = assert (kth 3 [1; 2; 3] = None)               

(* return a list in which for each element in xs, there are 
   two consecutive copies of that element *)
let rec dup (xs:'a list) : 'a list =
  match xs with
  | [] -> []
  | hd :: tl -> hd :: hd :: dup tl

let _ = assert (dup [] = [])
let _ = assert (dup [1] = [1;1])
let _ = assert (dup [1;2] = [1;1;2;2])
let _ = assert (dup [1;2;3] = [1;1;2;2;3;3])