(* Solutions Week 1 *)

(* 2(a) *)
let rec range m n =
  if m > n then [] else m :: range (m + 1) n;;

assert ([1;2;3;4;5] = range 1 5);;

(* 2(b) *)
let cons x xs = x :: xs

let rec prefix = function 
  | [] -> [ [] ]
  | x :: xs -> [] :: List.map (cons x) (prefix xs);;

assert ([[];[1];[1;2];[1;2;3]] = prefix [1;2;3]);;

(* 3(a-e) See /usr/lib/ocaml/list.ml. *)

(* 4(a) *)
let append list1 list2 = List.fold_right cons list1 list2;;

(* 4(b) *)
let for_all p list = List.fold_right (fun x b -> p x && b) list true;;

(* 4(c) *)
let exists p list = List.fold_right (fun x b -> p x || b) list false;;

(* 4(d) *)
let map f list = List.fold_right (fun x ys -> f x :: ys) list [];;

assert ([1;2;3] = map ((+) 1) [0;1;2]);;

(* 4(e) *)
let filter p list =
  let f x xs = if p x then x :: xs else xs in
  List.fold_right f list [];;

assert ([0;2] = filter (fun x -> x mod 2 = 0) [0;1;2]);;

(* 5(a) *)
let rec insert x = function
  | [] -> [x]
  | y :: ys when x < y -> x :: y :: ys
  | y :: ys -> y :: insert x ys;;

assert ([0;1;2;4] = insert 1 [0;2;4]);;
assert ([0;2;2;4] = insert 2 [0;2;4]);;

(* 5(b) *)
let isort list = List.fold_right insert list [];;

assert ([1;2;3] = isort [2;3;1]);;