(* I Variantes sur les fonctionnalités de base *)
(* I.1 Autour de appartient *)
(* Rappel : une programmation possible de la fonction appartient est *)
let rec appartient (x : 'a) (liste : 'a list) : bool =
  match liste with
  | [] -> false
  | tete :: queue when tete = x -> true
  | _ :: queue -> appartient x queue ;;



appartient 4 [3; 4; 2; 4; 5] ;;
appartient 2 [3; 4; 2; 4; 5] ;;
appartient 1 [3; 4; 2; 4; 5] ;;


(* Une autre version avec utilisation de l'évaluation paresseuse du ||.
Attention à bien expliquer ceci dans votre copie si c'est le choix que vous faites.
Assurez-vous de bien avoir compris la subtilité de cette programmation...*)

let rec appartient2 (x : 'a) (liste : 'a list) : bool =
  match liste with
  | [] -> false
  | tete :: queue -> (tete = x) || appartient2 x queue ;;

appartient2 4 [3; 4; 2; 4; 5] ;;
appartient2 2 [3; 4; 2; 4; 5] ;;
appartient2 1 [3; 4; 2; 4; 5] ;;
  
(* Pour écrire la fonction occurrences, on travaille récursivement sur la queue de la liste. Le cas de base est bien sûr la liste vide qui ne peut pas contenir x.
Pour une liste non vide, soit la tete est x auquel cas le nombre de l'occurrence est 1 + le nombre d'occurrences dans la queue. Soit
ce n'est pas x, auquel le nombre d'occurrence est le même que celui dans la queue.
Attention à bien utiliser une garde pour tester si tete = x !! *)
let rec occurrences  (x : 'a) (liste : 'a list) : int =
  match liste with
  | [] -> 0
  | tete :: queue when tete = x -> 1 + occurrences x queue
  | _ :: queue -> occurrences x queue ;;
  
occurrences 4 [3; 4; 2; 4; 5] ;;
occurrences 2 [3; 4; 2; 4; 5] ;;
occurrences 1 [3; 4; 2; 4; 5] ;;

(* Une version avec un if plutôt qu'une garde *)
let rec occurrences (x : 'a) (liste : 'a list) : int =
  match liste with
  | [] -> 0
  | tete :: queue -> if tete = x
    then 1 + occurrences x liste
    else occurrences x liste;;

(* Une dernière version qui montre que le "if" est une expression qui peut intervenir dans un calcul ! *)
let rec occurrences (x : 'a) (liste : 'a list) : int =
  match liste with
  | [] -> 0
  | tete :: queue -> occurrences x queue + if tete = x then 1 else 0;;

(* Pour la fontion pos_init, le cas de base est bien sûr celui de la liste vide qui ne peut pas contenir x, et donc on lève une exception.
Si la liste n'est pas vide, alors avec un filtrage gardé on regarde si la tête vaut x, auquel cas l'indice à rendre est 0.
Sinon la position de première occurrence est 1 + celle dans la queue de la liste. D'où la fonction suivante *)
let rec pos_init (x : 'a) (liste : 'a list) : int =
  match liste with
  | [] -> failwith "Pas d'occurrence de l'élément"
  | tete :: queue when tete = x -> 0
  | _ :: queue -> 1 + (pos_init x queue) ;;
  
pos_init 4 [3; 4; 2; 4; 5] ;;
pos_init 2 [3; 4; 2; 4; 5] ;;
pos_init 7 [3; 4; 2; 4; 5] ;;

(* ou encore une version avec un if *)
let rec pos_init (x : 'a) (liste : 'a list) : int =
  match liste with
  | [] -> failwith "Pas d'occurrence de l'élément"
  | tete :: queue -> if tete = x
    then 0
    else 1 + (pos_init x queue) ;;

(* Ici il faut ruser pour ne pas lever d'exception et rendre -1 en cas d'absence. Il faut utiliser un compteur interne que l'on passe
lors des appels récursifs. Il faut donc une fonction auxiliaire récursive *)
let pos_init2 (x : 'a) (liste : 'a list) : int =
  let rec pos_init_compteur (x : 'a) (liste : 'a list) (indice : int) : int =
  match liste with
  | [] -> -1
  | tete :: queue when tete = x -> indice
  | _ :: queue -> pos_init_compteur x queue (indice + 1)
  in pos_init_compteur x liste 0 ;;

pos_init2 4 [3; 4; 2; 4; 5] ;;
pos_init2 2 [3; 4; 2; 4; 5] ;;
pos_init2 1 [3; 4; 2; 4; 5] ;;

(* Une version avec vérification initiale de la présence de l'élément (d'après une suggestion de John) *)
let pos_init3 (x : 'a) (liste : 'a list) : int =
  if not (List.mem x liste) then -1 else pos_init x liste;;

pos_init3 4 [3; 4; 2; 4; 5] ;;
pos_init3 2 [3; 4; 2; 4; 5] ;;
pos_init3 1 [3; 4; 2; 4; 5] ;;

(* Proposition de fonction liste des indices des positions d'un élément dans une liste *)
let list_pos (x : 'a) (liste : 'a list) : int list =
  let rec list_pos_aux x liste indice =
    match liste with
    | [] -> []
    | t :: q when t = x -> indice :: (list_pos_aux x q (indice + 1))
    | _ :: q -> list_pos_aux x q (indice + 1) 
   in list_pos_aux x liste 0;;
list_pos 4 [3; 4; 2; 4; 5] ;;
list_pos 2 [3; 4; 2; 4; 5] ;;
list_pos 1 [3; 4; 2; 4; 5] ;;
list_pos 3 [3; 4; 2; 4; 5] ;;

(* Une version sans garde *)
let list_pos2 (x : 'a) (liste : 'a list) : int list =
  let rec list_pos_aux x liste indice =
    match liste with
    | [] -> []
    | t :: q -> let liste_inter = list_pos_aux x q (indice + 1) in
                if t = x then indice :: liste_inter else liste_inter
   in list_pos_aux x liste 0;;

list_pos2 4 [3; 4; 2; 4; 5] ;;
list_pos2 2 [3; 4; 2; 4; 5] ;;
list_pos2 1 [3; 4; 2; 4; 5] ;;
list_pos2 3 [3; 4; 2; 4; 5] ;;

(* I.2 Autour de dernier *)
(* Rappel une programmation possible de dernier est : *)
let rec dernier (liste : 'a list) : 'a =
  match liste with
  | [] -> failwith "Liste vide ! Pas de dernier element"
  | [a] -> a 
  | _ :: queue -> dernier queue ;;

dernier [3; 4; 2; 4; 5] ;;
dernier [3; 4; 2; 4] ;;
dernier [3] ;;
dernier [] ;;

(* Pour avant_dernier, les cas de base sont la liste vide qui n'a pas de dernier élément (on lève une exception) et la liste à un élément, qui est son dernier élément.
Sinon la liste a au moins deux éléments, et le dernier est celui de la queue *)
  
let rec avant_dernier (liste : 'a list) : 'a =
  match liste with
  | [] -> failwith "Liste vide ! Pas d'avant dernier element"
  | [a] ->  failwith "Liste a un element ! Pas d'avant dernier element"
  | a :: b :: [] -> a (* Ou alors [a; b] ou encore [a; _] *)
  | a :: b :: queue -> avant_dernier (b :: queue) ;;

avant_dernier [3; 4; 2; 4; 5] ;;
avant_dernier [3; 4; 2; 4] ;;
avant_dernier [3] ;;
avant_dernier [] ;;

(* I.3 Somme des éléments d'une liste. Aucune difficulté particulière a priori *)
let rec somme (liste : 'int list) : 'int =
  match liste with
  | [] -> 0
  | tete :: queue -> tete + somme queue ;;
  
somme  [3; 4; 2; 4; 5] ;;
somme  [3] ;;
somme  [] ;;

(* I.4 Propriétés logiques sur une liste *)
(* C'est l'occasion d'utiliser l'évaluation paresseuse. *)
(* Pour la fonction exists, le cas de base est celui de la liste vide, qui ne peut contenir un élément vérifiant la propriété et qui donc rend false.
Si la liste n'est pas vide, on vérifie si la propriété est satisfaite par le premier élément. Caml arrêtra
les appels récursifs grâce à l'évaluation paresseuse et rendra un résultat. Sinon, il y aura appel
récursif sur la queue pour voir si on y trouve un élément satisfaisant la propriété*)
let rec exists (propriete : 'a -> bool) (liste : 'a list) : bool =
  match liste with
  | [] -> false
  | tete :: queue -> propriete tete || exists propriete queue ;;

(* Ici le cas de base est différent. Dans la liste vide tous les éléments vérifient la propriété...
Dans les appels récursifs on ira au bout de la récursion si tous les éléments  satisfont la propriété
mais on s'arrêtera grâce à l'évaluation paresseuse dès qu'un élément ne satisfera pas la propritété *)  
let rec for_all (propriete : 'a -> bool) (liste : 'a list) : bool =
  match liste with
  | [] -> true
  | tete :: queue -> propriete tete && exists propriete queue ;;

let rec myst (propriete : 'a -> bool) (liste : 'a list) : bool =
  match liste with
  | [] -> []
  | tete :: queue when propriete tete -> tete :: (myst propriete queue)
  | _ :: queue -> myst propriete queue ;;
(* L'analyse du code montre dans un premier que cette fonction doit renvoyer une liste constituée
de certains éléments de la liste initiale. Il est clair qu'un élément ne sera mis dans la liste
renvoyée que si il vérifie la propriété passée en paramètre. La fonction renvoie donc la liste des éléments de la liste initiale
qui satisfont la propriété, dans le même ordre que dans la liste initiale *)

(* I.5 Ajout en fin de liste *)
(* Le cas de base est bien sûr celui de la liste vide pour lequel le résultat est évident *)
(* Si la liste n'est pas vide elle a donc un élément de tête, qu'il suffit de remettre en tête 
de la liste obtenue lors de l'ajout en dernière position de x à la queue de la liste.
Cette programmation permet de garder une complexité linéaire en la taille de la liste initiale. La preuve a été faite en TD *)
let rec ajout_fin (liste : 'a list) (x : 'a) : 'a list =
  match liste with
  | [] -> [x]
  | tete :: queue -> tete :: ajout_fin queue x ;;
  
ajout_fin [] 1 ;;
ajout_fin  [4; 5; 3] 1 ;;

(* La programmation suivante est non récursive et est également linéaire en la taille de la liste initiale.*)
let ajout_fin2 (liste : 'a list) (x : 'a) : 'a list =
  liste @ [x] ;;

ajout_fin2 [] 1 ;;
ajout_fin2  [4; 5; 3] 1 ;;

(* I.6 Travail sur deux éléments successifs *)
(* Cet exercice est l'occasion d'avoir un filtrage avec des listes ayant au moins deux éléments *)
(* Les cas de bases sont la liste vide et la liste à un élément pour lesquels la réponse est false *)
(* Sinon il y a au moins deux éléments. En utilisant une garde on peut savoir si les deux premiers
éléments sont égaux ou pas et agir en conséquence *)
let rec deux_consec (liste : 'a list): bool =
  match liste with
  | [] | [_] -> false
  | a :: b :: queue when a = b -> true
  | _ :: b :: queue -> deux_consec (b :: queue) ;;

deux_consec [] ;;
deux_consec [1] ;;
deux_consec [1; 1] ;;
deux_consec [1; 2] ;;
deux_consec [1; 2; 3; 4; 5; 6] ;;
deux_consec [1; 2; 3; 4; 4; 6] ;;

(* Une autre version plus synthétique dans laquelle on regroupe les deux cas de bases en un seul
et pour laquelle on utilise l'évaluation paresseuse plutôt qu'une garde *)
(* Cette version n'est pour autant pas meilleure (en particulier pour la lisibilité) que la précédente *)
let rec deux_consec2 (liste : 'a list): bool =
  match liste with
  | [] | [_] -> false
  | a :: b :: queue -> a = b || deux_consec2 (b :: queue) ;;

deux_consec2 [] ;;
deux_consec2 [1] ;;
deux_consec2 [1; 1] ;;
deux_consec2 [1; 2] ;;
deux_consec2 [1; 2; 3; 4; 5; 6] ;;
deux_consec2 [1; 2; 3; 4; 4; 6] ;;

(* II Manipulation sur les éléments *)
(* II.1 Supression et insertion *)
(* supprimer_tout : le cas de base est celui de la liste vide qui ne peut pas contenir l'objet x. Dans ce cas
on rend bien sûr la liste vide *)
(* Sinon la liste a au moins un élément. Si c'est x on renvoie la queue de la liste, nettoyée
des éléments valant x par un appel récurif. Si ce n'est pas x on renvoie la liste ayant x en tête
et pour queue la queue nettoyée des éléments valant x par appel récursif.
Il est important de comprendre qu'il est inutile de mettre x dans le motif car c'est précisément juste
un motif (i.e. une nouvelle liaision locale qui écraserait le x reçu en paramètre) !
Il faut enfin se convaincre qu'en procédant ainsi l'ordre est bien conservé *)
let rec supprimer_tous (x : 'a) (liste : 'a list) =
  match liste with  
  | [] ->  []
  | tete :: queue when tete = x -> supprimer_tous x queue
  | tete :: queue -> tete :: (supprimer_tous x queue) ;;

supprimer_tous 1 [] ;;
supprimer_tous 1 [1] ;;
supprimer_tous 1 [2] ;;
supprimer_tous 1 [2; 3; 1; 4; 1; 5] ;;
supprimer_tous 1 [2; 3; 6; 4; 7; 5] ;;

(* supprimer : il faut bien analyser la récursivité. La liste tete :: queue dont a ôté le
k-ième élément est la liste queue si k = 0, et si non la liste tete :: queue' dans laquelle
queue' est la liste queue dont on a ôté le k-1 ième élément. Il y a également le cas de base où la liste
reçue est la liste vide et dont on ne peut bien sûr enlever aucun élément : dans ce cas on rend
la liste vide *)
let rec supprimer k liste = 
  match k, liste with
  | _, [] ->  []
  | 0, tete :: queue -> queue
  | _, tete :: queue -> tete :: (supprimer (k - 1) queue ) ;;

supprimer 2 [] ;;
supprimer 0 [1] ;;
supprimer 2 [1] ;;
supprimer 2 [1; 3; 5] ;;
supprimer 4 [1; 3; 5] ;;

(* Remarque : on peut se contenter de faire un filtrage sur k, et calculer la tête et la queue de
la liste à l'aide des fonctions hd et tl, comme dans la proposition suivante.
On y perd cependant un peu en lisibilité du code *)
let rec supprimer2 k liste = 
  match k with
  | _ when liste =  [] ->  []
  | 0 -> List.tl liste
  | _ -> (List.hd liste) :: (supprimer (k - 1) (List.tl liste)) ;;

supprimer2 2 [] ;;
supprimer2 0 [1] ;;
supprimer2 2 [1] ;;
supprimer2 2 [1; 3; 5] ;;
supprimer2 4 [1; 3; 5] ;;


(* insérer : le cas de base est celui où k = 0 car on peut toujours insérer x en tête de la liste,
même si elle est vide. Si la liste passée est la liste vide on ne peut en revanche insérer que 
en position 0, ce qui aura été traité dans le cas de base précédent. Si k >0 et que la liste est vide
il faut lever une exception. Si on a passé ces deux cas, c'est que k > 0 et que la liste est de la forme
tete :: queue. On rend alors la liste avec le même premier élément (tete) et pour queue la liste
queue dans laquelle on a inséré en position k-1 l'objet x.  On choisit ici de filtrer sur le couple
k, liste pour plus de lisibilité*)

let rec inserer x k liste =
  match k, liste with
  | 0, _ -> x :: liste
  | _, [] -> failwith "Insertion impossible"
  | _, tete :: queue -> tete :: (inserer x (k - 1) queue) ;;

inserer 5 0 [] ;;
inserer 5 1 [] ;;
inserer 5 0 [4; 3; 2; 1] ;;
inserer 5 3 [4; 3; 2; 1] ;;
inserer 5 4 [4; 3; 2; 1] ;;
inserer 5 5 [4; 3; 2; 1] ;;


(* III Manipulations globales de listes *)
(* III.1 Miroir *)
(* Première version avec concaténation : il suffit de rajouter par concaténation la tete de la liste 
en fin de la liste obtenue par renversement de la queue. Le cas de base est bien sûr la liste vide *)
let rec miroir (liste : 'a list) : 'a list =
  match liste with
  | [] -> []
  | tete :: queue -> (miroir queue) @ [tete] ;;

miroir [] ;;
miroir [1] ;;
miroir [1; 2] ;;
miroir [1; 2; 3; 4; 5; 6; 7; 8] ;;

(* Cette implémentation est malheureusement de complexité quadratique. En effet le coût c_n pour un appel
avec une liste de taille n est telle que c_0 = 1 et c_n = c_(n-1) + n - 1. Le c_(n-1) vient de l'appel
à miroir queue et le n - 1 de l'appel à @ avec comme premier argument une liste de taille n - 1. On vérifie
facilement qu'alors c_n =O(n^2) (écrire les coûts c0 =, c1=, ... cn =  et sommer les égalités ainsi obtenues *)

(* Version linéaire sans concaténation : il faut utiliser un accumulateur dans lequel on construit
la liste résultat au fur et à mesure des appels récursifs. Il faut alors une fonction auxiliaire
récursive qui prend en paramètre cet accumulateur. La fonction miroir elle-même n'a plus besoin d'être
récursive. *)
let miroir2 (liste : 'a list) : 'a list =
  let rec miroir2_aux liste accumulateur =
    match liste with
    | [] -> accumulateur
    | tete :: queue -> miroir2_aux queue (tete :: accumulateur)
  in
  miroir2_aux liste [] ;;

miroir2 [] ;;
miroir2 [1] ;;
miroir2 [1; 2] ;;
miroir2 [1; 2; 3; 4; 5; 6; 7; 8] ;;

(* L'idée est que par filtrage et appel récursif on rencontre les éléments de la liste initiale par position croissante.
Comme on les ajoute en tête de l'accumulateur ils vont y figurer en sens inverse. Vérifier que maintenant on a bien une complexité linéaire.

Enfin on peut noter que dans la fonction miroir2_accu  le dernier calcul fait est précisément l'appel récursif : dans ce 
cas on dit que la fonction est récursive terminale, notion que nous etudierons dans le prochain chapitre et qui présente
certains avantages *)

(* III.2 Couper *)
(* Les cas de bases sont les liste à 0 ou 1 élément, auquel cas on peut rendre le couple (liste, []) qui satisfait 
le cahier des charges. Sinon c'est que la liste a au moins deux éléments. On met le premier dans le premier membre
du couple calculé à partir de la queue (liste sans les deux premiers termes) et le second dans le second membre du couple
calculé à partir de la queue. Techniquement on utilise une liaison locale pour éviter d'appeler deux fois récursivement
la fonction sur la queue et qui déconstruit le couple renvoyé *)
let rec couper liste =
  match liste with
  | [] | [_] -> (liste, [])
  | a :: b :: queue -> let (inter1, inter2) = couper queue
                       in (a :: inter1, b :: inter2) ;;

couper [] ;; 
couper [1] ;;                   
couper [1; 2] ;; 
couper [1; 2; 3] ;; 
couper [1; 2; 3; 4; 5; 6; 7; 8; 9; 10] ;; 

                       
(* III.3 Extraction *)
(* L'idée est de faire que la coupure au ième élément de la liste tete :: queue 
est la même que celle au i-1 ième élément de la liste queue, en pensant bien à rajouter
l'élément tete en tête du premier membre du couple rendue pour la coupure de queue.
Attention à la façon dont le paramètre est passé : on peut retraduire le cahier des charges en disant
que la fonction rend un couple dont le premier membre est constitué des i premiers termes de la liste, et le second
membre du reste de la liste. Par définition i est donc nécessairement strictement positif.
Comme premier cas de base il y a la situation où la liste passée est vide ce qui doit lever une exception.
Si la liste n'est pas vide, alors la réponse pour i = 1 est très simple et si i>1 on procède récursivement *)
let rec partage liste i =
  match liste, i with
  | [], _ -> failwith "Coupure impossible"
  | tete :: queue, 1 -> ([tete], queue)
  | tete :: queue, _ -> let (inter1, inter2) = partage queue (i - 1)
                        in (tete :: inter1, inter2) ;;

partage [] 1 ;;
partage [] 2 ;;
partage [1] 1 ;;
partage [1; 2] 1 ;;
partage [1] 2 ;;
partage [1; 2; 3] 2 ;;
partage [1; 2; 3; 4; 5; 6; 7; 8; 9; 10] 7 ;;

(* IV Mise à plat *)  
let rec mise_a_plat (lliste : 'a list list) : 'a list =
  match lliste with
  | [] -> []
  | t :: q -> t @ mise_a_plat q ;;
  
(* V Approche ensembliste *)
(* V.1 Préfixes 
On étudie les réponses pour des listes courtes pour découvrir le processus récursif
[] -> [[]]
[1] -> [[1]]
[1; 2] -> [[1]; [1; 2]] ce qui peut se lire comme le rajout de la liste complète à la liste des préfixes calculée sur la liste privée de son dernier élément. Il en est de même pour les listes plus longues. On a donc trouvé le processus récursif *)

let rec prefixes (liste : 'a list) : 'a list list = 
  match liste with
  | [] -> []
  | _ ->  prefixes (List.rev (List.tl (List.rev liste))) @ [liste] ;; 


prefixes [] ;;
prefixes [1] ;;
prefixes [1; 2] ;;
prefixes [1; 2; 3] ;;
prefixes [1; 2; 3; 4] ;;


(* En termes de complexité on peut déjà remarquer que la liste fabriquée contient n * (n + 1) / 2 termes finaux (i.e. pris parmis les éléments de la liste initiale ), dès lors comme au mieux l'ajout d'un élément à une liste est en O(1) on ne peut pas espérer faire mieux que O(n^2)
Dans notre programmation on a avec les notations habituelles C_0 = 1 pour la liste vide et la relation de récurrence C_n = n + 1 + (n-1) + C_{n-1} + (n - 1)
Explications : le n vient du rev sur la liste initiale, le 1 suivant du List.tl (on a alors une liste de taille (n-1), le (n-1) du rev sur cette liste de taille n-1, le C_{n-1} vient de l'appel récursif sur la liste de taille (n-1). Le retour de cet appel est une liste de taille (n-1), et par l'opération de concaténation on a donc un coût supplémentaire de n-1

Au total ceci montre une complexité en O(n^2).

On peut aussi penser à procéder ainsi : ajouter les éléments en tête (en temps constant), et à renverser enfin la liste finale, d'où le code suivant dont on montre également qu'il a une complexité en O(n^2) *)

let prefixes2 (liste : 'a list) : 'a list list = 
  let rec prefixes_aux liste =
    match liste with
    | [] -> []
    | _ ->  liste :: prefixes_aux (List.rev (List.tl (List.rev liste))) in
  List.rev (prefixes_aux liste) ;;

prefixes2 [] ;;
prefixes2 [1] ;;
prefixes2 [1; 2] ;;
prefixes2 [1; 2; 3] ;;
prefixes2 [1; 2; 3; 4] ;;

(* Troisième version, toujours en O(n^2) mais globalement plus efficace (en gros la constante devant le n^2 est plus petite que dans les deux autres versions), proposée par M.Fortier. On accumule dans le paramètre prev les éléments déjà lus *)
let prefixes3 (liste : 'a list) : 'a list list = 
  let rec prefixes_aux liste prev =
    match liste with
    | [] -> []
    | tete :: queue ->  let p = tete :: prev in
                        (List.rev p) :: prefixes_aux  queue p in
  prefixes_aux liste [] ;;

prefixes3 [] ;;
prefixes3 [1] ;;
prefixes2 [1; 2] ;;
prefixes2 [1; 2; 3] ;;
prefixes2 [1; 2; 3; 4] ;;

(* Test sur une grosse liste ! Ne pas chercher à comprendre les lignes qui suivent. Il s'agit de programmation impérative que nous n'avons pas encore vue... *)
let ref_liste_test = ref [];;
for i = 0 to 10000
do ref_liste_test := i :: !ref_liste_test
done ;;

let liste_test = !ref_liste_test ;;
liste_test ;;

(* Les lignes suivantes comparent les temps d'exécution des différentes versions *)
let compteur = Sys.time() in
 (prefixes liste_test; print_float (Sys.time() -. compteur)) ;;

let compteur = Sys.time() in
 (prefixes2 liste_test; print_float (Sys.time() -. compteur)) ;;

let compteur = Sys.time() in
 (prefixes3 liste_test; print_float (Sys.time() -. compteur)) ;;