answers.ml

Download file: answers.ml
(*** Keep these lines. ***)
let qfile = "qqs.ml" ;;
let formatter = Format.(make_formatter (fun _ _ _ -> ()) (fun () -> ())) ;;
Topdirs.dir_use formatter (if Sys.file_exists qfile then qfile else Sys.getenv "HOME" ^ "/Exam-OCaml/" ^ qfile) ;;

(*****  QUESTION 1  *****)

let rec f1 l1 l2 = match l1,l2 with
  | [], _ -> [], l2
  | _, [] -> l1, []
  | (x1 :: rest1), (x2 :: rest2) -> if x1 = x2 then f1 rest1 rest2 else l1, l2

let () = q1 { ff = f1 } ;;

(*****  QUESTION 2  *****)

let f2 = function
  | None -> 0
  | Some e -> raise e

let () = q2 { ff = f2 } ;;

(*****  QUESTION 3  *****)

let f3 l = List.map ( fun { nn ; vv } -> { nn = vv ; vv = nn } ) l


(*****  QUESTION 3, alternative  *****)
let rec f3 = function
  | [] -> []
  | c :: rest -> { nn = c.vv ; vv = c.nn } :: f3 rest 

let () = q3 { ff = f3 } ;;

(*****  QUESTION 4  *****)

(* apply_filter c filter applies the given filter to c *)
let apply_filter c = function
  | Equal x -> c.vv = x
  | GT x -> c.nn > x

let f4 ff ll = List.filter (fun c -> List.exists (apply_filter c) ff) ll

(*****  QUESTION 4, alternative  *****)

(* Still using apply_filter above *)
let rec f4 ff = function
  | [] -> []
  | c :: rest ->
    if List.exists (fun filter -> apply_filter c filter) ff
    then c :: f4 ff rest else f4 ff rest

(* For those who don't remember List.exists, it can be defined like this: *)
let exists f l = List.fold_left (fun acu x -> acu || f x) false l ;;


let () = q4 { ff = f4 } ;;

(*****  QUESTION 5  *****)

let rec f5 = function
  | [] -> []
  | [c] -> [c]
  | c1 :: c2 :: rest -> 
    if c1.vv = c2.vv then 
      (* Recursive call starting from the new value (not starting from the rest) 
         so that this element can still be compacted with the next elements. *)
      f5 ({ vv = c1.vv ; nn = c1.nn + c2.nn } :: rest)

    (* We must iterate from c2, not from the rest. *)
    else c1 :: f5 (c2 :: rest)

let () = q5 { ff = f5 } ;;

(*****  QUESTION 6  *****)

let f6 l = 

  (* Find all values *)
  let all_vv = List.fold_left (fun acu c -> if List.mem c.vv acu then acu else c.vv :: acu) [] l in

  (* Given a value v, compute the max of its associated .nn values *)
  let rec find_max v mx = function
    | [] -> mx
    | c :: rest -> if c.vv = v then find_max v (max mx c.nn) rest else find_max v mx rest
  in

  (* Compute max for each value *)
  List.map ( fun v -> { vv = v ; nn = find_max v 0 l } ) all_vv

let () = q6 { ff = f6 } ;;

(*****  QUESTION 7  *****)

let f7 tree = 

  (* Check that the values in the tree are between the given lower and upper bounds. *)
  let rec aux acu low upp = function
    | Z -> acu
    | C c -> if c.nn < low || c.nn > upp then c :: acu else acu        
    | S (left, cmp, right) ->
      let acu2 = aux acu low (min upp cmp) left in
      aux acu2 (max low cmp) upp right
  in

  aux [] min_int max_int tree

let () = q7 { ff = f7 } ;;