Section RBindings.
Require Import List.
Require Import Sumbool.
Require Import Arith.
Require Import Bool.
Require Import Permutation.
Require Import Equivalence.
Require Import EquivDec.
Require Import RelationClasses.
Require Import Orders.
Require Import Permutation.
Require Import RUtil RAssoc RList RSort RSublist.
Class ODT {
K:
Type}
:=
mkODT {
ODT_eqdec:>
EqDec K eq;
ODT_lt:
K ->
K ->
Prop;
ODT_lt_strorder:>
StrictOrder ODT_lt;
ODT_lt_dec:
forall (
a b:
K), {
ODT_lt a b} + {~
ODT_lt a b};
ODT_compare:
K ->
K ->
comparison;
ODT_compare_spec:
forall x y :
K,
CompareSpec (
eq x y) (
ODT_lt x y) (
ODT_lt y x) (
ODT_compare x y) }.
Generalizable Variables K.
Context `{
odt:@
ODT K}.
Lemma ODT_lt_irr (
k:
K) :
~(
ODT_lt k k).
Proof.
Ltac dest_strlt :=
match goal with
| [|-
context [
ODT_lt_dec ?
x ?
y]] =>
destruct (
ODT_lt_dec x y);
simpl
| [
H:
ODT_lt ?
x ?
x|-
_] => (
assert False by (
apply (
ODT_lt_irr x);
auto);
contradiction)
end.
Lemma trichotemy a b : {
ODT_lt a b} + {
eq a b} + {
ODT_lt b a}.
Proof.
generalize (
ODT_compare_spec a b);
intros nc.
destruct (
ODT_compare a b); [
left;
right|
left;
left|
right];
inversion nc;
trivial.
Defined.
Lemma compare_refl_eq a:
ODT_compare a a =
Eq.
Proof.
Lemma compare_eq_iff x y : (
ODT_compare x y) =
Eq <->
x=
y.
Proof.
Lemma ODT_lt_contr (
x y :
K) : ~
ODT_lt x y -> ~
ODT_lt y x ->
x =
y.
Proof.
destruct (
trichotemy x y)
as [[?|?]|?];
intuition.
Qed.
Definition rec_field_lt {
A} (
a b:
K*
A) :=
ODT_lt (
fst a) (
fst b).
Global Instance rec_field_lt_strict {
A} :
StrictOrder (@
rec_field_lt A).
Proof.
Lemma rec_field_lt_dec {
A} (
a b:
K*
A) :
{
rec_field_lt a b} + {~
rec_field_lt a b}.
Proof.
Lemma rec_field_lt_irr {
A} (
a:
K*
A) :
~(
rec_field_lt a a).
Proof.
Lemma Forall_rec_field_lt {
A} (
a:
K*
A)
l :
Forall (
rec_field_lt a)
l <->
Forall (
ODT_lt (
fst a)) (
domain l).
Proof.
destruct a; simpl.
induction l; simpl.
- intuition.
- destruct IHl as [H1 H2].
split; inversion 1; subst; constructor; eauto.
Qed.
Definition rec_cons_sort {
A} :=
@
insertion_sort_insert (
K*
A)
rec_field_lt rec_field_lt_dec.
Definition rec_sort {
A} :=
@
insertion_sort (
K*
A)
rec_field_lt rec_field_lt_dec.
Definition rec_concat_sort {
A} (
l1 l2:
list (
K*
A)) : (
list (
K*
A)) :=
rec_sort (
l1++
l2).
Lemma sorted_rec_nil {
A} :
is_list_sorted ODT_lt_dec (@
domain K A nil) =
true.
Proof.
reflexivity.
Qed.
Lemma sort_rec_single_type {
A} (
k:
K) (
a:
A):
is_list_sorted ODT_lt_dec (
domain ((
k,
a)::
nil)) =
true.
Proof.
reflexivity.
Defined.
Lemma field_less_is_neq (
a1 a2:
K) :
ODT_lt a1 a2 ->
a1 <>
a2.
Proof.
unfold not;
intros.
subst;
dest_strlt.
Qed.
Lemma field_less_is_not_more (
a1 a2:
K) :
ODT_lt a1 a2 -> ~(
ODT_lt a2 a1).
Proof.
Lemma field_not_less_and_neq_is_more (
a1 a2:
K) :
~(
ODT_lt a1 a2) -> ~(
eq a1 a2) ->
ODT_lt a2 a1.
Proof.
unfold not;
intros.
generalize (
ODT_compare_spec a1 a2).
intros.
inversion H1.
congruence.
assert False.
apply H.
assumption.
contradiction.
assumption.
Qed.
Lemma rec_cons_lt {
A} (
l1:
list (
K*
A)) (
a1 a2:
K*
A) :
is_list_sorted ODT_lt_dec (
domain (
a2 ::
l1)) =
true ->
ODT_lt (
fst a1) (
fst a2) ->
is_list_sorted ODT_lt_dec (
domain (
a1 ::
a2 ::
l1)) =
true.
Proof.
simpl;
intros.
revert H0;
elim (
ODT_lt_dec (
fst a1) (
fst a2));
intros.
assumption.
contradiction.
Qed.
Lemma rec_sorted_skip_first {
A} (
l1:
list (
K*
A)) (
a:
K*
A) :
is_list_sorted ODT_lt_dec (
domain (
a ::
l1)) =
true ->
is_list_sorted ODT_lt_dec (
domain l1) =
true.
Proof.
simpl.
intros.
revert H;
elim (
domain l1);
intros.
reflexivity.
destruct (
ODT_lt_dec (
fst a)
a0);
congruence.
Qed.
Lemma rec_sorted_skip_second {
A} (
l:
list (
K*
A)) (
a1 a2:
K*
A) :
is_list_sorted ODT_lt_dec (
domain (
a1 ::
a2 ::
l)) =
true ->
is_list_sorted ODT_lt_dec (
domain (
a1 ::
l)) =
true.
Proof.
Lemma rec_sorted_skip_third {
A} (
l:
list (
K*
A)) (
a1 a2 a3:
K*
A) :
is_list_sorted ODT_lt_dec (
domain (
a1 ::
a2 ::
a3 ::
l)) =
true ->
is_list_sorted ODT_lt_dec (
domain (
a1 ::
a2 ::
l)) =
true.
Proof.
Lemma rec_sorted_distinct {
A} (
l:
list (
K*
A)) (
a1 a2:
K*
A) :
is_list_sorted ODT_lt_dec (
domain (
a1 ::
a2 ::
l)) =
true ->
(
fst a1) <> (
fst a2).
Proof.
Lemma rec_sorted_lt {
A} (
l:
list (
K*
A)) (
a1 a2:
K*
A) :
is_list_sorted ODT_lt_dec (
domain (
a1 ::
a2 ::
l)) =
true ->
ODT_lt (
fst a1) (
fst a2).
Proof.
simpl.
elim (
ODT_lt_dec (
fst a1) (
fst a2));
intros.
assumption.
congruence.
Qed.
Lemma sorted_cons_in {
A} (
l:
list (
K*
A)) (
a a':
K*
A) :
is_list_sorted ODT_lt_dec (
domain (
a ::
l)) =
true ->
In a'
l ->
ODT_lt (
fst a) (
fst a').
Proof.
Lemma rec_cons_lt_first {
A} (
l1:
list (
K*
A)) (
a1 a2:
K*
A) :
is_list_sorted ODT_lt_dec (
domain (
a2 ::
l1)) =
true ->
ODT_lt (
fst a1) (
fst a2) ->
rec_cons_sort a1 (
a2 ::
l1) = (
a1 ::
a2 ::
l1).
Proof.
Lemma sort_sorted_is_id {
A} (
l:
list (
K*
A)) :
is_list_sorted ODT_lt_dec (
domain l) =
true ->
rec_sort l =
l.
Proof.
Lemma rec_concat_sort_concats {
A} (
l1 l2:
list (
K*
A)) :
rec_concat_sort l1 l2 =
rec_sort (
l1++
l2).
Proof.
reflexivity.
Qed.
Lemma rec_cons_sorted_id {
A} (
l:
list (
K*
A)) (
a:
K*
A) :
is_list_sorted ODT_lt_dec (
domain (
a ::
l)) =
true ->
rec_cons_sort a l =
a::
l.
Proof.
Lemma rec_sorted_id {
A} (
l:
list (
K*
A)) :
is_list_sorted ODT_lt_dec (
domain l) =
true ->
rec_sort l =
l.
Proof.
Lemma rec_cons_gt_first {
A} (
l'
l:
list (
K*
A)) (
a1 a2:
K*
A) :
rec_cons_sort a1 l =
l' ->
is_list_sorted ODT_lt_dec (
domain (
a2 ::
l)) =
true ->
ODT_lt (
fst a2) (
fst a1) ->
(
exists a3,
exists l'',
rec_cons_sort a1 l = (
a3 ::
l'')
/\
ODT_lt (
fst a2) (
fst a3)).
Proof.
revert a1 a2 l'.
induction l;
intros.
-
simpl in *;
intros;
exists a1,
nil;
split; [
reflexivity|
assumption].
-
simpl in *.
revert H;
elim (
rec_field_lt_dec a1 a);
intros.
inversion H.
exists a1,(
a::
l).
split; [
reflexivity|
assumption].
revert H;
elim (
rec_field_lt_dec a a1);
intros.
destruct l';
try congruence.
rewrite H in *.
exists p,
l'.
+
split;
try reflexivity.
inversion H.
rewrite <-
H3 in *;
clear H3.
revert H0.
elim (
ODT_lt_dec (
fst a2) (
fst a));
intros.
assumption.
congruence.
+
exists a,
l.
split.
reflexivity.
revert H0.
elim (
ODT_lt_dec (
fst a2) (
fst a));
intros.
assumption.
congruence.
Qed.
Lemma rec_cons_sorted {
A} (
l1 l2:
list (
K*
A)) (
a:
K*
A) :
is_list_sorted ODT_lt_dec (
domain l1) =
true ->
rec_cons_sort a l1 =
l2 ->
is_list_sorted ODT_lt_dec (
domain l2) =
true.
Proof.
Lemma rec_sort_sorted {
A} (
l1 l2:
list (
K*
A)) :
rec_sort l1 =
l2 ->
is_list_sorted ODT_lt_dec (
domain l2) =
true.
Proof.
revert l2.
induction l1;
intros.
simpl;
inversion H;
reflexivity.
simpl in *.
assert (
exists l'',
rec_sort l1 =
l'').
revert H.
elim (
rec_sort l1);
intros.
exists nil;
reflexivity.
exists (
a0::
l);
reflexivity.
elim H0;
intros;
clear H0.
rewrite H1 in H.
assert (
is_list_sorted ODT_lt_dec (
domain x) =
true).
apply (
IHl1 x H1);
assumption.
apply (
rec_cons_sorted x l2 a);
assumption.
Qed.
Lemma rec_sort_pf {
A} {
l1:
list (
K*
A)} :
is_list_sorted ODT_lt_dec (
domain (
rec_sort l1)) =
true.
Proof.
Lemma rec_concat_sort_sorted {
A} (
l1 l2 x:
list (
K*
A)) :
rec_concat_sort l1 l2 =
x ->
is_list_sorted ODT_lt_dec (
domain x) =
true.
Proof.
Lemma same_domain_same_sorted {
A} {
B} (
l1:
list (
K*
A)) (
l2:
list (
K*
B)) :
domain l1 =
domain l2 ->
is_list_sorted ODT_lt_dec (
domain l1) =
true ->
is_list_sorted ODT_lt_dec (
domain l2) =
true.
Proof.
intros.
rewrite <- H; assumption.
Qed.
Lemma same_domain_insert {
A} {
B}
(
l1:
list (
K*
A)) (
l2:
list (
K*
B))
(
a:
K*
A) (
b:
K*
B):
domain l1 =
domain l2 ->
fst a =
fst b ->
domain (
rec_cons_sort a l1) =
domain (
rec_cons_sort b l2).
Proof.
intros.
revert l2 H.
induction l1.
induction l2;
simpl in *;
congruence.
intros;
simpl in *.
induction l2;
simpl in *;
try congruence.
clear IHl2.
inversion H.
elim (
rec_field_lt_dec a a0);
intros.
elim (
rec_field_lt_dec b a1);
intros.
simpl.
rewrite H2;
rewrite H0;
rewrite H3;
reflexivity.
unfold rec_field_lt in *.
destruct a;
destruct a0;
destruct b;
destruct a1;
simpl in *.
subst.
congruence.
unfold rec_field_lt in *.
destruct a;
destruct a0;
destruct b;
destruct a1;
simpl in *.
subst.
inversion H.
destruct (
ODT_lt_dec k1 k2);
try congruence.
destruct (
ODT_lt_dec k2 k1);
try congruence;
simpl.
-
rewrite (
IHl1 l2 H1);
reflexivity.
-
rewrite H1;
reflexivity.
Qed.
Lemma same_domain_rec_sort {
A} {
B}
(
l1:
list (
K*
A)) (
l2:
list (
K*
B)) :
domain l1 =
domain l2 ->
domain (
rec_sort l1) =
domain (
rec_sort l2).
Proof.
Lemma insertion_sort_insert_nin_perm {
A:
Type}
l a :
~
In (
fst a) (@
domain _ A l) ->
Permutation (
a::
l) (
insertion_sort_insert rec_field_lt_dec a l).
Proof.
Lemma insertion_sort_perm_proper {
A:
Type} (
l l':
list (
K*
A))
a :
~
In (
fst a) (
domain l) ->
Permutation l l' ->
Permutation
(
insertion_sort_insert rec_field_lt_dec a l)
(
insertion_sort_insert rec_field_lt_dec a l').
Proof.
Lemma rec_sort_perm {
A:
Type}
l :
NoDup (@
domain _ A l) ->
Permutation l (
rec_sort l).
Proof.
Lemma insertion_sort_insert_insertion_nin {
A} (
a:
K*
A)
a0 l :
~
rec_field_lt a0 a ->
~
rec_field_lt a a0 ->
insertion_sort_insert rec_field_lt_dec a0
(
insertion_sort_insert rec_field_lt_dec a l)
=
insertion_sort_insert rec_field_lt_dec a l.
Proof.
Lemma insertion_sort_insert_cons_app {
A} (
a:
K*
A)
l l2 :
insertion_sort rec_field_lt_dec (
insertion_sort_insert rec_field_lt_dec a l ++
l2) =
insertion_sort rec_field_lt_dec (
a::
l ++
l2).
Proof.
Lemma insertion_sort_insertion_sort_app1 {
A}
l1 l2 :
insertion_sort rec_field_lt_dec (
insertion_sort (@
rec_field_lt_dec A)
l1 ++
l2) =
insertion_sort rec_field_lt_dec (
l1 ++
l2).
Proof.
Lemma insertion_sort_insertion_sort_app {
A}
l1 l2 l3 :
insertion_sort rec_field_lt_dec (
l1 ++
insertion_sort (@
rec_field_lt_dec A)
l2 ++
l3) =
insertion_sort rec_field_lt_dec (
l1 ++
l2 ++
l3).
Proof.
Lemma insertion_sort_eq_app1 {
A l1 l1'}
l2 :
insertion_sort (@
rec_field_lt_dec A)
l1 =
insertion_sort rec_field_lt_dec l1' ->
insertion_sort rec_field_lt_dec (
l1 ++
l2) =
insertion_sort rec_field_lt_dec (
l1' ++
l2).
Proof.
Lemma rec_sort_rec_sort_app1 {
A}
l1 l2 :
rec_sort ((@
rec_sort A)
l1 ++
l2) =
rec_sort (
l1 ++
l2).
Proof.
Lemma rec_sort_rec_sort_app {
A}
l1 l2 l3 :
rec_sort (
l1 ++ (@
rec_sort A)
l2 ++
l3) =
rec_sort (
l1 ++
l2 ++
l3).
Proof.
Lemma rec_sort_rec_sort_app2 {
A}
l1 l2 :
rec_sort (
l1 ++ (@
rec_sort A)
l2) =
rec_sort (
l1 ++
l2).
Proof.
Lemma rec_sort_eq_app1 {
A l1 l1'}
l2 :
(@
rec_sort A)
l1 =
rec_sort l1' ->
rec_sort (
l1 ++
l2) =
rec_sort (
l1' ++
l2).
Proof.
Lemma rec_cons_sort_Forall2 {
A B}
P l1 l2 a b :
Forall2 P l1 l2 ->
P a b ->
(
domain l1) = (
domain l2) ->
fst a =
fst b ->
Forall2 P
(
insertion_sort_insert (@
rec_field_lt_dec A)
a l1)
(
insertion_sort_insert (@
rec_field_lt_dec B)
b l2).
Proof.
Lemma rec_sort_Forall2 {
A B}
P l1 l2 :
(
domain l1) = (
domain l2) ->
Forall2 P l1 l2 ->
Forall2 P (@
rec_sort A l1) (@
rec_sort B l2).
Proof.
Lemma rec_concat_sort_nil_r {
A}
g :
@
rec_concat_sort A g nil =
rec_sort g.
Proof.
Lemma rec_concat_sort_nil_l {
A}
g :
@
rec_concat_sort A nil g =
rec_sort g.
Proof.
Lemma drec_sort_idempotent {
A}
l : @
rec_sort A (
rec_sort l) =
rec_sort l.
Proof.
Lemma insertion_sort_insert_equiv_domain {
A:
Type}
x a (
l:
list (
K*
A)) :
In x
(
domain (
RSort.insertion_sort_insert rec_field_lt_dec a l)) <->
fst a =
x \/
In x (
domain l).
Proof.
induction l;
simpl; [
intuition|].
destruct a;
destruct a0;
simpl in *.
destruct (
ODT_lt_dec k k0);
simpl; [
intuition|].
destruct (
ODT_lt_dec k0 k);
simpl;
intuition.
subst;
clear H.
destruct (
trichotemy x k0);
intuition.
Qed.
Lemma drec_sort_equiv_domain {
A}
l :
equivlist (
domain (@
rec_sort A l)) (
domain l).
Proof.
Hint Resolve ODT_lt_strorder.
Lemma insertion_sort_insert_swap_neq {
A}
a1 (
b1:
A)
a2 b2 l :
~(
eq a1 a2) ->
insertion_sort_insert rec_field_lt_dec (
a1,
b1)
(
insertion_sort_insert rec_field_lt_dec
(
a2,
b2)
l) =
insertion_sort_insert rec_field_lt_dec (
a2,
b2)
(
insertion_sort_insert rec_field_lt_dec
(
a1,
b1)
l).
Proof.
revert a1 b1 a2 b2.
induction l;
simpl;
intros.
-
destruct (
ODT_lt_dec a1 a2);
destruct (
ODT_lt_dec a2 a1);
trivial.
+
eelim @
asymmetry;
eauto.
unfold Asymmetric;
intros.
apply (@
asymmetry _ _ _ x y);
assumption.
+
destruct (
trichotemy a1 a2)
as [[?|?]|?];
intuition.
-
destruct a;
simpl.
Ltac t :=
try (
solve[
eelim @
asymmetry;
eauto]);
intuition.
repeat dest_strlt;
intuition;
try solve[
rewrite o0 in *;
t
|
destruct (
trichotemy a1 a2)
as [[?|?]|?];
intuition].
rewrite o0 in o2.
dest_strlt.
rewrite IHl; [
reflexivity|
assumption].
Qed.
Lemma insertion_sort_insert_middle {
A}
l1 l2 a (
b:
A) :
~
In a (
domain l1) ->
RSort.insertion_sort_insert rec_field_lt_dec (
a,
b)
(
RSort.insertion_sort rec_field_lt_dec (
l1 ++
l2)) =
RSort.insertion_sort rec_field_lt_dec (
l1 ++ (
a,
b) ::
l2).
Proof.
revert l2 a b.
induction l1;
simpl;
trivial;
intros.
intuition.
rewrite <-
IHl1;
auto.
destruct a;
simpl in *.
apply insertion_sort_insert_swap_neq;
auto.
Qed.
Lemma drec_sort_perm_eq {
A}
l l' :
NoDup (@
domain _ A l) ->
Permutation l l' ->
rec_sort l =
rec_sort l'.
Proof.
Lemma drec_sorted_perm_eq {
A :
Type} (
l l' :
list (
K *
A)) :
is_list_sorted ODT_lt_dec (
domain l) =
true ->
is_list_sorted ODT_lt_dec (
domain l') =
true ->
Permutation l l' ->
l =
l'.
Proof.
Lemma drec_concat_sort_app_comm {
A}
l l':
NoDup (@
domain _ A (
l ++
l')) ->
rec_concat_sort l l' =
rec_concat_sort l'
l.
Proof.
Lemma in_dom_rec_sort {
B} {
l x}:
In x (
domain (
rec_sort l)) <->
In x (@
domain _ B l).
Proof.
Lemma drec_sort_sorted {
A}
l :
RSort.is_list_sorted ODT_lt_dec
(@
domain _ A
(
rec_sort l)) =
true.
Proof.
Lemma drec_concat_sort_sorted {
A}
l l' :
RSort.is_list_sorted ODT_lt_dec
(@
domain _ A
(
rec_concat_sort l l')) =
true.
Proof.
Lemma drec_sort_drec_sort_concat {
A}
l l' :
(
rec_sort (@
rec_concat_sort A l l')) =
rec_concat_sort l l'.
Proof.
Lemma assoc_lookupr_insertion_sort_insert_neq {
B:
Type}
a x (
b:
B)
l :
~(
eq x a)->
assoc_lookupr ODT_eqdec
(
RSort.insertion_sort_insert rec_field_lt_dec (
a,
b)
l)
x
=
assoc_lookupr ODT_eqdec l x.
Proof.
Lemma assoc_lookupr_insertion_sort_fresh {
B:
Type}
x (
d:
B)
b :
~
In x (
domain b) ->
assoc_lookupr ODT_eqdec
(
RSort.insertion_sort rec_field_lt_dec (
b ++ (
x,
d) ::
nil))
x =
Some d.
Proof.
Lemma is_list_sorted_NoDup_strlt {
A}
l :
is_list_sorted ODT_lt_dec (@
domain _ A l) =
true ->
NoDup (
domain l).
Proof.
Lemma rec_sort_self_cons_middle {
A} (
l:
list (
K*
A)) (
a:
K*
A):
is_list_sorted ODT_lt_dec (
domain (
a::
l)) =
true ->
rec_sort (
l ++
a ::
l) =
rec_sort ((
a ::
l) ++
l).
Proof.
Lemma rec_field_anti {
A}
a:
~ (@
rec_field_lt A)
a a.
Proof.
Lemma lt_not_not k1 k2:
~
ODT_lt k1 k2 -> ~
ODT_lt k2 k1 ->
eq k1 k2.
Proof.
unfold not;
intros.
generalize (
trichotemy k1 k2);
intros.
inversion H1.
elim H2;
intros.
congruence.
assumption.
congruence.
Qed.
Lemma rec_concat_sort_self {
A} (
l:
list (
K*
A)):
is_list_sorted ODT_lt_dec (
domain l) =
true ->
rec_concat_sort l l =
l.
Proof.
Lemma insert_first_into_app {
A} (
l l0:
list (
K*
A)) (
a:
K*
A):
is_list_sorted ODT_lt_dec (
domain (
a ::
l)) =
true ->
rec_sort (
l ++
insertion_sort_insert rec_field_lt_dec a (
rec_sort (
l ++
l0))) =
insertion_sort_insert rec_field_lt_dec a (
rec_sort (
l ++
rec_sort (
l ++
l0))).
Proof.
Lemma rec_concat_sort_idem {
A} (
l l0:
list (
K*
A)):
is_list_sorted ODT_lt_dec (
domain l) =
true ->
is_list_sorted ODT_lt_dec (
domain l0) =
true ->
rec_concat_sort l (
rec_concat_sort l l0) =
rec_concat_sort l l0.
Proof.
Instance In_equivlist_proper {
A}:
Proper (
eq ==>
equivlist ==>
iff) (@
In A).
Proof.
Lemma assoc_lookupr_insert B s (
d:
B)
l x :
assoc_lookupr ODT_eqdec
(
RSort.insertion_sort_insert rec_field_lt_dec (
s,
d)
l)
x =
match assoc_lookupr ODT_eqdec l x with
|
Some d' =>
Some d'
|
None =>
if ODT_eqdec x s then Some d else None
end.
Proof.
Lemma assoc_lookupr_drec_sort {
A}
l x :
assoc_lookupr ODT_eqdec (@
rec_sort A l)
x =
assoc_lookupr ODT_eqdec l x.
Proof.
revert x.
induction l;
simpl;
trivial;
intros.
destruct a;
simpl.
rewrite assoc_lookupr_insert,
IHl.
trivial.
Qed.
Lemma assoc_lookupr_drec_sort_app_nin {
A}
l l'
x:
~
In x (
domain l') ->
assoc_lookupr ODT_eqdec (@
rec_sort A (
l ++
l'))
x
=
assoc_lookupr ODT_eqdec (
rec_sort l)
x.
Proof.
Lemma insertion_sort_insert_domain {
B:
Type}
x a (
b:
B)
l :
In x (
domain
(
RSort.insertion_sort_insert rec_field_lt_dec
(
a,
b)
l)) ->
a =
x \/
In x (
domain l).
Proof.
revert x a b.
induction l;
simpl;
intuition.
destruct (
ODT_lt_dec a a0);
simpl in *; [
intuition|].
destruct (
ODT_lt_dec a0 a);
simpl in *; [|
intuition].
intuition.
destruct (
IHl _ _ _ H0);
auto.
Qed.
Lemma drec_sort_domain {
A}
x l :
In x (
domain (@
rec_sort A l)) ->
In x (
domain l).
Proof.
Lemma drec_concat_sort_pullout {
A}
b x xv y yv :
NoDup (
x::
y::(
domain b)) ->
(@
rec_concat_sort A (
rec_concat_sort b ((
x,
xv) ::
nil))
((
y,
yv) ::
nil))
=
(
rec_concat_sort (
rec_concat_sort b ((
y,
yv) ::
nil))
((
x,
xv) ::
nil)).
Proof.
Lemma sorted_cons_filter_in_domain {
A} (
l l':
list (
K*
A))
f a :
filter f l =
a ::
l' ->
In a l.
Proof.
induction l; intros.
simpl in H; congruence.
simpl in *.
destruct (f a0).
- inversion H; left; reflexivity.
- right; apply (IHl H).
Qed.
Lemma filter_choice {
A} (
l:
list(
K*
A))
f:
filter f l =
nil \/ (
exists a,
exists l',
filter f l =
a ::
l').
Proof.
induction l.
left;
reflexivity.
simpl in *.
elim IHl;
clear IHl;
intros.
rewrite H.
destruct (
f a).
right;
exists a;
exists nil;
reflexivity.
left;
reflexivity.
elim H;
clear H;
intros.
elim H;
clear H;
intros.
rewrite H.
destruct (
f a).
right;
exists a;
exists (
x ::
x0);
reflexivity.
right;
exists x;
exists x0;
reflexivity.
Qed.
Lemma sorted_over_filter {
A} (
l:
list (
K*
A))
f:
is_list_sorted ODT_lt_dec (
domain l) =
true ->
is_list_sorted ODT_lt_dec (
domain (
filter f l)) =
true.
Proof.
intros.
induction l.
reflexivity.
simpl.
case_eq (
f a);
intros.
-
generalize (
filter_choice l f);
intros.
elim H1;
clear H1;
intros.
+
rewrite H1 in *.
reflexivity.
+
elim H1;
clear H1;
intros.
elim H1;
clear H1;
intros.
rewrite H1 in *.
assert (
In x l)
by (
apply (
sorted_cons_filter_in_domain l x0 f);
assumption).
assert (
ODT_lt (
fst a) (
fst x))
by (
apply (
sorted_cons_in l a x);
assumption).
apply rec_cons_lt.
apply IHl.
simpl in H.
destruct (
domain l).
reflexivity.
destruct (
ODT_lt_dec (
fst a)
k);
try congruence;
assumption.
assumption.
-
apply IHl.
simpl in H.
destruct (
domain l).
reflexivity.
destruct (
ODT_lt_dec (
fst a)
k).
assumption.
congruence.
Qed.
Lemma rec_sort_insert_filter_fst_true {
A:
Type}
f
(
a:
K*
A) (
l:
list (
K*
A))
(
fstonly:
forall a b c,
f (
a,
b) =
f (
a,
c)) :
StronglySorted rec_field_lt l ->
f a =
true ->
filter f (
insertion_sort_insert rec_field_lt_dec a l)
=
insertion_sort_insert rec_field_lt_dec a (
filter f l).
Proof.
revert a.
induction l;
simpl;
intros b lsort fb.
-
rewrite fb;
trivial.
-
inversion lsort;
subst.
case_eq (
f a);
simpl;
intros fa.
+
destruct (
rec_field_lt_dec b a);
simpl.
*
rewrite fb.
simpl.
match_destr.
*
rewrite <-
IHl;
trivial.
match_destr;
simpl;
rewrite fa;
trivial.
+
match_destr.
*
simpl.
rewrite fb,
fa.
rewrite insertion_sort_insert_forall_lt;
trivial.
apply Forall_filter.
revert H2.
apply Forall_impl_in;
intros.
etransitivity;
eauto.
*
rewrite <-
IHl;
trivial.
match_destr;
simpl;
rewrite fa;
trivial.
unfold rec_field_lt in *.
destruct (
trichotemy (
fst a) (
fst b))
as [[?|?]|?];
try congruence.
destruct a;
destruct b;
simpl in *;
subst.
specialize (
fstonly k0 a a0).
congruence.
Qed.
Lemma rec_sort_insert_filter_fst_false {
A:
Type}
f
(
a:
K*
A) (
l:
list (
K*
A))
(
fstonly:
forall a b c,
f (
a,
b) =
f (
a,
c)) :
f a =
false ->
filter f (
insertion_sort_insert rec_field_lt_dec a l) =
filter f l.
Proof.
revert a.
induction l; simpl; intros ? fa.
- rewrite fa; trivial.
- match_destr; simpl.
+ rewrite fa; trivial.
+ match_destr; simpl.
rewrite IHl; trivial.
Qed.
Lemma rec_sort_filter_fst_commute {
A:
Type}
f (
l:
list (
K*
A))
(
fstonly:
forall a b c,
f (
a,
b) =
f (
a,
c)) :
filter f (
rec_sort l)
=
rec_sort (
filter f l).
Proof.
Lemma forallb_rec_sort {
A}
f (
l:
list (
K*
A)) :
forallb f l =
true ->
forallb f (
rec_sort l) =
true.
Proof.
Lemma forallb_rec_sort_inv {
A}
f (
l:
list (
K*
A)) :
NoDup (
domain l) ->
forallb f (
rec_sort l) =
true ->
forallb f l =
true.
Proof.
Lemma domain_rec_sort_insert {
B} (
a:
K*
B)
l :
domain (
insertion_sort_insert rec_field_lt_dec a l) =
insertion_sort_insert ODT_lt_dec (
fst a) (
domain l).
Proof.
revert a.
induction l; simpl; trivial; intros.
destruct a; destruct a0.
simpl.
match_destr.
match_destr.
simpl. rewrite IHl; trivial.
Qed.
Lemma domain_rec_sort {
B} (
l:
list (
K*
B)) :
domain (
rec_sort l) =
insertion_sort ODT_lt_dec (
domain l).
Proof.
Lemma is_list_sorted_domain_rec_field {
B} (
l:
list (
K*
B)) :
is_list_sorted rec_field_lt_dec l
=
is_list_sorted ODT_lt_dec (
domain l).
Proof.
induction l; simpl; trivial.
match_destr.
destruct a; destruct p; simpl.
match_destr.
Qed.
Lemma rec_sort_insert_in_dom {
B}
a (
l:
list (
K*
B)) :
In (
fst a) (
domain l) ->
is_list_sorted ODT_lt_dec (
domain l) =
true ->
insertion_sort_insert rec_field_lt_dec a l =
l.
Proof.
induction l.
-
intuition.
-
intros.
destruct a;
destruct a0;
simpl.
simpl in H.
destruct H.
+
subst.
match_destr.
apply ODT_lt_irr in o.
intuition.
+
rewrite IHl;
trivial.
{
match_destr.
-
assert (
is_list_sorted ODT_lt_dec (
domain ((
k,
b)::(
k0,
b0) ::
l)) =
true).
+
simpl;
match_destr;
intuition.
+
eapply is_list_sorted_NoDup_strlt in H1.
simpl in H1.
inversion H1;
subst.
elim H4.
simpl;
intuition.
-
match_destr.
}
apply is_list_sorted_cons_inv in H0;
trivial.
Qed.
Lemma rec_sort_filter_latter_from_former {
B}
s (
l1 l2:
list (
K*
B)) :
In s (
domain l2) ->
rec_sort (
l1 ++
l2) =
rec_sort (
filter (
fun x :
K *
B =>
s <>
b fst x)
l1 ++
l2).
Proof.
Section Forall.
Lemma Forall_sorted {
A} (
P:(
K*
A) ->
Prop) (
l:
list (
K*
A)):
Forall P l ->
Forall P (
rec_sort l).
Proof.
End Forall.
Section CompatSort.
Require Import RCompat.
Lemma compatible_app_compatible {
A} `{
EqDec A eq} {
l1 l2:
list (
K*
A)} :
is_list_sorted ODT_lt_dec (
domain l1) =
true ->
is_list_sorted ODT_lt_dec (
domain l2) =
true ->
compatible l1 l2 =
true ->
compatible (
l1++
l2) (
l1++
l2) =
true.
Proof.
Lemma compatible_asymmetric_over {
A} `{
EqDec A eq} {
l:
list(
K*
A)} :
compatible l l =
true ->
asymmetric_over rec_field_lt l.
Proof.
Lemma compatible_sort_equivlist {
A} `{
EqDec A eq} {
l:
list(
K*
A)} :
compatible l l =
true ->
equivlist l (
rec_sort l).
Proof.
End CompatSort.
Section sublist.
Lemma sublist_rec_concat_sort_bounded {
A}
r srl :
incl (
domain r) (
domain srl) ->
domain (@
rec_concat_sort A r srl) =
domain (
rec_sort srl).
Proof.
Lemma domain_rec_concat_sort_app_comm:
forall (
A :
Type) (
l l' :
list (
K *
A)),
domain (
rec_concat_sort l l') =
domain (
rec_concat_sort l'
l).
Proof.
Lemma incl_sort_sublist {
A B}
a b :
incl (@
domain _ A a) (@
domain _ B b) ->
sublist (
domain (
rec_sort a)) (
domain (
rec_sort b)).
Proof.
Lemma rec_concat_sort_sublist {
B}
l1 l2 :
sublist (@
domain _ B (
rec_sort l1)) (
domain (
rec_concat_sort l1 l2)).
Proof.
Lemma rec_concat_sort_sublist_sorted {
B}
l1 l2 :
is_list_sorted ODT_lt_dec (
domain l1) =
true ->
sublist (@
domain _ B l1) (
domain (
rec_concat_sort l1 l2)).
Proof.
End sublist.
Section rev.
Lemma lookup_rev_rec_sort {
B} (
x:
K) (
l:
list (
K*
B)) :
lookup ODT_eqdec (
rev (
rec_sort l))
x =
lookup ODT_eqdec (
rec_sort l)
x.
Proof.
End rev.
End RBindings.
Section map.
Lemma map_rec_sort {
A B C D} `{
odta:
ODT A} `{
odtb:
ODT B} (
f:
A*
C->
B*
D) (
l:
list(
A*
C))
(
consistent:
forall x y,
rec_field_lt x y <->
rec_field_lt (
f x) (
f y)) :
map f (
rec_sort l) =
rec_sort (
map f l).
Proof.
End map.
Section RBindingsString.
Require Import String RString.
Global Program Instance ODT_string : (@
ODT string)
:=
mkODT _ _ StringOrder.lt _ StringOrder.lt_dec StringOrder.compare StringOrder.compare_spec.
End RBindingsString.
Hint Unfold rec_sort rec_concat_sort.
Hint Resolve drec_sort_sorted drec_concat_sort_sorted.
Hint Resolve is_list_sorted_NoDup_strlt.