(* Exercice 1 *)

(* 1 *)
let premierElement l = match l with
  | [] -> failwith "liste vide"
  | t::q -> t
;;

premierElement [1; 2; 3] ;; (* 1 *)

premierElement [] ;; (* erreur *)

(* 2 *)
let rec dernierElement l = match l with
  | [] -> failwith "liste vide"
  | x::[] -> x
  | _::q -> dernierElement q
;;

dernierElement [1; 2; 3; 4] ;; (* 4 *)

(* 3 *)
let rec avantDernier l = match l with
  | [] | [_] -> failwith "liste trop petite"
  | t::_::[] -> t
  | t::q -> avantDernier q
;;

avantDernier [ 1 ; 2 ; 3 ] ;; (* 2 *)

avantDernier [] ;; (* erreur *)

(* 4 *)
let rec element l k = match (k,l) with
  | _, [] -> failwith "liste trop petite"
  | 0, t::_ -> t
  | k, _::q -> element q (k-1)
;;

element [12; 25; 42; 100] 0 ;; (* 12 *)

element [12; 25; 42; 100] 2 ;; (* 42 *)

element [12; 25; 42; 100] 4 ;; (* erreur *)

(* 5 *)
let rec indice l x = match l with
  | [] -> failwith "x n'appartient pas a l"
  | t::q when t=x -> 0
  | _::q -> 1 + indice q x
;;

indice [12; 42; 25; 100]  12 ;; (* 0 *)

indice [12; 25; 42; 100]  42 ;; (* 2 *)

indice [12; 25; 42; 100]  3 ;; (* erreur *)

let indice l x =
  let rec aux l x n = match l with
    | [] -> failwith "x n'appartient pas a l"
    | t::q when t=x -> n
    | _::q -> aux q x (n+1)
  in aux l x 0
;;

(* 6 *)
let rec ajouterEnQueue l x = match l with
  | [] -> [x]
  | t::q -> t::(ajouterEnQueue q x)
;;

ajouterEnQueue [1; 2; 3; 4] 5 (* [1; 2; 3; 4; 5] *)

(* 7 *)
let miroir l =
  let rec aux acc l = match l with
    | [] -> acc
    | x::q -> aux (x::acc) q
  in aux [] l
;;

miroir [1; 2; 3] ;; (* [3; 2; 1] *)

(* 8 *)
let rec maMap f l = match l with
  | [] -> []
  | t::q -> (f t)::(maMap f q)
;;

maMap (fun x -> 2*x) [1; 2; 3] ;; (* [2; 4; 6] *)

(* 9 *)
let rec somme l = match l with 
  | [] -> 0
  | t::q -> t + somme q
;;

somme [1; 2; 3; 4] ;; (* 10 *)

(* Exercice 2 *)
let rec mystere f l = match l with
  | [] -> []
  | t::q -> (f t)::(mystere f q)
;;

(* Exercice 3 *)
let rec mystere' f = function
  | [] -> []
  | t::q when f t > 1 -> t::(mystere' f q)
  | t::q -> mystere' f q
;;

(* 3 *)
let rec filtrer f = function
  | [] -> []
  | t::q when f t -> t::(filtrer f q)
  | t::q -> filtrer f q
;;

let est_pair n = n mod 2 = 0 ;;

filtrer est_pair [1; 2; 3; 4; 5; 6; 7] ;; (* [2; 4; 6] *)

(* Exercice 4 *)
let rec concat l1 l2 = match l1 with
  | [] -> l2
  | t::q -> t::(concat q l2)
;;

concat [1; 2; 3] [4; 5; 6] ;; (* [1; 2; 3; 4; 5; 6] *)

(* Exercice 5 *)
let rec listIt f l b = match l with
  | [] -> b
  | t::q -> f t (listIt f q b)
;;

listIt (fun x l -> x::l) [1; 2; 3] [4; 5; 6] ;; (* [1; 2; 3; 4; 5; 6] *)

(* Exercice 6 *)
(* 1 *)
let rec existe f l = match l with
  | [] -> false
  | t::q -> (f t) || existe f q (*Ici il y a évaluation paresseuse*)
;;

existe est_pair [1; 2; 3] ;; (* true *)

existe est_pair [1; 5; 3] ;; (* false *)

(* 2 *)
let rec pourTout f l = match l with 
  | [] -> true
  | t::q -> (f t) && pourTout f q
;;

pourTout est_pair [2; 4; 6] ;; (* true *)

pourTout est_pair [1; 2; 3] ;; (* false *)

(* Exercice 7 *)

(* 1 *)
let rec appartient x l = match l with
  | [] -> false
  | t::q -> x = t || appartient x q
;;

appartient 2 [1; 2; 3] ;; (* true *)

appartient 12 [1; 2; 3] ;; (* false *)

(* 2 *)
let rec purge l = match l with
  | [] -> []
  | t::q when appartient t q -> purge q
  | t::q -> t::(purge q)
;;

purge [1; 2; 3; 1; 4; 3; 1] ;; (* [2; 4; 3; 1] *)

(* 3 *)
let purge' l =
  let rec aux l l' = match l with
    | [] -> []
    | t::q when appartient t l' -> aux q l'
    | t::q -> t::aux q (t::l')
  in aux l []
;;

purge' [1; 2; 3; 1; 4; 3; 1] ;; (* [1; 2; 3; 4] *)

(* Exercice 8 *)

(* 1 *)
let rec membre x l = match l with
  | [] -> false
  | t::q when t=x -> true
  | _::q -> membre x q
;;

(* 2 *)
let rec union l1 l2 = match l1 with
  | [] -> l2
  | t::q -> t::(union q l2)
;;

(* 3 *)
let rec intersection l1 l2 = match l1 with
  | [] -> []
  | t::q when membre t l2 -> t::(intersection q l2)
  | t::q -> (intersection q l2)
;;

(* 4 *)
let rec union l1 l2 = match l1 with
  | [] -> l2
  | t::q when (membre t l2) -> union q l2
  | t::q -> t::(union q l2)
;;

(* Exercice 9 *)

let rec insere x l = match l with
  | [] -> [x]
  | t::q when x<=t -> x::l
  | t::q -> t::(insere x q)
;;

let rec triInsertion l = match l with
  | [] -> []
  | t::q -> insere t (triInsertion q)
;;

triInsertion [12; 100; 25; 42; 12] ;;

(* Exercice 10 *)

let rec minimum l = match l with
  | [] -> failwith "liste vide"
  | t::[] -> t,[]
  | t::q -> let m,l1 = minimum q in
    if t<m then t,q
    else m,t::l1
;;

let rec triSelection l = match l with
  | [] -> []
  | _ -> let m,q = minimum l in
    m::triSelection q
;;

triSelection [12; 100; 25; 42; 12] ;;

(* Exercice 11 *)

let rec triBulle l =
  let rec aux l = match l with
    | x::y::q when x>y -> y::(aux (x::q))
    | x::y::q -> x::(aux (y::q))
    | _ -> l
  in
  let l' = aux l in
  if l=l' then l
  else triBulle l'
;;

triBulle [12; 100; 25; 42; 12] ;;