(* Ex 1 *)
let liste_entiers n =
   let rec __liste_entiers n acc =

    (* On regarde si l'accumulateur est supérieur à n ou pas *)
      match acc with

        (* Si oui, on ne rappelle pas la fonction et on retourne n-1 *)
          | acc when acc >= n-1 -> [n-1]

          (* Sinon ba on rajoute, au début acc vaut 1 ensuite 2.. et sa forme 1::2::3::4..... *)
          | _ -> acc :: (__liste_entiers (n) (acc+1)); in

    (*
      Et on appelle la fonction, je rappelle que tout était
      caché dans une fonction lol, et bien sûr la complexité c'est O(n)
    *)
    __liste_entiers n 0;;

liste_entiers 20;; (* petit test des familles *)



(* ça c'est juste du bonus *)
let rec longueur l = match l with
   | [] -> 0
   | x::q -> 1+(longueur q);;


(* Ex 2 *)
let rec repetition x n = match n with

    (* Si le n est négatif, on quitte car c'est inadmissible *)
    | n when n < 0 -> failwith "erreur"

    (* Si c'est 0 on renvoie une liste de 1 élément *)
    | 0 -> [x]

    (*
      Sinon on rappelle la fonction en diminuant l'accumulateur
      et bien sûr quand celui vaut zéro on retombe sur le cas ci-dessus donc la fonction se termine
      la complexité c'est O(n)
     *)
    | _ -> x :: (repetition x (n-1));;

repetition 5 10;; (* petit test des familles *)



(* Ex 3 *)
let a = 4::3::2::1::[0];; (* Ceci va nous servir d'exemple pour les 4859 exercices suivants *)
let rec appartient l a = match l with

    (* Si l est vide ba, il est clair que x ne peut pas appartenir donc on renvoie false *)
    | [] -> false

    (* On teste si x=a, si c'est le cas, c'est qu'il appartient donc on renvoie direct true, pas le temps de naiser *)
    | x::q when x=a -> true

    (* Sinon on explore jusqu'a retomber sur le 1er cas dans le cas ou x n'appartient pas *)
    | x::q -> appartient q a;;

appartient a 47;; (* petit test des familles *)


(* Ex 4 *)
let a = 4::3::4::2::1::[0];; (* El famous exemple *)
let rec sans_repetition l = match l with

    (* Si la liste est vide => pas de répétitions donc on renvoie true *)
    | [] -> true

    (*
      Sinon on itère, si on trouve que x appartient à q ça veut dire
      qu'il existe 2 fois donc qu'il y a répétition don on rage quitte
    *)
    | x::q -> if (appartient q x) then false else sans_repetition q;;

sans_repetition a;; (* petit test des familles *)


(* Ex 5 *)
let a = 4::3::4::2::1::[0];;(* El famous example *)
let rec supprime_repetition l = match l with

    (*
      Si la liste est vide => il n'y a pas de répétions donc on quitte et on renvoie l
      la liste vide (on aurait pu mettre l mais c'est juste pour faire propre)
    *)
    | [] -> []

    (* Si x appartient à q, ça veut dire qu'il existe au moins 2 fois donc on le remet pas *)
    | x::q -> if (appartient q x) then (supprime_repetition q) else x::(supprime_repetition q);;

supprime_repetition a;; (* petit test des familles *)


(* Ex 6 *)
(* Je me suis embrouillé moi même, c'est la version non-optimisé avec utilisation d'accumulateur lol *)
let a = 4::3::4::2::1::[0];;
let retirer_un x l =
    if (appartient l x) then
        let rec __retirer_un x l acc =
        match l with
                | [] -> []
                | y::q when x=y -> if acc=true then y::(__retirer_un x q acc) else (__retirer_un x q true)
                | y::q -> y::(__retirer_un x q acc); in (__retirer_un x l false);
    else failwith "x n'appartient pas";;

retirer_un 4 a;; (* petit test des familles *)




(* Ex 7 *)
let a = 4::3::4::2::1::[0];;
let rec retirer_tous x l = match l with

    (* Si la liste est vide on quitte *)
    | [] -> []

    (* Si x=y, on l'enlève *)
    | y::q when x=y -> retirer_tous x q

    (* Sinon on le met *)
    | y::q -> y::(retirer_tous x q);;


retirer_tous 4 a;; (* petit test des familles *)





(* Ex 8 *)
let a = 4::3::4::2::1::[0];;
let rec extraire n l = match n with

    (* Si n est négative, là on rage quitte *)
    | n when n < 0 -> failwith "n invalide"

    (*
      Si n=0, on quitte en renvoyant la liste
      qui est pas forcément la liste l du début, attention c'est récursif
    *)
    | 0 -> l

    (* Sinon on itère jusqu'à ce que n=0, auquel cas on revient au cas du dessus *)
    | _ -> match l with
        (* Si on arrive là, c'est que la valeur de n est trop grande, du coup on rage quitte *)
        | [] -> failwith "n invalide"

        (* Sinon on continue d'explorer la liste est espérer qu'à un moment n soit égal à 0 *)
        | x::q -> if n-1=0 then x::(extraire (n-1) q) else (extraire (n-1) q);;

extraire 3 a;; (* petit test des familles *)



(* Ex 9 *)
let a = 4::3::4::2::1::[0];;
let reperer x l =

    (* Si x appartient, c'est bon *)
    if (appartient l x) then
        let rec __reperer x l = match l with

            (* Si c'est vide, on arrête la récursion *)
            | [] -> []

            (* Sinon on continue d'explorer *)
            | y::q -> if x=y then y::q else (__reperer x q); in (__reperer x l);

    else failwith "x n'appartient pas";; (* sinon on rage quitte *)

reperer 2 a;; (* petit test des familles *)


(* Là c'est quand je m'embrouille xD *)
(*
let inserer n x l =
    let dynamic = ref false in
    let rec __inserer n1 n2 x l =
       if !dynamic=false then
        match n with
                | n when n < 0 -> failwith "n invalide"
                | 0 -> x::l
                | x::q -> match l with
                    | [] -> dynamic := (x,n)
                    | y::q -> if x=y then begin
                                dynamic := (x,n);
                                (__inserer (n-1) n x q);
                                end;
                                else (__inserer (n-1) n x q);
        else
            match l with
                | [] -> []
                | x::q -> if
    ; in( __inserer n x l)
*)




(* Ex 10 *)
let a = 4::3::4::2::1::[0];;
let inserer n x l =
    let rec _inserer n x l acc = match n with

        (* Si n est négtive on rage quitte *)
        | n when n < 0 -> failwith "n invalide"

        (* Si n = 0, ba on rajoute juste l'élément *)
        | 0 -> x::l

        (* Sinon, ba on itère jusqu'à ce qu'on arrive à l'élément n *)
        | _ -> match l with

            (* Si on arrive là, c'est que la valeur de n est trop grande, du coup on rage quitte *)
            | [] -> failwith "Sorry, length of the list too small"

            (* Sinon on explore tout en constuisant notre liste au fur et à mesure *)
            | h::q -> if n!=acc then h::(inserer n x q (acc+1)) else x::h::q;

    (* et on oublie pas d'appeler la fonction *)
    in _inserer n x l 0;;



inserer 3 999 a;; (* petit test des familles *)



(* Ex 11 *)
let rec sous_mot m l = match m,l with (* double filtrage *)

    (* [] = [] donc on renvoie true *)
    | [],[] -> true

    (* x::q != [] donc on renvoie faux *)
    | x::q,[] -> false

    (* [] != x::q donc on renvoie faux *)
    | [],x::q -> false

    (* On teste si x=y, si oui on continue d'explorer sinon on renvoie faux *)
    | x::q,y::h -> if x=y then sous_mot q h else false;;

(* petit test des familles *)
  sous_mot (1::2::3::4::[5]) (1::2::3::4::[5]);;  (* true *)
  sous_mot (1::2::3::4::[5]) (1::2::9875::4::[5]);; (* false *)



(* Ex 12 *)
let a = 4::3::4::2::1::[0];;
let mirroir l =

    (*
      l : la liste a inversé
      g : la liste inversée
     *)
    let rec _mirroir l g = match l with

        (*
          Si on arrive là,
          c'est qu'on est arrivé au bout de la liste l,
          du coup en renvoie g qui contient la liste l inversée
        *)
        | [] -> g

        (* on rappelle la fonction en stockant la valeur dans l'accumulateur *)
        | x::q -> _mirroir q (x::g); in

        (* Voici ce qu'il se passe pour la liste 1::2::[3]

             - ETAPE 1 : g = []
             - ETAPE 2 : g = [1]
             - ETAPE 3 : g = 2::[1] (car on fait x::g, ici x = 2 et g = [1])
             - ETAPE 4 : g = 3::2::[1]  (car on fait x::g, ici x = 3 et g = 2::[1])
             - ETAPE 5 : l est vide donc on renvoie g
         *)


    _mirroir l [];; (* On appelle la fonction avec un accumulateur vide (une liste vide) *)
    (* Fin de la fonction ici ;) *)


mirroir a;; (* petit test des familles *)




(* Ex 13 *)
let a = 1::2::3::[4];;
let b = 5::6::7::8::9::[10];;
let rec concat m l = match m with

    (*
      Si la liste m est vide, c'est qu'on la ajouté,
      maintenant on teste si l=[],
        Si oui ba on a fini donc on arrête et on quitte
        Sinon on inverse l et m, comme m est déjà vide,
        on l'indique explicitement, pour une meilleure lecture
    *)
    | [] -> if l=[] then [] else concat l []

    (* On ajoute tranquillement une après l'autre chaque valeur *)
    | x::q -> x::(concat q l);;


concat a b;; (* et le teste qui va avec bien sûr *)


(* Ex 14 *)
let a = 4::3::4::2::1::[0];;
let f x = x*x;; (* notre fonction *)
let rec parcours l f = match l with

    (* Si la liste est vide on quitte *)
    | [] -> []

    (* Sinon on remplace chaque valeur x par f x *)
    | x::q -> (f x)::(parcours q f);;

(* le test *)
parcours a f;;



(* Ex 15 *)
let a = 4::3::4::2::1::[0];;
let f x = x*x;; (* notre fonction *)
let parcours_envers l f =
    let rec _parcours_envers l f acc = match l with

        (* Si la liste est vide, on renvoie la liste inversée contenu dans acc *)
        | [] -> acc

        (* Sinon on explore tout en ajoutant dans l'accumulateur f x *)
        | x::q -> _parcours_envers q (f) ((f x)::acc); in _parcours_envers l (f) [];;

parcours_envers a f;; (* El Famous Test *)





(* Ex 16 *)

(* Voici une liste de liste *)
(* je rappelle que ceci est équivalent :
    - let a = 1::2::[3];;
    - let a = [1; 2; 3];;
   du coup on va se servir de ces 2 syntaxes pour avoir quelque chose d'agréable au niveau visuel *)

let a = [1::2::[3]; 4::5::[6]; 7::8::[9]];;
(*
  correspond à ceci : [[1; 2; 3]; [4; 5; 6]; [7; 8; 9]]
  et bien sûr pour accéder à l'élément 3 de la 2ème liste, il faut faire une double récursion mdr
*)

(* maintenant qu'on posait les bases, on y va *)
let aplatir l =

    (* on déclare 2 fonctions récrusive *)
    (* et on va utiliser un accumulateur pour sotcker succesivement la double récursion *)

    (* 1ère récursion, on itère de liste en liste *)
    let rec _aplatir l acc  = match l with
        | [] -> acc
        | x::q -> _aplatir q (_concat acc x);

    (* 2ème récursion imbriqué dans la 1ère, on itère de int en int *)
    (* cette fonction permet de concatener de liste (plus de détail Exercice 13 *)
    and _concat m l = match m with
        | [] -> if l=[] then [] else _concat l []
        | x::q -> x::(_concat q l);

    (* plus qu'à appeler tranquillement notre fonction aplatir ;) avec l'accumulateur vide *)
    in _aplatir l [];;

(* et on teste :D *)
aplatir a;;
(*
on obtients bien                          : 1::2::3::4::5::6::7::8::[9]
ou suivant la syntaxe que vous préférez   : [1; 2; 3; 4; 5; 6; 7; 8; 9]   (* équivalent *)
*)





(* Ex 17 *)

(* la liste est sous la forme : *)
let a = [(1,2); (3,4); (5,6)];;

let separe l =
    let rec _separe l acc1 acc2 = match l with

        (* Si la liste est vide, c'est qu'on terminé du coup on renvoie acc1 et acc2 dans une liste *)
        | [] -> [acc1; acc2]

        (* Sinon on explore en mettant d'un côté la 1ère composante et de l'autre la 2ème composante *)
        | x::q -> _separe q (acc1@[(fst x)]) (acc2@[(snd x)]);

    in _separe l [] [];;

(* le mega teste de malade -----> *)
separe a;; (* output: [[1; 3; 5]; [2; 4; 6]] *)





(* Ex 18 *)
let create_pile = [];; (* trop dure, je me suis fait mal *)

let append_pile l x = x::l;; (* beaucoup trop dure cette exo, limite c'est impossible en fait *)

let pop_pile l = match l with | [] -> [] | x::q -> q;; (* nan mais là, même moi j'ai du mal *)

let isEmpty_pile l = if l=[] then true else false;; (* je viens de perdre un bras *)


(* le mega test *)
let ma_pile = create_pile;;
isEmpty_pile ma_pile;;
let ma_pile = append_pile ma_pile 1;;
let ma_pile = append_pile ma_pile 2;;
let ma_pile = append_pile ma_pile 3;;
let ma_pile = pop_pile ma_pile;;
let ma_pile = pop_pile ma_pile;;
isEmpty_pile ma_pile;;





(* Ex 19 *)
let create_file = [];; (* ça y est, je pourrais plus jamais nager, quoique il me reste mes jambes *)

let append_file l x = x::l;; (* woooooow chaud *)

(* enfin un petit challenge *)
let rec pop_file l = match l with
    | [] -> []
    | [x] -> []
    | x::q -> x::(pop_file q);;

let isEmpty_file l = if l=[] then true else false;; (* je viens de perdre une jambe *)


(* le mega test *)
let ma_file = create_file;;
isEmpty_file ma_file;;
let ma_file = append_file ma_file 1;;
let ma_file = append_file ma_file 2;;
let ma_file = append_file ma_file 3;;
let ma_file = pop_file ma_file;;
let ma_file = pop_file ma_file;;
isEmpty_file ma_file;;