(* Exercice 1: 2pts *)
(* 1 *)
(* voir le cours *)

(* Exercice 2: 6pts *)
(* 2 à tester soi-même *)
(* 3 à tester soi-même *)
(* 4 à tester soi-même *)
(* 5 mystere1 et mystere2 sont équivalentes *)
(* 6 prend en paramètre une liste l d'élements de type 'a et un prédicat p s'appliquant à des objets de type 'a et retourne la liste des éléments de l qui vérifient p dans l'ordre inverse d'apparition dans l  *)

(* 7 *)
(* mystere2 l p est en O(len(l)^2) donc quadratique du fait de la concaténation en fin de liste r @ [e] alors que mystere1 l p est en O(len(l)) donc linéaire.
Ceci explique que mystere1 soit plus rapide que mystere2.
 *)

(* 8 *)
let  mystere_rt l f =
  let rec aux l nl =
    match l with
      [] -> nl
    | e :: t -> aux t (if f e then e :: nl else nl)
  in aux l []

(* 9 *)
(* en intervertissant l'ordre des paramètres mystere2 l p est  équivalente à List.filter p l
 *)

(* Exercice 3: 4pts *)
(* 10 *)
let count e l =
  List.fold_left (fun c x -> c + if x = e then 1 else 0) 0 l

(* 11 *)
let rec list_to_2set l =
  match l with
    [] -> []
  | e :: t -> 
      let l' = list_to_2set t in
      if count e l' < 2 then
	e :: l'
      else l'

(* Exercice 4: 5pts*)
(* 12 *)
let monster_arity m = List.length (monster_children m)

(* 13 *)
let rec monster_size m =
  List.fold_left (+) 1 (List.map monster_size (monster_children m))

(* 14 *)
let rec monster_max_arity m =
  let children = monster_children m in
  max
    (List.length children)
    (List.fold_left max 0 (List.map monster_max_arity children))

(* Exercice 4: 3pts*)
(* 15 *)
let dict_of_keys_and_values keys values =
  fun key ->
  let rec aux keys values =
    match keys, values with
      k :: keys', v :: values' -> if k = key then Some v
                                  else aux keys' values'
    | _ -> None
  in aux keys values