(* 1 *)

let average l =
  let rec traverse somme longueur = function
    | [] -> somme /. (float_of_int longueur)
    | x::l' ->
        traverse (float_of_int x +. somme) (longueur + 1) l'
  in
  traverse 0. 0 l;;

(* ou: *)

let rec fold_left f acc l = match l with
  | [] -> acc
  | x::l' -> fold_left f (f acc x) l';;

let average l =
  let sum, num = fold_left
    (fun (sum,num) x -> sum + x, num+1)
    (0,0) l
  in
  match l with
  | [] -> 0.
  | _ -> float_of_int sum /. float_of_int num;;

let rec sorted = function
  | []
  | [_] -> true
  | x::y::l -> x <= y && sorted (y::l);;

let rec sorted_strict = function
  | []
  | [_] -> true
  | x::y::l -> x < y && sorted (y::l);;

let rec maxmin' lowest (a,b) l =
    match l with
    | [] -> a,b
    | [x] ->
        if x-lowest > b-a then lowest,x else (a,b)
    | x::l' ->
        let lowest' = min x lowest in
        let a,b = if x-lowest > b-a then lowest,x else a,b in
        maxmin' lowest' (a,b) l';;

let maxmin = function
    | [] -> failwith "empty"
    | x::l' -> maxmin' x (x,x) l';;

let rec insert l x = match l with
  | [] -> [x]
  | y::l when x < y -> x :: y :: l
  | y::l -> y :: (insert l x);;

let sort l =
  let rec traverse acc = function
    | [] -> acc
    | x::l ->
        let acc' = insert acc x in
        traverse acc' l
  in
  traverse [] l;;

(* 2 *)

(* 2.1 *)

let rec mem l x = match l with
  | [] -> false
  | y :: l' -> x = y || mem l' x;;

let multiplicity l x =
  let rec count n = function
  | [] -> n
  | y::l' ->
      let n' = if x = y then n+1 else n in
      count n' l'
  in
  count 0 l;;

let support l =
  let rec traverse acc = function
    | [] -> acc
    | x::l' ->
        let acc' = if mem acc x then acc else x :: acc in
        traverse acc' l'
  in
  traverse [] l;;

(* 2.2 *)

let rec add m x i =
  if i = 0 then m else x :: add m x (i-1);;

let combine f m1 m2 =
  let rec traverse acc elements = match elements with
  | [] -> acc
  | x :: elements' ->
      let how_many_x = f (multiplicity m1 x) (multiplicity m2 x) in
      let acc' = add acc x how_many_x in
      traverse acc' elements'
  in traverse [] (support (m1 @ m2));;

let somme m1 m2 =
  combine (fun x y -> x+y) m1 m2 ;;

let union m1 m2 =
  combine max m1 m2 ;;

let difference m1 m2 =
  combine (fun x y -> max 0 (x-y)) m1 m2 ;;

let intersection m1 m2 =
  combine min m1 m2;;

(* sur les fonctions *)

let somme_fct m1 m2 x = m1 x + m2 x;;
let union_fct m1 m2 x = max (m1 x) (m2 x);;
let difference_fct m1 m2 x = max 0 (m1 x - m2 x);;
let intersection_fct m1 m2 x = min (m1 x) (m2 x);;

(* 2.3 *)

let rec map f = function
  | [] -> []
  | x::l' -> f x :: map f l';;

let compact m =
  let l = support m in
  map (fun x -> x, multiplicity m x) l;;

let rec remove m x = match m with
  | [] -> []
  | (y,i) :: m' when x = y ->
      if i = 1
        then m'   (* x n'est plus élément du résultat *)
        else (y,i-1) :: m'
  | pair :: m' -> pair :: remove m' x ;;