Library Coq.Sets.Multiset
Require Import Permut Setoid.
Require Plus.
Set Implicit Arguments.
Section multiset_defs.
Variable A : Type.
Variable eqA : A -> A -> Prop.
Hypothesis eqA_equiv : Equivalence eqA.
Hypothesis Aeq_dec : forall x y:A, {eqA x y} + {~ eqA x y}.
Inductive multiset : Type :=
Bag : (A -> nat) -> multiset.
Definition EmptyBag := Bag (fun a:A => 0).
Definition SingletonBag (a:A) :=
Bag (fun a':A => match Aeq_dec a a' with
| left _ => 1
| right _ => 0
end).
Definition multiplicity (m:multiset) (a:A) : nat := let (f) := m in f a.
multiset equality
Definition meq (m1 m2:multiset) :=
forall a:A, multiplicity m1 a = multiplicity m2 a.
Lemma meq_refl : forall x:multiset, meq x x.
Lemma meq_trans : forall x y z:multiset, meq x y -> meq y z -> meq x z.
Lemma meq_sym : forall x y:multiset, meq x y -> meq y x.
forall a:A, multiplicity m1 a = multiplicity m2 a.
Lemma meq_refl : forall x:multiset, meq x x.
Lemma meq_trans : forall x y z:multiset, meq x y -> meq y z -> meq x z.
Lemma meq_sym : forall x y:multiset, meq x y -> meq y x.
multiset union
Definition munion (m1 m2:multiset) :=
Bag (fun a:A => multiplicity m1 a + multiplicity m2 a).
Lemma munion_empty_left : forall x:multiset, meq x (munion EmptyBag x).
Lemma munion_empty_right : forall x:multiset, meq x (munion x EmptyBag).
Lemma munion_comm : forall x y:multiset, meq (munion x y) (munion y x).
Lemma munion_ass :
forall x y z:multiset, meq (munion (munion x y) z) (munion x (munion y z)).
Lemma meq_left :
forall x y z:multiset, meq x y -> meq (munion x z) (munion y z).
Lemma meq_right :
forall x y z:multiset, meq x y -> meq (munion z x) (munion z y).
Bag (fun a:A => multiplicity m1 a + multiplicity m2 a).
Lemma munion_empty_left : forall x:multiset, meq x (munion EmptyBag x).
Lemma munion_empty_right : forall x:multiset, meq x (munion x EmptyBag).
Lemma munion_comm : forall x y:multiset, meq (munion x y) (munion y x).
Lemma munion_ass :
forall x y z:multiset, meq (munion (munion x y) z) (munion x (munion y z)).
Lemma meq_left :
forall x y z:multiset, meq x y -> meq (munion x z) (munion y z).
Lemma meq_right :
forall x y z:multiset, meq x y -> meq (munion z x) (munion z y).
Here we should make multiset an abstract datatype, by hiding Bag,
munion, multiplicity; all further properties are proved abstractly
Lemma munion_rotate :
forall x y z:multiset, meq (munion x (munion y z)) (munion z (munion x y)).
Lemma meq_congr :
forall x y z t:multiset, meq x y -> meq z t -> meq (munion x z) (munion y t).
Lemma munion_perm_left :
forall x y z:multiset, meq (munion x (munion y z)) (munion y (munion x z)).
Lemma multiset_twist1 :
forall x y z t:multiset,
meq (munion x (munion (munion y z) t)) (munion (munion y (munion x t)) z).
Lemma multiset_twist2 :
forall x y z t:multiset,
meq (munion x (munion (munion y z) t)) (munion (munion y (munion x z)) t).
specific for treesort
Lemma treesort_twist1 :
forall x y z t u:multiset,
meq u (munion y z) ->
meq (munion x (munion u t)) (munion (munion y (munion x t)) z).
Lemma treesort_twist2 :
forall x y z t u:multiset,
meq u (munion y z) ->
meq (munion x (munion u t)) (munion (munion y (munion x z)) t).
SingletonBag
Lemma meq_singleton : forall a a',
eqA a a' -> meq (SingletonBag a) (SingletonBag a').
End multiset_defs.
Unset Implicit Arguments.
Hint Unfold meq multiplicity: datatypes.
Hint Resolve munion_empty_right munion_comm munion_ass meq_left meq_right
munion_empty_left: datatypes.
Hint Immediate meq_sym: datatypes.