1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
|
(************************************************************************)
(* v * The Coq Proof Assistant / The Coq Development Team *)
(* <O___,, * INRIA - CNRS - LIX - LRI - PPS - Copyright 1999-2015 *)
(* \VV/ **************************************************************)
(* // * This file is distributed under the terms of the *)
(* * GNU Lesser General Public License Version 2.1 *)
(************************************************************************)
(* Made by Hugo Herbelin *)
(** This file defines two notions of sorted list:
- a list is locally sorted if any element is smaller or equal than
its successor in the list
- a list is sorted if any element coming before another one is
smaller or equal than this other element
The two notions are equivalent if the order is transitive.
*)
Require Import List Relations Relations_1.
(* Set Universe Polymorphism. *)
(** Preambule *)
Set Implicit Arguments.
Local Notation "[ ]" := nil (at level 0).
Local Notation "[ a ; .. ; b ]" := (a :: .. (b :: []) ..) (at level 0).
Arguments Transitive [U] R.
Section defs.
Variable A : Type.
Variable R : A -> A -> Prop.
(** Locally sorted: consecutive elements of the list are ordered *)
Inductive LocallySorted : list A -> Prop :=
| LSorted_nil : LocallySorted []
| LSorted_cons1 a : LocallySorted [a]
| LSorted_consn a b l :
LocallySorted (b :: l) -> R a b -> LocallySorted (a :: b :: l).
(** Alternative two-step definition of being locally sorted *)
Inductive HdRel a : list A -> Prop :=
| HdRel_nil : HdRel a []
| HdRel_cons b l : R a b -> HdRel a (b :: l).
Inductive Sorted : list A -> Prop :=
| Sorted_nil : Sorted []
| Sorted_cons a l : Sorted l -> HdRel a l -> Sorted (a :: l).
Lemma HdRel_inv : forall a b l, HdRel a (b :: l) -> R a b.
Proof.
inversion 1; auto.
Qed.
Lemma Sorted_inv :
forall a l, Sorted (a :: l) -> Sorted l /\ HdRel a l.
Proof.
intros a l H; inversion H; auto.
Qed.
Lemma Sorted_rect :
forall P:list A -> Type,
P [] ->
(forall a l, Sorted l -> P l -> HdRel a l -> P (a :: l)) ->
forall l:list A, Sorted l -> P l.
Proof.
induction l. firstorder using Sorted_inv. firstorder using Sorted_inv.
Qed.
Lemma Sorted_LocallySorted_iff : forall l, Sorted l <-> LocallySorted l.
Proof.
split; [induction 1 as [|a l [|]]| induction 1];
auto using Sorted, LocallySorted, HdRel.
inversion H1; subst; auto using LocallySorted.
Qed.
(** Strongly sorted: elements of the list are pairwise ordered *)
Inductive StronglySorted : list A -> Prop :=
| SSorted_nil : StronglySorted []
| SSorted_cons a l : StronglySorted l -> Forall (R a) l -> StronglySorted (a :: l).
Lemma StronglySorted_inv : forall a l, StronglySorted (a :: l) ->
StronglySorted l /\ Forall (R a) l.
Proof.
intros; inversion H; auto.
Defined.
Lemma StronglySorted_rect :
forall P:list A -> Type,
P [] ->
(forall a l, StronglySorted l -> P l -> Forall (R a) l -> P (a :: l)) ->
forall l, StronglySorted l -> P l.
Proof.
induction l; firstorder using StronglySorted_inv.
Defined.
Lemma StronglySorted_rec :
forall P:list A -> Type,
P [] ->
(forall a l, StronglySorted l -> P l -> Forall (R a) l -> P (a :: l)) ->
forall l, StronglySorted l -> P l.
Proof.
firstorder using StronglySorted_rect.
Qed.
Lemma StronglySorted_Sorted : forall l, StronglySorted l -> Sorted l.
Proof.
induction 1 as [|? ? ? ? HForall]; constructor; trivial.
destruct HForall; constructor; trivial.
Qed.
Lemma Sorted_extends :
Transitive R -> forall a l, Sorted (a::l) -> Forall (R a) l.
Proof.
intros. change match a :: l with [] => True | a :: l => Forall (R a) l end.
induction H0 as [|? ? ? ? H1]; [trivial|].
destruct H1; constructor; trivial.
eapply Forall_impl; [|eassumption].
firstorder.
Qed.
Lemma Sorted_StronglySorted :
Transitive R -> forall l, Sorted l -> StronglySorted l.
Proof.
induction 2; constructor; trivial.
apply Sorted_extends; trivial.
constructor; trivial.
Qed.
End defs.
Hint Constructors HdRel.
Hint Constructors Sorted.
(* begin hide *)
(* Compatibility with deprecated file Sorting.v *)
Notation lelistA := HdRel (only parsing).
Notation nil_leA := HdRel_nil (only parsing).
Notation cons_leA := HdRel_cons (only parsing).
Notation sort := Sorted (only parsing).
Notation nil_sort := Sorted_nil (only parsing).
Notation cons_sort := Sorted_cons (only parsing).
Notation lelistA_inv := HdRel_inv (only parsing).
Notation sort_inv := Sorted_inv (only parsing).
Notation sort_rect := Sorted_rect (only parsing).
(* end hide *)
|
