(* Exercice 1 *)

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

(* 2 *)
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
;;

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

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

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

(* Exercice 2 *)

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

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

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

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

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

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

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

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

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

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

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

(* Exercice 8 *)
(* 1 *)
let rec purge l = match l with
  | [] -> []
  | t::q when List.mem t q -> purge q
  | t::q -> t::(purge q)
;;

(* 2 *)
let purge' l =
  let rec aux l l' = match l with
    | [] -> l'
    | t::q when List.mem t l' -> aux q l'
    | t::q -> aux q (t::l')
  in List.rev (aux l [])
;;

(* Exercice 9 *)
(* 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 10 *)

(* 1 *)
let flooredRoot n =
  let rec floorAux n k = match k with
    | k when k*k>n -> k-1
    | _ -> floorAux n (k+1)
  in floorAux n 0
;;

flooredRoot 51 ;;

let flooredRootDicho n =
  let rec aux n i j =
    let k = (i+j)/2 in match i,j with
    (*on maintient l'invariant suivant i*i<=n<j*j*)
    | i,j when i=j-1 -> i
    | i,j when k*k=n -> k
    | i,j when k*k<n -> aux n k j
    | _,_ -> aux n i k
  in aux n 0 (n+1)
;;

flooredRootDicho 50;;

(* Exercice 11 *)

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)
;;

(* Exercice 12 *)

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
;;

(* Exercice 13 *)

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'
;;