(* ==================================================================
   Cours 3 : La monade Liste et les listes en compréhension
   ================================================================== *)

(* ==================================================================
   Partie 1 : La monade Liste
   ================================================================== *)

(* --- Les deux opérations de la monade --- *)

(* return : 'a -> 'a list *)
let return x = [x]

(* bind : 'a list -> ('a -> 'b list) -> 'b list
   aussi appelé flat_map ou concat_map *)
let (>>=) m f = List.concat (List.map f m)

(* join : 'a list list -> 'a list *)
let join m = m >>= (fun x -> x)

(* --- Vérification des lois de la monade --- *)

(* 1. return x >>= f  =  f x *)
(* 2. m >>= return    =  m *)
(* 3. (m >>= f) >>= g =  m >>= (fun x -> f x >>= g) *)

let loi1 x f = (return x >>= f) = f x
let loi2 m = (m >>= return) = m
let loi3 m f g = ((m >>= f) >>= g) = (m >>= fun x -> f x >>= g)

(* --- Exemples fondamentaux --- *)

(* 1. Produit cartésien de deux listes *)
let cartesian xs ys =
  xs >>= fun x ->
  ys >>= fun y ->
  return (x, y)
(* cartesian [1; 2; 3] ["a"; "b"] =
   [(1,"a"); (1,"b"); (2,"a"); (2,"b"); (3,"a"); (3,"b")] *)

(* 2. Triplets pythagoriciens : a² + b² = c², avec a,b,c ≤ n *)
let range n = List.init n (fun i -> i + 1)

let pythagore n =
  range n >>= fun a ->
  range n >>= fun b ->
  range n >>= fun c ->
  if a * a + b * b = c * c then return (a, b, c) else []
(* pythagore 15 = [(3,4,5); (4,3,5); (5,12,13); (6,8,10); (8,6,10); (9,12,15); (12,5,13); (12,9,15)] *)

(* 3. Toutes les paires (i,j) avec somme ≤ n *)
let paires_somme n =
  range n >>= fun i ->
  range n >>= fun j ->
  if i + j <= n then return (i, j) else []
(* paires_somme 3 = [(1,1); (1,2); (2,1)] *)

(* 4. Toutes les parties d'une liste (ensemble des sous-listes) *)
let rec parties = function
  | [] -> [[]]
  | x :: xs ->
    parties xs >>= fun p ->
    [p; x :: p]
(* parties [1; 2; 3] = [[]; [1]; [2]; [1;2]; [3]; [1;3]; [2;3]; [1;2;3]] *)

(* 5. Toutes les combinaisons de k éléments parmi une liste *)
let rec combinaisons k = function
  | _ when k = 0 -> [[]]
  | [] -> []
  | x :: xs ->
    (combinaisons (k - 1) xs >>= fun c -> return (x :: c))
    @ combinaisons k xs
(* combinaisons 2 [1; 2; 3; 4] = [[1;2]; [1;3]; [1;4]; [2;3]; [2;4]; [3;4]] *)

(* 6. Décomposition additive : toutes les façons d'écrire n comme somme *)
let rec partitions_entieres n =
  if n = 0 then [[]]
  else
    range n >>= fun k ->
    partitions_entieres (n - k) >>= fun p ->
    if List.for_all ((<=) k) p then return (k :: p) else []
(* partitions_entieres 4 = [[1;1;1;1]; [1;1;2]; [1;3]; [2;2]; [4]] *)

(* --- Exemple 7 : Chemins dans un graphe orienté --- *)

(* Un graphe est une liste d'arêtes : (départ, arrivée) *)
type graphe = (string * string) list

let graphe_exemple : graphe =
  [("A", "B"); ("A", "C"); ("B", "D"); ("B", "E"); ("C", "E"); ("D", "F"); ("E", "F")]

(* Voisins directs d'un nœud *)
let voisins graphe noeud =
  List.filter (fun (a, _) -> a = noeud) graphe >>= fun (_, b) -> return b

(* Tous les chemins de depart vers arrivee (sans cycles) *)
let rec chemins graphe depart arrivee =
  let rec aux courant visite =
    if courant = arrivee then return [courant]
    else if List.mem courant visite then []
    else
      voisins graphe courant >>= fun suivant ->
      aux suivant (courant :: visite) >>= fun chemin ->
      return (courant :: chemin)
  in
  aux depart []
(* chemins graphe_exemple "A" "F" =
   [["A"; "B"; "D"; "F"]; ["A"; "B"; "E"; "F"]; ["A"; "C"; "E"; "F"]] *)

(* --- Exemple 8 : mini-IA au taquin (Tic-Tac-Toe) --- *)

type joueur = X | O
type case = Vide | J of joueur
type plateau = case list  (* 9 cases en ligne *)

let plateau_vide = List.init 9 (fun _ -> Vide)

(* Coups possibles : cases vides *)
let coups_possibles plateau =
  let indices = List.init 9 (fun i -> i) in
  indices >>= fun i ->
  match List.nth plateau i with
  | Vide -> return i
  | _ -> []

(* Appliquer un coup *)
let jouer plateau i joueur =
  List.mapi (fun j c -> if j = i then J joueur else c) plateau

(* Triple gagnant ? *)
let alignements_gagnants =
  [[0; 1; 2]; [3; 4; 5]; [6; 7; 8];  (* lignes *)
   [0; 3; 6]; [1; 4; 7]; [2; 5; 8];  (* colonnes *)
   [0; 4; 8]; [2; 4; 6]]             (* diagonales *)

let est_gagnant plateau joueur =
  List.exists (fun alig ->
    List.for_all (fun i -> List.nth plateau i = J joueur) alig
  ) alignements_gagnants

(* Jouer tous les coups possibles à partir d'une position *)
let tous_les_coups plateau joueur =
  coups_possibles plateau >>= fun i ->
  return (jouer plateau i joueur)

(* Évaluer un coup : jouer et basculer le joueur *)
let rec jouer_tous_coups plateau joueur =
  let adversaire = match joueur with X -> O | O -> X in
  let suivant = tous_les_coups plateau joueur in
  if est_gagnant plateau joueur then [plateau]
  else if coups_possibles plateau = [] then [plateau]
  else suivant >>= fun p -> jouer_tous_coups p adversaire
(* jouer_tous_coups plateau_vide X : explore tout l'arbre de jeu *)


(* ==================================================================
   Partie 2 : Listes en compréhension comme langage de requête
   ================================================================== *)

(* On représente une table par :
     - une ligne d'en-tête (liste de noms de colonnes)
     - une liste de lignes (chaque ligne est une liste de chaînes) *)
type table = { entete : string list; lignes : string list list }

(* --- Affichage d'une table --- *)
let affiche_table t =
  Printf.printf "| %s |\n" (String.concat " | " t.entete);
  Printf.printf "|-%s-|\n" (String.concat "-+-" (List.map (fun _ -> String.make 10 '-') t.entete));
  List.iter (fun ligne ->
    Printf.printf "| %s |\n" (String.concat " | " ligne)
  ) t.lignes

(* --- Données d'exemple : employés --- *)
let employes : table = {
  entete = ["Nom"; "Age"; "Ville"; "Salaire"];
  lignes = [
    ["Alice";  "25"; "Paris";   "45000"];
    ["Bob";    "30"; "Lyon";    "52000"];
    ["Charlie";"22"; "Paris";   "38000"];
    ["Diane";  "35"; "Marseille";"60000"];
    ["Eve";    "28"; "Lyon";    "47000"];
    ["Franck"; "40"; "Paris";   "55000"];
    ["Grace";  "32"; "Toulouse";"49000"];
    ["Hugo";   "27"; "Marseille";"42000"];
  ]
}

(* --- Fonctions utilitaires --- *)

(* Indice d'une colonne par son nom *)
let colonne_idx table nom =
  let rec chercher i = function
    | [] -> failwith ("Colonne introuvable : " ^ nom)
    | x :: _ when x = nom -> i
    | _ :: xs -> chercher (i + 1) xs
  in
  chercher 0 table.entete

(* Valeur d'une colonne pour une ligne *)
let valeur table ligne nom =
  List.nth ligne (colonne_idx table nom)

(* Parse un entier depuis une chaîne *)
let int_of_string_opt s =
  try Some (int_of_string s) with Failure _ -> None

(* --- Requêtes avec la monade Liste --- *)

(* SELECT : projeter sur certaines colonnes *)
let select table noms =
  let indices = List.map (colonne_idx table) noms in
  let entete = noms in
  let lignes =
    table.lignes >>= fun ligne ->
    [List.map (fun i -> List.nth ligne i) indices]
  in
  { entete; lignes }
(* select employes ["Nom"; "Ville"] =
   { entete = ["Nom"; "Ville"];
     lignes = [["Alice";"Paris"]; ["Bob";"Lyon"]; ["Charlie";"Paris"];
               ["Diane";"Marseille"]; ["Eve";"Lyon"]; ["Franck";"Paris"];
               ["Grace";"Toulouse"]; ["Hugo";"Marseille"]] } *)

(* WHERE : filtrer les lignes selon un prédicat *)
let where table pred =
  { table with
    lignes = table.lignes >>= fun ligne ->
             if pred ligne then [ligne] else [] }
(* where employes (fun l -> int_of_string (valeur employes l "Age") > 30) =
   { entete = [...]; lignes = [["Diane";35;...]; ["Franck";40;...]; ["Grace";32;...]] } *)

(* SELECT combiné à WHERE : les deux en une passe *)
let select_where table noms pred =
  let indices = List.map (colonne_idx table) noms in
  let entete = noms in
  let lignes =
    table.lignes >>= fun ligne ->
    if not (pred ligne) then []
    else [List.map (fun i -> List.nth ligne i) indices]
  in
  { entete; lignes }

(* --- Requêtes prédéfinies --- *)

(* Q1 : Noms et salaires des employés de Paris *)
let q1 =
  let parisiens = where employes (fun l -> valeur employes l "Ville" = "Paris") in
  select parisiens ["Nom"; "Salaire"]
(* Resultat :
   | Nom     | Salaire |
   |---------+---------|
   | Alice   | 45000   |
   | Charlie | 38000   |
   | Franck  | 55000   | *)

(* Q2 : Employés ≥ 30 ans (nom, age, ville) *)
let q2 = select_where employes ["Nom"; "Age"; "Ville"]
           (fun l -> int_of_string (valeur employes l "Age") >= 30)

(* Q3 : Salaire moyen par ville *)
let salaire_moyen_par_ville table =
  (* liste des villes distinctes *)
  let villes =
    List.sort_uniq compare (List.map (fun l -> valeur table l "Ville") table.lignes)
  in
  villes >>= fun v ->
  let (total, count) =
    List.fold_left (fun (s, c) l ->
      if valeur table l "Ville" = v then
        (s + int_of_string (valeur table l "Salaire"), c + 1)
      else (s, c)
    ) (0, 0) table.lignes
  in
  return (v, string_of_int (total / count))
(* salaire_moyen_par_ville employes =
   [("Lyon", "49500"); ("Marseille", "51000"); ("Paris", "46000"); ("Toulouse", "49000")] *)

(* --- Q4 : Jointure de deux tables --- *)

(* Deuxième table : départements *)
let depts : table = {
  entete = ["Ville"; "Departement"; "Region"];
  lignes = [
    ["Paris";     "75"; "Ile-de-France"];
    ["Lyon";      "69"; "Auvergne-Rhone-Alpes"];
    ["Marseille"; "13"; "Provence-Alpes-Cote-d-Azur"];
    ["Toulouse";  "31"; "Occitanie"];
  ]
}

(* Jointure naturelle sur la colonne Ville *)
let jointure_ville t1 t2 =
  let new_entete = t1.entete @ List.filter (fun c -> not (List.mem c t1.entete)) t2.entete in
  let colonnes_t2 = List.filter (fun c -> not (List.mem c t1.entete)) t2.entete in
  let idx_t2 = List.map (colonne_idx t2) colonnes_t2 in
  let new_lignes =
    t1.lignes >>= fun l1 ->
    t2.lignes >>= fun l2 ->
    if valeur t1 l1 "Ville" = valeur t2 l2 "Ville" then
      [l1 @ List.map (fun i -> List.nth l2 i) idx_t2]
    else []
  in
  { entete = new_entete; lignes = new_lignes }

(* Q4 : Employés avec leur région *)
let q4 =
  let joined = jointure_ville employes depts in
  select joined ["Nom"; "Ville"; "Region"; "Salaire"]

(* --- Q5 : Sous-requête — les villes où le salaire moyen dépasse 48000 --- *)
let q5 =
  let salaires_par_ville = salaire_moyen_par_ville employes in
  let bonnes_villes =
    salaires_par_ville >>= fun (ville, sal) ->
    if int_of_string sal > 48000 then return ville else []
  in
  let lignes =
    employes.lignes >>= fun l ->
    if List.mem (valeur employes l "Ville") bonnes_villes then [l] else []
  in
  { employes with lignes }
(* Résultat : seuls Lyon, Marseille, Toulouse (salaire moyen > 48000) *)

(* --- Q7 : Les 3 employés les mieux payés --- *)
let q7 =
  let tries = List.sort (fun l1 l2 ->
    compare (int_of_string (valeur employes l2 "Salaire"))
            (int_of_string (valeur employes l1 "Salaire"))
  ) employes.lignes in
  { employes with lignes = List.filteri (fun i _ -> i < 3) tries }

(* --- Q8 : Requête avec plusieurs conditions --- *)
(* Employés parisiens ou lyonnais gagnant plus de 44000 *)
let q8 =
  employes.lignes >>= fun l ->
  let ville = valeur employes l "Ville" in
  let salaire = int_of_string (valeur employes l "Salaire") in
  if (ville = "Paris" || ville = "Lyon") && salaire > 44000 then
    return [valeur employes l "Nom"; ville; valeur employes l "Salaire"]
  else []
(* [["Alice"; "Paris"; "45000"]; ["Bob"; "Lyon"; "52000"];
    ["Franck"; "Paris"; "55000"]] *)

(* ==================================================================
   Tests
   ================================================================== *)

let () =
  Printf.printf "\n=== PARTIE 1 : La monade Liste ===\n\n";

  Printf.printf "--- Produit cartésien [1;2;3] x [\"a\";\"b\"] ---\n";
  List.iter (fun (x, y) -> Printf.printf "  (%d, %s)\n" x y) (cartesian [1; 2; 3] ["a"; "b"]);

  Printf.printf "\n--- Triplets pythagoriciens (≤ 15) ---\n";
  List.iter (fun (a, b, c) -> Printf.printf "  %d² + %d² = %d²\n" a b c) (pythagore 15);

  Printf.printf "\n--- Parties de [1;2;3] ---\n";
  List.iter (fun p -> Printf.printf "  [%s]\n" (String.concat ";" (List.map string_of_int p))) (parties [1; 2; 3]);

  Printf.printf "\n--- Combinaisons 2 de [1;2;3;4] ---\n";
  List.iter (fun c -> Printf.printf "  [%s]\n" (String.concat ";" (List.map string_of_int c))) (combinaisons 2 [1; 2; 3; 4]);

  Printf.printf "\n--- Chemins de A à F ---\n";
  List.iter (fun c -> Printf.printf "  %s\n" (String.concat " → " c)) (chemins graphe_exemple "A" "F");

  Printf.printf "\n\n=== PARTIE 2 : Listes en compréhension ===\n\n";

  Printf.printf "--- Table employés ---\n";
  affiche_table employes;
  Printf.printf "\n";

  Printf.printf "--- Q1 : Parisiens (Nom, Salaire) ---\n";
  affiche_table q1;
  Printf.printf "\n";

  Printf.printf "--- Q2 : Employés ≥ 30 ans ---\n";
  affiche_table q2;
  Printf.printf "\n";

  Printf.printf "--- Q3 : Salaire moyen par ville ---\n";
  List.iter (fun (v, s) -> Printf.printf "  %s : %s €\n" v s) (salaire_moyen_par_ville employes);
  Printf.printf "\n";

  Printf.printf "--- Q4 : Employés avec région ---\n";
  affiche_table q4;
  Printf.printf "\n";

  Printf.printf "--- Q5 : Villes avec salaire moyen > 48000 ---\n";
  affiche_table q5;
  Printf.printf "\n";

  Printf.printf "--- Q7 : Top 3 salaires ---\n";
  affiche_table q7;
  Printf.printf "\n";

  Printf.printf "--- Q8 : Paris/Lyon avec salaire > 44000 ---\n";
  List.iter (fun l -> Printf.printf "  [%s]\n" (String.concat "; " l)) q8