(* This program is free software; you can redistribute it and/or      *)
(* modify it under the terms of the GNU Lesser General Public License *)
(* as published by the Free Software Foundation; either version 2.1   *)
(* of the License, or (at your option) any later version.             *)
(*                                                                    *)
(* This program is distributed in the hope that it will be useful,    *)
(* but WITHOUT ANY WARRANTY; without even the implied warranty of     *)
(* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the      *)
(* GNU General Public License for more details.                       *)
(*                                                                    *)
(* You should have received a copy of the GNU Lesser General Public   *)
(* License along with this program; if not, write to the Free         *)
(* Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA *)
(* 02110-1301 USA                                                     *)


(*****************************************************************************)
(*          Projet Formel - Calculus of Inductive Constructions V5.10        *)
(*****************************************************************************)
(*									     *)
(*	            Functor Free Monoid : SET -> MON                         *)
(*									     *)
(*****************************************************************************)
(*									     *)
(*                     A. SAIBI	  May 95                  		     *)
(*									     *)
(*****************************************************************************)

Require Export FreeMonoid.
Require Export Functor.
Require Export MON.

Set Implicit Arguments.
Unset Strict Implicit.

(* SET -> MON *)

Section funfreemon_map_def.

Variable A B : Setoid.

 Section funfreemon_mor_def.

 Variable f : Map A B.

 Fixpoint Dist_fun (l : Tlist A) : Tlist B :=
   match l with
   | Empty => Empty B
   | Concat1 a l1 => Concat1 (f a) (Dist_fun l1)
   end.

 Lemma Dist_map_law : Map_law Dist_fun.
 Proof.
(* Goal: @Map_law (Tlist_setoid A) (Tlist_setoid B) Dist_fun *)
 unfold Map_law in |- *; intros l1; elim l1.
(* Goal: forall (y : Carrier (Tlist_setoid A)) (_ : @Equal (Tlist_setoid A) (Empty A) y), @Equal (Tlist_setoid B) (Dist_fun (Empty A)) (Dist_fun y) *)
(* Goal: forall (c : Carrier A) (t : Tlist A) (_ : forall (y : Carrier (Tlist_setoid A)) (_ : @Equal (Tlist_setoid A) t y), @Equal (Tlist_setoid B) (Dist_fun t) (Dist_fun y)) (y : Carrier (Tlist_setoid A)) (_ : @Equal (Tlist_setoid A) (@Concat1 A c t) y), @Equal (Tlist_setoid B) (Dist_fun (@Concat1 A c t)) (Dist_fun y) *)
 intro l2; elim l2.
(* Goal: forall _ : @Equal (Tlist_setoid A) (Empty A) (Empty A), @Equal (Tlist_setoid B) (Dist_fun (Empty A)) (Dist_fun (Empty A)) *)
(* Goal: forall (c : Carrier A) (t : Tlist A) (_ : forall _ : @Equal (Tlist_setoid A) (Empty A) t, @Equal (Tlist_setoid B) (Dist_fun (Empty A)) (Dist_fun t)) (_ : @Equal (Tlist_setoid A) (Empty A) (@Concat1 A c t)), @Equal (Tlist_setoid B) (Dist_fun (Empty A)) (Dist_fun (@Concat1 A c t)) *)
(* Goal: forall (c : Carrier A) (t : Tlist A) (_ : forall (y : Carrier (Tlist_setoid A)) (_ : @Equal (Tlist_setoid A) t y), @Equal (Tlist_setoid B) (Dist_fun t) (Dist_fun y)) (y : Carrier (Tlist_setoid A)) (_ : @Equal (Tlist_setoid A) (@Concat1 A c t) y), @Equal (Tlist_setoid B) (Dist_fun (@Concat1 A c t)) (Dist_fun y) *)
 intros; apply Refl.
(* Goal: forall (c : Carrier A) (t : Tlist A) (_ : forall _ : @Equal (Tlist_setoid A) (Empty A) t, @Equal (Tlist_setoid B) (Dist_fun (Empty A)) (Dist_fun t)) (_ : @Equal (Tlist_setoid A) (Empty A) (@Concat1 A c t)), @Equal (Tlist_setoid B) (Dist_fun (Empty A)) (Dist_fun (@Concat1 A c t)) *)
(* Goal: forall (c : Carrier A) (t : Tlist A) (_ : forall (y : Carrier (Tlist_setoid A)) (_ : @Equal (Tlist_setoid A) t y), @Equal (Tlist_setoid B) (Dist_fun t) (Dist_fun y)) (y : Carrier (Tlist_setoid A)) (_ : @Equal (Tlist_setoid A) (@Concat1 A c t) y), @Equal (Tlist_setoid B) (Dist_fun (@Concat1 A c t)) (Dist_fun y) *)
 intros c t H H1; elim H1.
(* Goal: forall (c : Carrier A) (t : Tlist A) (_ : forall (y : Carrier (Tlist_setoid A)) (_ : @Equal (Tlist_setoid A) t y), @Equal (Tlist_setoid B) (Dist_fun t) (Dist_fun y)) (y : Carrier (Tlist_setoid A)) (_ : @Equal (Tlist_setoid A) (@Concat1 A c t) y), @Equal (Tlist_setoid B) (Dist_fun (@Concat1 A c t)) (Dist_fun y) *)
 intros c t H l2; elim l2.
(* Goal: forall _ : @Equal (Tlist_setoid A) (@Concat1 A c t) (Empty A), @Equal (Tlist_setoid B) (Dist_fun (@Concat1 A c t)) (Dist_fun (Empty A)) *)
(* Goal: forall (c0 : Carrier A) (t0 : Tlist A) (_ : forall _ : @Equal (Tlist_setoid A) (@Concat1 A c t) t0, @Equal (Tlist_setoid B) (Dist_fun (@Concat1 A c t)) (Dist_fun t0)) (_ : @Equal (Tlist_setoid A) (@Concat1 A c t) (@Concat1 A c0 t0)), @Equal (Tlist_setoid B) (Dist_fun (@Concat1 A c t)) (Dist_fun (@Concat1 A c0 t0)) *)
 intro H1; absurd (Equal_Tlist (Concat1 c t) (Empty A)).
(* Goal: not (@Equal_Tlist A (@Concat1 A c t) (Empty A)) *)
(* Goal: @Equal_Tlist A (@Concat1 A c t) (Empty A) *)
(* Goal: forall (c0 : Carrier A) (t0 : Tlist A) (_ : forall _ : @Equal (Tlist_setoid A) (@Concat1 A c t) t0, @Equal (Tlist_setoid B) (Dist_fun (@Concat1 A c t)) (Dist_fun t0)) (_ : @Equal (Tlist_setoid A) (@Concat1 A c t) (@Concat1 A c0 t0)), @Equal (Tlist_setoid B) (Dist_fun (@Concat1 A c t)) (Dist_fun (@Concat1 A c0 t0)) *)
 apply (Diff_Concat1_Empty (A:=A)).
(* Goal: @Equal_Tlist A (@Dist_fun A A (Id_SET A) t) t *)
 trivial.
(* Goal: forall (c0 : Carrier A) (t0 : Tlist A) (_ : forall _ : @Equal (Tlist_setoid A) (@Concat1 A c t) t0, @Equal (Tlist_setoid B) (Dist_fun (@Concat1 A c t)) (Dist_fun t0)) (_ : @Equal (Tlist_setoid A) (@Concat1 A c t) (@Concat1 A c0 t0)), @Equal (Tlist_setoid B) (Dist_fun (@Concat1 A c t)) (Dist_fun (@Concat1 A c0 t0)) *)
 intros c0 t0 H1 H2.
(* Goal: @Equal (Tlist_setoid B) (Dist_fun (@Concat1 A c t)) (Dist_fun (@Concat1 A c0 t0)) *)
 elim H2; intros H3 H4.
(* Goal: @Equal (Tlist_setoid B) (Dist_fun (@Concat1 A c t)) (Dist_fun (@Concat1 A c0 t0)) *)
 simpl in |- *; split.
(* Goal: @Equal_Tlist A (@Dist_fun A A (Id_SET A) t) t *)
 apply Pres1; trivial.
(* Goal: @Equal_Tlist B (Dist_fun t) (Dist_fun t0) *)
 exact (H t0 H4).
 Qed.

 Canonical Structure Dist_map := Build_Map Dist_map_law.

 Lemma Dist_map_unit_law : MonUnit_law Dist_map.
 Proof.
(* Goal: @Equal_Tlist A (@Dist_fun A A (Id_SET A) t) t *)
 unfold MonUnit_law in |- *; simpl in |- *; trivial.
 Qed.

 Lemma Dist_map_op_law : MonOp_law Dist_map.
 Proof.
(* Goal: @MonOp_law (FreeMonoid A) (FreeMonoid B) Dist_map *)
 unfold MonOp_law in |- *.
(* Goal: forall a b : Carrier (Mcarrier (FreeMonoid A)), @Equal (Mcarrier (FreeMonoid B)) (@Ap (Mcarrier (FreeMonoid A)) (Mcarrier (FreeMonoid B)) Dist_map (@ApMop (FreeMonoid A) a b)) (@ApMop (FreeMonoid B) (@Ap (Mcarrier (FreeMonoid A)) (Mcarrier (FreeMonoid B)) Dist_map a) (@Ap (Mcarrier (FreeMonoid A)) (Mcarrier (FreeMonoid B)) Dist_map b)) *)
 intros l1 l2; elim l1.
(* Goal: @Equal (Mcarrier (FreeMonoid B)) (@Ap (Mcarrier (FreeMonoid A)) (Mcarrier (FreeMonoid B)) Dist_map (@ApMop (FreeMonoid A) (Empty A) l2)) (@ApMop (FreeMonoid B) (@Ap (Mcarrier (FreeMonoid A)) (Mcarrier (FreeMonoid B)) Dist_map (Empty A)) (@Ap (Mcarrier (FreeMonoid A)) (Mcarrier (FreeMonoid B)) Dist_map l2)) *)
(* Goal: forall (c : Carrier A) (t : Tlist A) (_ : @Equal (Mcarrier (FreeMonoid B)) (@Ap (Mcarrier (FreeMonoid A)) (Mcarrier (FreeMonoid B)) Dist_map (@ApMop (FreeMonoid A) t l2)) (@ApMop (FreeMonoid B) (@Ap (Mcarrier (FreeMonoid A)) (Mcarrier (FreeMonoid B)) Dist_map t) (@Ap (Mcarrier (FreeMonoid A)) (Mcarrier (FreeMonoid B)) Dist_map l2))), @Equal (Mcarrier (FreeMonoid B)) (@Ap (Mcarrier (FreeMonoid A)) (Mcarrier (FreeMonoid B)) Dist_map (@ApMop (FreeMonoid A) (@Concat1 A c t) l2)) (@ApMop (FreeMonoid B) (@Ap (Mcarrier (FreeMonoid A)) (Mcarrier (FreeMonoid B)) Dist_map (@Concat1 A c t)) (@Ap (Mcarrier (FreeMonoid A)) (Mcarrier (FreeMonoid B)) Dist_map l2)) *)
 unfold ApMop in |- *; apply Refl.
(* Goal: forall (c : Carrier A) (t : Tlist A) (_ : @Equal (Mcarrier (FreeMonoid B)) (@Ap (Mcarrier (FreeMonoid A)) (Mcarrier (FreeMonoid B)) Dist_map (@ApMop (FreeMonoid A) t l2)) (@ApMop (FreeMonoid B) (@Ap (Mcarrier (FreeMonoid A)) (Mcarrier (FreeMonoid B)) Dist_map t) (@Ap (Mcarrier (FreeMonoid A)) (Mcarrier (FreeMonoid B)) Dist_map l2))), @Equal (Mcarrier (FreeMonoid B)) (@Ap (Mcarrier (FreeMonoid A)) (Mcarrier (FreeMonoid B)) Dist_map (@ApMop (FreeMonoid A) (@Concat1 A c t) l2)) (@ApMop (FreeMonoid B) (@Ap (Mcarrier (FreeMonoid A)) (Mcarrier (FreeMonoid B)) Dist_map (@Concat1 A c t)) (@Ap (Mcarrier (FreeMonoid A)) (Mcarrier (FreeMonoid B)) Dist_map l2)) *)
 intros; split.
(* Goal: @Equal A (@Id_fun A c) c *)
(* Goal: @Equal_Tlist A (@Dist_fun A A (Id_SET A) t) t *)
 apply Refl.
(* Goal: @Equal_Tlist A (@Dist_fun A A (Id_SET A) t) t *)
 trivial.
 Qed.

 Canonical Structure FunFreeMon_mor :=
   Build_MonMor Dist_map_unit_law Dist_map_op_law.

 End funfreemon_mor_def.

Lemma FunFreeMon_map_law : Map_law FunFreeMon_mor.
Proof.
(* Goal: @Map_law (Map_setoid A B) (MonMor_setoid (FreeMonoid A) (FreeMonoid B)) FunFreeMon_mor *)
unfold Map_law in |- *; simpl in |- *.
(* Goal: forall (x y : Map A B) (_ : @Ext A B x y), @Equal_MonMor (FreeMonoid A) (FreeMonoid B) (FunFreeMon_mor x) (FunFreeMon_mor y) *)
intros f g; unfold Equal_MonMor in |- *; simpl in |- *.
(* Goal: forall _ : @Ext A B f g, @Ext (Tlist_setoid A) (Tlist_setoid B) (Dist_map f) (Dist_map g) *)
unfold Ext in |- *; simpl in |- *; intro H; intro l; elim l; simpl in |- *.
(* Goal: @Equal_Tlist A (@Dist_fun A A (Id_SET A) t) t *)
trivial.
(* Goal: forall (c : Carrier A) (t : Tlist A) (_ : @Equal_Tlist B (Dist_fun f t) (Dist_fun g t)), and (@Equal B (@Ap A B f c) (@Ap A B g c)) (@Equal_Tlist B (Dist_fun f t) (Dist_fun g t)) *)
intros c t H1; split.
(* Goal: @Equal B (@Ap A B f c) (@Ap A B g c) *)
(* Goal: @Equal_Tlist B (Dist_fun f t) (Dist_fun g t) *)
apply H.
(* Goal: @Equal_Tlist A (@Dist_fun A A (Id_SET A) t) t *)
trivial.
Qed.

Canonical Structure FunFreeMon_map := Build_Map FunFreeMon_map_law.

End funfreemon_map_def.

Lemma FunFreeMon_fcomp_law : Fcomp_law FunFreeMon_map.
Proof.
(* Goal: @Fcomp_law SET MON FreeMonoid FunFreeMon_map *)
unfold Fcomp_law in |- *; simpl in |- *.
(* Goal: forall (a b c : Setoid) (f : Map a b) (g : Map b c), @Equal_MonMor (FreeMonoid a) (FreeMonoid c) (@FunFreeMon_mor a c (@Comp SET a b c f g)) (@Comp MON (FreeMonoid a) (FreeMonoid b) (FreeMonoid c) (@FunFreeMon_mor a b f) (@FunFreeMon_mor b c g)) *)
intros A B C f g; unfold Equal_MonMor in |- *; simpl in |- *.
(* Goal: @Ext (Tlist_setoid A) (Tlist_setoid A) (@Dist_map A A (Id_SET A)) (Id_MON_map (FreeMonoid A)) *)
unfold Ext in |- *; simpl in |- *; intro l; elim l; simpl in |- *.
(* Goal: @Equal_Tlist A (@Dist_fun A A (Id_SET A) t) t *)
trivial.
(* Goal: forall (c : Carrier A) (t : Tlist A) (_ : @Equal_Tlist A (@Dist_fun A A (Id_SET A) t) (@Id_fun (Tlist_setoid A) t)), and (@Equal A (@Id_fun A c) c) (@Equal_Tlist A (@Dist_fun A A (Id_SET A) t) t) *)
intros c t H; split.
(* Goal: @Equal A (@Id_fun A c) c *)
(* Goal: @Equal_Tlist A (@Dist_fun A A (Id_SET A) t) t *)
apply Refl.
(* Goal: @Equal_Tlist A (@Dist_fun A A (Id_SET A) t) t *)
trivial.
Qed.

Lemma FunFreeMon_fid_law : Fid_law FunFreeMon_map.
Proof.
(* Goal: @Fid_law SET MON FreeMonoid FunFreeMon_map *)
unfold Fid_law in |- *; simpl in |- *.
(* Goal: forall a : Setoid, @Equal_MonMor (FreeMonoid a) (FreeMonoid a) (@FunFreeMon_mor a a (Id_SET a)) (Id_MON (FreeMonoid a)) *)
intro A; unfold Equal_MonMor in |- *; simpl in |- *.
(* Goal: @Ext (Tlist_setoid A) (Tlist_setoid A) (@Dist_map A A (Id_SET A)) (Id_MON_map (FreeMonoid A)) *)
unfold Ext in |- *; simpl in |- *; intro l; elim l; simpl in |- *.
(* Goal: @Equal_Tlist A (@Dist_fun A A (Id_SET A) t) t *)
trivial.
(* Goal: forall (c : Carrier A) (t : Tlist A) (_ : @Equal_Tlist A (@Dist_fun A A (Id_SET A) t) (@Id_fun (Tlist_setoid A) t)), and (@Equal A (@Id_fun A c) c) (@Equal_Tlist A (@Dist_fun A A (Id_SET A) t) t) *)
intros c t H; split.
(* Goal: @Equal A (@Id_fun A c) c *)
(* Goal: @Equal_Tlist A (@Dist_fun A A (Id_SET A) t) t *)
apply Refl.
(* Goal: @Equal_Tlist A (@Dist_fun A A (Id_SET A) t) t *)
trivial.
Qed.

Canonical Structure FunFreeMon :=
  Build_Functor FunFreeMon_fcomp_law FunFreeMon_fid_law.

