(**********************************************************************)
(**********************************************************************)
(* 1.1 *)

(**
Concatène 2 listes
@param l1 la première liste à concaténer
@param l2 la deuxième liste
@return la liste résultant de la concaténation de l1 avec l2 
*)
let rec concatene (l1 : int list) (l2 : int list) : int list =
  match l1 with [] -> l2 | x :: l1' -> x :: concatene l1' l2
;;

(* Quelques tests *)
concatene [ 1; 2; 3 ] [ 4; 5; 6 ] = [ 1; 2; 3; 4; 5; 6 ];;
concatene [] [ 4; 5; 6 ] = [ 4; 5; 6 ];;
concatene [ 1; 2; 3 ] [] = [ 1; 2; 3 ];;
concatene [] [] = []

(**********************************************************************)
(* 1.2 *)

(**
applatit prend une liste de liste et renvoie la liste resultant de la concatenation des sous-listes
@param ll la liste contenant les liste à concatener
@return la liste contenant les élements des sous-listes    
*)
let rec applatit (ll : int list list) : int list =
  match ll with [] -> [] | l :: ll' -> concatene l (applatit ll')
;;

(* Quelques tests *)
applatit [ [ 1; 2 ]; [ 3; 4; 5 ]; []; [ 6 ] ] = [ 1; 2; 3; 4; 5; 6 ];;
applatit [ [ 1 ] ] = [ 1 ];;
applatit [ [] ] = [];;
applatit [] = []

(**
applatit2 prend une liste de liste et renvoie la liste resultant de la concatenation des sous-listes.
applatit2 n'utilise pas concatene
@param ll la liste contenant les liste à concatener
@return la liste contenant les élements des sous-listes    
*)
let rec applatit2 (ll : int list list) : int list =
  match ll with
  | [] -> []
  | [] :: ll' -> applatit2 ll'
  | (n :: l') :: ll' -> n :: applatit2 (l' :: ll')
;;

(* Quelques tests *)
applatit2 [ [ 1; 2 ]; [ 3; 4; 5 ]; []; [ 6 ] ] = [ 1; 2; 3; 4; 5; 6 ];;
applatit2 [ [ 1 ] ] = [ 1 ];;
applatit2 [ [] ] = [];;
applatit2 [] = []

(**********************************************************************)
(**********************************************************************)
(* 2 *)

(**
Renverse une liste.
@param l la liste à renverse.
@return la liste renversée    
*)
let renverse =
  (*
  Cette fonction concatène son premier argument renversé à son second
  @param lr la liste à renverser
  @param lc la liste à laquelle on veut concaténer des éléments
  @return la concaténation de lr renversée et de lc    
  *)
  let rec renverse_ajoute (lr : int list) (lc : int list) : int list =
    match lr with
    | [] -> lc
    | n :: lr' ->
        (* on ajoute n en tête de la liste lc et on fait l'appel récursif
           qui ajoutera les autres éléments devant *)
        renverse_ajoute lr' (n :: lc)
  in
  fun (l : int list) -> renverse_ajoute l []

(**********************************************************************)
(**********************************************************************)
(* 3.1 *)
(* Insersion dans une liste triée *)

(**
Insère un entier dans une liste triée.
@param n la valeur à insérer
@param l la liste dans laquelle on fait l'insertion    
@return une nouvelle liste contenant les élément de l et n et elle-même
*)
let rec insertion (n : int) (l : int list) : int list =
  match l with
  | [] -> [ n ] (* on aurait pu écrire [n] *)
  | k :: l' ->
      if k >= n (* on veut placer n en tête de liste *) then n :: l
        (* attention c'est n :: l et pas n :: l'
           on aurait aussi pu écrire n :: k :: l' *)
      else k :: insertion n l'
;;

(* Quelques tests*)
insertion 3 [ 1; 2; 4; 5 ] = [ 1; 2; 3; 4; 5 ];;
insertion 3 [ 1; 2; 3; 4; 5 ] = [ 1; 2; 3; 3; 4; 5 ];;
insertion 3 [ 4; 5 ] = [ 3; 4; 5 ];;
insertion 3 [ 1; 2 ] = [ 1; 2; 3 ];;
insertion 3 [] = [ 3 ]
(**********************************************************************)
(* 3.2 *)

(**
Trie une liste en utilisant l'algorithme de tri par insertion
@param l la liste à trier
@return la liste contenant les éléments de l triés    
*)
let rec tri_insertion (l : int list) : int list =
  match l with
  | [] -> []
  | n :: l' ->
      (* Ici, on insère dans le reste de la liste triée *)
      insertion n (tri_insertion l')
;;

(* Quelques tests *)
tri_insertion [ 1; 4; 2; 3 ] = [ 1; 2; 3; 4 ];;
tri_insertion [ 1; 2; 3; 4 ] = [ 1; 2; 3; 4 ];;
tri_insertion [ 4; 3; 2; 1 ] = [ 1; 2; 3; 4 ];;
tri_insertion [ 1 ] = [ 1 ];;
tri_insertion [] = []

(**********************************************************************)
(**********************************************************************)
(* 4.1 *)

(** 
Résultat d'une recherche 
*)
type resultat =
  (* une valeur a été trouvée,
     on associe la donnée de cette valeur au constructeur,
     elle a donc le type string*)
  | Trouve of string
  (* On a rien trouvé, pas de donnée associée *)
  | Rien

(* 4.2 *)

(**
Cherche la valeur associée à une clé dans une liste de paires (clé,valeur).
@param cle la clé
@param la la liste d'association
@return Trouve v si la paire (cle,v) est dans la liste, Rien sinon
*)
let rec cherche (cle : int) (la : (int * string) list) : resultat =
  match la with
  | [] -> Rien
  | (cle', v) :: la' ->
      if cle' = cle (* si on a trouvé la clé *) then Trouve v
      else (* on cherche dans le reste de la liste *)
        cherche cle la'
;;

(* Quelques tests *)
cherche 3 [ (1, "a"); (3, "b"); (5, "c") ] = Trouve "b";;
cherche 3 [ (3, "b"); (5, "c") ] = Trouve "b";;
cherche 3 [ (1, "a"); (3, "b") ] = Trouve "b";;
cherche 3 [ (5, "b"); (1, "a") ] = Rien;;
cherche 3 [] = Rien

(**********************************************************************)
(**********************************************************************)

(**
Type représentant les opérateurs binaires.    
*)
type binop = Plus | Moins | Mult | Div

(**
Type représentant les morceaux d'expression.
*)
type elt_expr = Op of binop | Cst of int

(**
Type représentant les résultats.    
*)
type resultat =
  | Ok of int
  | ErrDivZero
  | ErrExpr
      (**
Évalue le résultat d'une opération binaire.
Prend l'opération en argument ainsi que deux résultats.
S'il l'un des arguments est une erreur, cette (une de ces)
erreur est renvoyée comme résultat.
@param op l'opération à effectuer
@param a1 la première valeur à passer à op
@param a2 la deuxième valeur à passer à op
@return le réultat de l'opération ou une erreur le cas échéant
*)
(* 5.1 *)

let eval_op (op : binop) (a1 : resultat) (a2 : resultat) : resultat =
  match (a1, a2) with
  | Ok v1, Ok v2 -> (
      match op with
      | Plus -> Ok (v1 + v2)
      | Moins -> Ok (v1 - v2)
      | Mult -> Ok (v1 * v2)
      | Div -> if v2 = 0 then ErrDivZero else Ok (v1 / v2))
  | Ok _, err -> err
  | err, _ -> err
;;

(* Quelques tests *)
eval_op Plus (Ok 1) (Ok 2) = Ok 3;;
eval_op Moins (Ok 2) (Ok 3) = Ok (-1);;
eval_op Div (Ok 3) (Ok 0) = ErrDivZero;;
eval_op Div (Ok 5) (Ok 2) = Ok 2;;
eval_op Mult (Ok 7) (Ok 6) = Ok 42;;
eval_op Plus ErrDivZero (Ok 5) = ErrDivZero;;
eval_op Mult ErrExpr (Ok 4) = ErrExpr;;
eval_op Div (Ok 5) ErrExpr = ErrExpr;;
eval_op Moins (Ok 4) ErrDivZero = ErrDivZero;;
eval_op Plus ErrDivZero ErrExpr = ErrDivZero

(**********************************************************************)
(* 5.2 *)

(**
Évalue une suite d'expressions et donne la liste des résultats
@param la liste d'éléments d'expression formant la liste suite d'expressions
@return le résultat de l'évaluation des expressions
*)
let rec eval_expr (le : elt_expr list) : resultat list =
  match le with
  | [] -> []
  | Cst n :: le' -> Ok n :: eval_expr le'
  | Op op :: le' -> (
      match eval_expr le' with
      | r1 :: r2 :: rl -> eval_op op r1 r2 :: rl
      | _ -> [ ErrExpr ])
;;

(* Quelques tests *)
eval_expr [ Cst 3 ] = [ Ok 3 ];;
eval_expr [ Op Mult; Cst 3; Cst 2 ] = [ Ok 6 ];;
eval_expr [ Op Div; Cst 7; Cst 3 ] = [ Ok 2 ];;
eval_expr [ Op Moins; Cst 3; Cst 1 ] = [ Ok 2 ];;
eval_expr [ Op Plus; Op Div; Cst 7; Cst 3 ] = [ ErrExpr ];;
eval_expr [ Op Plus; Op Div; Cst 7; Cst 3; Cst 5 ] = [ Ok 7 ];;

eval_expr [ Op Plus; Op Div; Cst 7; Op Moins; Cst 2; Cst 2; Cst 3 ]
= [ ErrDivZero ]
;;

eval_expr [ Op Plus; Cst 3; Cst 5; Op Moins; Cst 2; Cst 7 ] = [ Ok 8; Ok (-5) ]