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 = function
  | [] -> []
  | [x] -> []
  | x :: y :: rest -> if x <= y then f1 (y :: rest) else (y :: rest) 

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


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

let f2 g =
  try g () ; None
  with e -> Some e

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


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

let get_vv c = c.vv
let get_nn c = c.nn

let f3 l = (List.map get_vv l, List.map get_nn l)

(*****  QUESTION 3, alternative  *****)
let rec f3 = function
  | [] -> [], []
  | c :: rest ->
      let (l1, l2) = f3 rest in
        (c.vv :: l1, c.nn :: l2)

(*****  QUESTION 3, alternative with acu  *****)
let f3 l =

  let rec aux acu1 acu2 = function
    | [] -> (List.rev acu1, List.rev acu2)
    | c :: rest -> aux (c.vv :: acu1) (c.nn :: acu2) rest
  in

    aux [] [] l


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.for_all (apply_filter c) ff) ll

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

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

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

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


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

let rec f5 = function
  | [] -> []
  | [_] -> []
  | c1 :: c2 :: rest -> { vv = c2.vv ; nn = c1.nn } :: 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 mean of its associated .nn values.
   * we make the sum, and nb is the number of elements *)
  let rec find_mean v sum nb = function
    | [] -> sum / nb
    | c :: rest -> if c.vv = v then find_mean v (sum + c.nn) (nb + 1) rest else find_mean v sum nb rest
  in

    (* Compute mean for each value *)
    List.map ( fun v -> { vv = v ; nn = find_mean v 0 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 } ;;