Require Arith.

(* 1. Quelques preliminaires, utiles pour la suite, mais ce n'est
  pas grave si vous ne comprenez pas les preuves. *)

(* au_plus est une function qui retourne le booleen true si m<=n, false sinon.
  Il s'agit d'un programme, au contraire de la relation le, qui est un predicat
  (de type nat -> nat -> Prop). *)
Fixpoint au_plus [m,n:nat] : bool :=
  Cases m of
      O => true
    | (S m') =>
      Cases n of
          O => false
	| (S n') => (au_plus m' n')
      end
  end.

Lemma choix_bool : (b:bool) b=true \/ b=false.
Proof.
  Induction b. Left . Reflexivity.
  Right . Reflexivity.
Qed.

Lemma au_plus_le_1 : (n,m:nat) (au_plus m n)=true -> (le m n).
Proof.
  Induction n. Induction m. Intro. Apply le_n.
  Simpl. Intros. Discriminate H0.
  Induction m. Intro. Apply le_O_n.
  Simpl. Intros. Apply le_n_S. Apply H. Assumption.
Qed.

Lemma au_plus_le_2 : (n,m:nat) (le m n) -> (au_plus m n)=true.
Proof.
  Induction n. Induction m. Trivial.
  Intros. Elim (le_Sn_O n0 H0).
  Induction m. Trivial.
  Intros. Simpl. Apply H. Apply le_S_n. Assumption.
Qed.

Lemma au_plus_le_3 : (n,m:nat) (au_plus m n)=false -> ~(le m n).
Proof.
  Unfold not. Intros. Rewrite (au_plus_le_2 n m H0) in H. Discriminate H.
Qed.

Lemma au_plus_le_4 : (n,m:nat) ~(le m n) -> (au_plus m n)=false.
Proof.
  Intros. Elim (choix_bool (au_plus m n)). Intro. Elim (H (au_plus_le_1 n m H0)).
  Trivial.
Qed.

Lemma au_plus_refl : (m:nat) (au_plus m m)=true.
Proof.
  Induction m; Trivial.
Qed.

Lemma au_plus_trans : (m,n,k:nat) (au_plus m n)=true -> (au_plus n k)=true ->
                            (au_plus m k)=true.
Proof.
  Intros. Apply au_plus_le_2. (Apply (le_trans m n k); Apply au_plus_le_1; Assumption).
Qed.

Lemma au_plus_total : (m,n:nat) (au_plus m n)=false -> (au_plus n m)=true.
Proof.
  Induction m. Induction n. Trivial.
  Intros. Elim (au_plus_le_3 ? ? H0 (le_O_n (S n0))).
  Induction n0. Trivial.
  Intros. Simpl. Apply H. Exact H1.
Qed.

(* De meme, egal est le programme calculant si les deux entiers en entree sont
  egaux ou non. *)
Fixpoint egal [m,n:nat] : bool :=
  Cases m n of
      O O => true
    | (S m') (S n') => (egal m' n')
    | _ _ => false
  end.

Lemma egal_1 : (m,n:nat) (egal m n)=true -> m=n.
Proof.
  Induction m. Induction n. Trivial.
  Intros. Simpl in H0. Discriminate H0.
  Induction n0. Simpl. Intro. Discriminate H0.
  Simpl. Intros. Cut n=n1. Intro. Rewrite H2. Reflexivity.
  Apply H. Assumption.
Qed.

Lemma egal_refl : (m:nat) (egal m m)=true.
Proof.
  Induction m; Trivial.
Qed.

Lemma egal_imp_au_plus : (m,n:nat) (egal m n)=true -> (au_plus m n)=true.
Proof.
  Intros. Rewrite (egal_1 m n H). Apply au_plus_refl.
Qed.

Lemma non_au_plus_imp_non_egal : (m,n:nat) (au_plus m n)=false -> (egal m n)=false.
Proof.
  Intros. Elim (choix_bool (egal m n)). Intro. Rewrite (egal_imp_au_plus m n H0) in H.
  Discriminate H.
  Trivial.
Qed.



(* 2. Les listes d'entiers *)


Inductive liste : Set :=
  nil : liste | cons : nat -> liste -> liste.


(* 3. Analyse des proprietes des listes triees *)


Fixpoint minore [x:nat; l:liste] : Prop := (* un predicat disant si x est <= a
  tous les elements de la liste l. *)
  Cases l of
      nil => True
    | (cons m l') => (au_plus x m)=true /\ (minore x l')
  end.

Fixpoint ordonnee [l : liste] : Prop := (* un predicat disant si l est une liste
  ordonnee, c'est-a-dire triee en ordre croissant. *)
  Cases l of
      nil => True
    | (cons n l') => (minore n l') /\ (ordonnee l')
  end.

Lemma minore_ordonnee_1 : (l:liste) (m:nat) (ordonnee (cons m l)) ->
      (x:nat) (au_plus x m)=true -> (minore x l).
Proof.
  Induction l. Intros. Simpl. Trivial.
  Intros. Simpl. Split. Apply au_plus_trans with n:=m. Assumption.
  Simpl in H0. Elim H0. Intros. Elim H2. Intros. Assumption.
  Apply H with m:=m. Simpl in H0. Simpl. Elim H0. Intros. Elim H3. Intros. Elim H2. Intros.
  (Split; Assumption).
  Assumption.
Qed.

Lemma minore_ordonnee_2 : (l:liste) (m:nat) (ordonnee (cons m l)) ->
      (x:nat) (au_plus x m)=true -> (minore x (cons m l)).
Proof.
  Intros. Simpl. Split. Assumption.
  Apply minore_ordonnee_1 with m:=m. Assumption.
  Assumption.
Qed.

Fixpoint insere [x:nat; l:liste] : liste :=
  Cases l of
      nil => (cons x nil)
    | (cons m l') =>
      if (au_plus x m)
      then (cons x l)
      else (cons m (insere x l'))
  end.

Lemma minore_insere_1 : (l:liste) (x,m:nat)
      (au_plus m x)=true -> (minore m l) -> (minore m (insere x l)).
Proof.
  Induction l. Simpl. Intros. (Split; Trivial).
  Simpl. Intros. Elim H1. Intros. Elim (choix_bool (au_plus x n)). Intro. Rewrite H4. Simpl.
  Split. Assumption.
  Split. Assumption.
  Assumption.
  Intro. Rewrite H4. Simpl. Split. Assumption.
  Apply H. Assumption.
  Assumption.
Qed.

Lemma insere_preserve_l_ordre : (l:liste) (ordonnee l) ->
      (x:nat) (ordonnee (insere x l)).
Proof.
  Induction l. Simpl. Intros. (Split; Trivial).
  Intros. Simpl. Elim (choix_bool (au_plus x n)). Intro. Rewrite H1.
  Change (minore x (cons n l0))/\(ordonnee (cons n l0)). Split.
  Apply minore_ordonnee_2. Assumption.
  Assumption.
  Assumption.
  Intro. Rewrite H1. Simpl. Split. Apply minore_insere_1. Apply au_plus_total. Assumption.
  Simpl in H0. Elim H0. Intros. Assumption.
  Apply H. Simpl in H0. Elim H0. Intros. Assumption.
Qed.


(* 4. Analyse des nombres d'occurrences de valeurs dans les listes *)

(* Le nombre d'occurrences de x dans l est le nombre de fois ou x apparait dans l.
  On dira que l et l' ont les memes elements si tout x apparait dans les deux
  exactement le meme nombre de fois. *)

Fixpoint nombre_d_occurrences [x:nat; l:liste] : nat :=
  Cases l of
      nil => O
    | (cons m l') =>
      if (egal x m)
      then (S (nombre_d_occurrences x l'))
      else (nombre_d_occurrences x l')
  end.

Lemma nocc_insere_1 : (l:liste) (x:nat)
    (nombre_d_occurrences x (insere x l))=(S (nombre_d_occurrences x l)).
Proof.
  Induction l. Simpl. Intro. Rewrite (egal_refl x). Reflexivity.
  Intros. Simpl. Elim (choix_bool (au_plus x n)). Intro. Rewrite H0. Simpl.
  Rewrite (egal_refl x). Reflexivity.
  Intro. Rewrite H0. Simpl. Rewrite (non_au_plus_imp_non_egal x n H0). Apply H.
Qed.

Lemma nocc_insere_2 : (l:liste) (x:nat) (m:nat)
    (egal x m)=false ->
      (nombre_d_occurrences x (insere m l))=(nombre_d_occurrences x l).
Proof.
  Induction l. Simpl. Intros. Rewrite H. Reflexivity.
  Intros. Simpl. Elim (choix_bool (au_plus m n)). Intro. Rewrite H1. Simpl. Rewrite H0.
  Reflexivity.
  Intro. Rewrite H1. Simpl. Rewrite (H x m H0). Reflexivity.
Qed.

Definition memes_elements := [l,l':liste]
  (x:nat) (nombre_d_occurrences x l)=(nombre_d_occurrences x l').

Lemma memes_elements_trans : (l,l',l'':liste)
  (memes_elements l l') -> (memes_elements l' l'') -> (memes_elements l l'').
Proof.
  Unfold memes_elements. Intros. Rewrite (H x). Apply H0.
Qed.

Lemma insere_preserve_les_elements_1 : (l:liste)
      (x:nat) (memes_elements (cons x l) (insere x l)).
Proof.
  Induction l. Simpl. Intro. Unfold memes_elements. Intro. Reflexivity.
  Unfold memes_elements. Intros. Elim (choix_bool (egal x0 x)). Intro. Rewrite (egal_1 x0 x H0).
  Rewrite (nocc_insere_1 (cons n l0) x). Simpl. Rewrite (egal_refl x). Reflexivity.
  Intro. Rewrite (nocc_insere_2 (cons n l0) x0 x H0). Simpl. Rewrite H0. Reflexivity.
Qed.

Lemma memes_elements_cons : (l,l':liste) (memes_elements l l') ->
      (x:nat) (memes_elements (cons x l) (cons x l')).
Proof.
  Unfold memes_elements. Simpl. Intros. Rewrite (H x0). Reflexivity.
Qed.

Lemma insere_preserve_les_elements_2 : (l,l':liste)
      (memes_elements l l') -> (x:nat) (memes_elements (cons x l) (insere x l')).
Proof.
  Intros. Apply memes_elements_trans with l':=(cons x l'). Apply memes_elements_cons.
  Assumption.
  Apply insere_preserve_les_elements_1.
Qed.


(* 5. Le tri par insertion *)


(* La modelisation du tri (en fait, un vrai programme de tri, essayez
  Eval Compute in (tri (cons (3) (cons (1) (cons (2) nil)))).
  par exemple...
   *)

Fixpoint tri [l:liste] : liste :=
  Cases l of
      nil => nil
    | (cons x l') => (insere x (tri l'))
  end.

(* La specification du tri, en deux parties:
  (tri_ordonne) le resultat du tri sur toute liste l est une liste triee;
  (tri_preserve_les_elements) le resultat du tri sur toute liste l a les memes elements que l.
*)
Lemma tri_ordonne : (l:liste) (ordonnee (tri l)).
Proof.
  Induction l. Simpl. Trivial.
  Simpl. Intros. Apply insere_preserve_l_ordre. Assumption.
Qed.

Lemma tri_preserve_les_elements : (l:liste) (memes_elements l (tri l)).
Proof.
  Induction l. Unfold memes_elements. Intro. Simpl. Reflexivity.
  Simpl. Intros. Apply insere_preserve_les_elements_2. Assumption.
Qed.