author | haftmann |
Thu, 20 May 2010 16:35:54 +0200 | |
changeset 37023 | efc202e1677e |
parent 36176 | 3fe7e97ccca8 |
child 37024 | e938a0b5286e |
permissions | -rw-r--r-- |
31807 | 1 |
|
2 |
(* Author: Florian Haftmann, TU Muenchen *) |
|
3 |
||
4 |
header {* Executable finite sets *} |
|
5 |
||
31849 | 6 |
theory Fset |
37023 | 7 |
imports List_Set More_List |
31807 | 8 |
begin |
9 |
||
31846 | 10 |
declare mem_def [simp] |
11 |
||
31807 | 12 |
subsection {* Lifting *} |
13 |
||
14 |
datatype 'a fset = Fset "'a set" |
|
15 |
||
16 |
primrec member :: "'a fset \<Rightarrow> 'a set" where |
|
17 |
"member (Fset A) = A" |
|
18 |
||
34048 | 19 |
lemma member_inject [simp]: |
20 |
"member A = member B \<Longrightarrow> A = B" |
|
21 |
by (cases A, cases B) simp |
|
22 |
||
31807 | 23 |
lemma Fset_member [simp]: |
24 |
"Fset (member A) = A" |
|
25 |
by (cases A) simp |
|
26 |
||
27 |
definition Set :: "'a list \<Rightarrow> 'a fset" where |
|
28 |
"Set xs = Fset (set xs)" |
|
29 |
||
30 |
lemma member_Set [simp]: |
|
31 |
"member (Set xs) = set xs" |
|
32 |
by (simp add: Set_def) |
|
33 |
||
32880 | 34 |
definition Coset :: "'a list \<Rightarrow> 'a fset" where |
35 |
"Coset xs = Fset (- set xs)" |
|
36 |
||
37 |
lemma member_Coset [simp]: |
|
38 |
"member (Coset xs) = - set xs" |
|
39 |
by (simp add: Coset_def) |
|
40 |
||
41 |
code_datatype Set Coset |
|
42 |
||
43 |
lemma member_code [code]: |
|
37023 | 44 |
"member (Set xs) = List.member xs" |
45 |
"member (Coset xs) = Not \<circ> List.member xs" |
|
46 |
by (simp_all add: expand_fun_eq mem_iff fun_Compl_def bool_Compl_def) |
|
32880 | 47 |
|
48 |
lemma member_image_UNIV [simp]: |
|
49 |
"member ` UNIV = UNIV" |
|
50 |
proof - |
|
51 |
have "\<And>A \<Colon> 'a set. \<exists>B \<Colon> 'a fset. A = member B" |
|
52 |
proof |
|
53 |
fix A :: "'a set" |
|
54 |
show "A = member (Fset A)" by simp |
|
55 |
qed |
|
56 |
then show ?thesis by (simp add: image_def) |
|
57 |
qed |
|
31807 | 58 |
|
59 |
||
34048 | 60 |
subsection {* Lattice instantiation *} |
61 |
||
62 |
instantiation fset :: (type) boolean_algebra |
|
63 |
begin |
|
64 |
||
65 |
definition less_eq_fset :: "'a fset \<Rightarrow> 'a fset \<Rightarrow> bool" where |
|
66 |
[simp]: "A \<le> B \<longleftrightarrow> member A \<subseteq> member B" |
|
67 |
||
68 |
definition less_fset :: "'a fset \<Rightarrow> 'a fset \<Rightarrow> bool" where |
|
69 |
[simp]: "A < B \<longleftrightarrow> member A \<subset> member B" |
|
70 |
||
71 |
definition inf_fset :: "'a fset \<Rightarrow> 'a fset \<Rightarrow> 'a fset" where |
|
72 |
[simp]: "inf A B = Fset (member A \<inter> member B)" |
|
73 |
||
74 |
definition sup_fset :: "'a fset \<Rightarrow> 'a fset \<Rightarrow> 'a fset" where |
|
75 |
[simp]: "sup A B = Fset (member A \<union> member B)" |
|
76 |
||
77 |
definition bot_fset :: "'a fset" where |
|
78 |
[simp]: "bot = Fset {}" |
|
79 |
||
80 |
definition top_fset :: "'a fset" where |
|
81 |
[simp]: "top = Fset UNIV" |
|
82 |
||
83 |
definition uminus_fset :: "'a fset \<Rightarrow> 'a fset" where |
|
84 |
[simp]: "- A = Fset (- (member A))" |
|
85 |
||
86 |
definition minus_fset :: "'a fset \<Rightarrow> 'a fset \<Rightarrow> 'a fset" where |
|
87 |
[simp]: "A - B = Fset (member A - member B)" |
|
88 |
||
89 |
instance proof |
|
90 |
qed auto |
|
91 |
||
92 |
end |
|
93 |
||
94 |
instantiation fset :: (type) complete_lattice |
|
95 |
begin |
|
96 |
||
97 |
definition Inf_fset :: "'a fset set \<Rightarrow> 'a fset" where |
|
98 |
[simp, code del]: "Inf_fset As = Fset (Inf (image member As))" |
|
99 |
||
100 |
definition Sup_fset :: "'a fset set \<Rightarrow> 'a fset" where |
|
101 |
[simp, code del]: "Sup_fset As = Fset (Sup (image member As))" |
|
102 |
||
103 |
instance proof |
|
104 |
qed (auto simp add: le_fun_def le_bool_def) |
|
105 |
||
106 |
end |
|
107 |
||
37023 | 108 |
|
31807 | 109 |
subsection {* Basic operations *} |
110 |
||
111 |
definition is_empty :: "'a fset \<Rightarrow> bool" where |
|
31846 | 112 |
[simp]: "is_empty A \<longleftrightarrow> List_Set.is_empty (member A)" |
31807 | 113 |
|
114 |
lemma is_empty_Set [code]: |
|
115 |
"is_empty (Set xs) \<longleftrightarrow> null xs" |
|
31846 | 116 |
by (simp add: is_empty_set) |
31807 | 117 |
|
34048 | 118 |
lemma empty_Set [code]: |
119 |
"bot = Set []" |
|
120 |
by simp |
|
31807 | 121 |
|
34048 | 122 |
lemma UNIV_Set [code]: |
123 |
"top = Coset []" |
|
124 |
by simp |
|
31807 | 125 |
|
126 |
definition insert :: "'a \<Rightarrow> 'a fset \<Rightarrow> 'a fset" where |
|
31846 | 127 |
[simp]: "insert x A = Fset (Set.insert x (member A))" |
31807 | 128 |
|
129 |
lemma insert_Set [code]: |
|
34976
06df18c9a091
generalized lemma foldl_apply_inv to foldl_apply
haftmann
parents:
34048
diff
changeset
|
130 |
"insert x (Set xs) = Set (List.insert x xs)" |
06df18c9a091
generalized lemma foldl_apply_inv to foldl_apply
haftmann
parents:
34048
diff
changeset
|
131 |
"insert x (Coset xs) = Coset (removeAll x xs)" |
37023 | 132 |
by (simp_all add: Set_def Coset_def) |
31807 | 133 |
|
134 |
definition remove :: "'a \<Rightarrow> 'a fset \<Rightarrow> 'a fset" where |
|
31846 | 135 |
[simp]: "remove x A = Fset (List_Set.remove x (member A))" |
31807 | 136 |
|
137 |
lemma remove_Set [code]: |
|
34976
06df18c9a091
generalized lemma foldl_apply_inv to foldl_apply
haftmann
parents:
34048
diff
changeset
|
138 |
"remove x (Set xs) = Set (removeAll x xs)" |
06df18c9a091
generalized lemma foldl_apply_inv to foldl_apply
haftmann
parents:
34048
diff
changeset
|
139 |
"remove x (Coset xs) = Coset (List.insert x xs)" |
06df18c9a091
generalized lemma foldl_apply_inv to foldl_apply
haftmann
parents:
34048
diff
changeset
|
140 |
by (simp_all add: Set_def Coset_def remove_set_compl) |
06df18c9a091
generalized lemma foldl_apply_inv to foldl_apply
haftmann
parents:
34048
diff
changeset
|
141 |
(simp add: List_Set.remove_def) |
31807 | 142 |
|
143 |
definition map :: "('a \<Rightarrow> 'b) \<Rightarrow> 'a fset \<Rightarrow> 'b fset" where |
|
31846 | 144 |
[simp]: "map f A = Fset (image f (member A))" |
31807 | 145 |
|
146 |
lemma map_Set [code]: |
|
147 |
"map f (Set xs) = Set (remdups (List.map f xs))" |
|
31846 | 148 |
by (simp add: Set_def) |
31807 | 149 |
|
31847 | 150 |
definition filter :: "('a \<Rightarrow> bool) \<Rightarrow> 'a fset \<Rightarrow> 'a fset" where |
151 |
[simp]: "filter P A = Fset (List_Set.project P (member A))" |
|
31807 | 152 |
|
31847 | 153 |
lemma filter_Set [code]: |
154 |
"filter P (Set xs) = Set (List.filter P xs)" |
|
31846 | 155 |
by (simp add: Set_def project_set) |
31807 | 156 |
|
157 |
definition forall :: "('a \<Rightarrow> bool) \<Rightarrow> 'a fset \<Rightarrow> bool" where |
|
31846 | 158 |
[simp]: "forall P A \<longleftrightarrow> Ball (member A) P" |
31807 | 159 |
|
160 |
lemma forall_Set [code]: |
|
161 |
"forall P (Set xs) \<longleftrightarrow> list_all P xs" |
|
31846 | 162 |
by (simp add: Set_def ball_set) |
31807 | 163 |
|
164 |
definition exists :: "('a \<Rightarrow> bool) \<Rightarrow> 'a fset \<Rightarrow> bool" where |
|
31846 | 165 |
[simp]: "exists P A \<longleftrightarrow> Bex (member A) P" |
31807 | 166 |
|
167 |
lemma exists_Set [code]: |
|
168 |
"exists P (Set xs) \<longleftrightarrow> list_ex P xs" |
|
31846 | 169 |
by (simp add: Set_def bex_set) |
170 |
||
31849 | 171 |
definition card :: "'a fset \<Rightarrow> nat" where |
172 |
[simp]: "card A = Finite_Set.card (member A)" |
|
173 |
||
174 |
lemma card_Set [code]: |
|
175 |
"card (Set xs) = length (remdups xs)" |
|
176 |
proof - |
|
177 |
have "Finite_Set.card (set (remdups xs)) = length (remdups xs)" |
|
178 |
by (rule distinct_card) simp |
|
37023 | 179 |
then show ?thesis by (simp add: Set_def) |
31849 | 180 |
qed |
181 |
||
37023 | 182 |
lemma compl_Set [simp, code]: |
183 |
"- Set xs = Coset xs" |
|
184 |
by (simp add: Set_def Coset_def) |
|
185 |
||
186 |
lemma compl_Coset [simp, code]: |
|
187 |
"- Coset xs = Set xs" |
|
188 |
by (simp add: Set_def Coset_def) |
|
189 |
||
31846 | 190 |
|
191 |
subsection {* Derived operations *} |
|
192 |
||
193 |
lemma subfset_eq_forall [code]: |
|
34048 | 194 |
"A \<le> B \<longleftrightarrow> forall (member B) A" |
31846 | 195 |
by (simp add: subset_eq) |
196 |
||
197 |
lemma subfset_subfset_eq [code]: |
|
34048 | 198 |
"A < B \<longleftrightarrow> A \<le> B \<and> \<not> B \<le> (A :: 'a fset)" |
199 |
by (fact less_le_not_le) |
|
31846 | 200 |
|
201 |
lemma eq_fset_subfset_eq [code]: |
|
34048 | 202 |
"eq_class.eq A B \<longleftrightarrow> A \<le> B \<and> B \<le> (A :: 'a fset)" |
31846 | 203 |
by (cases A, cases B) (simp add: eq set_eq) |
204 |
||
31807 | 205 |
|
206 |
subsection {* Functorial operations *} |
|
207 |
||
32880 | 208 |
lemma inter_project [code]: |
34048 | 209 |
"inf A (Set xs) = Set (List.filter (member A) xs)" |
37023 | 210 |
"inf A (Coset xs) = foldr remove xs A" |
31807 | 211 |
proof - |
34048 | 212 |
show "inf A (Set xs) = Set (List.filter (member A) xs)" |
32880 | 213 |
by (simp add: inter project_def Set_def) |
37023 | 214 |
have *: "\<And>x::'a. remove = (\<lambda>x. Fset \<circ> List_Set.remove x \<circ> member)" |
215 |
by (simp add: expand_fun_eq) |
|
216 |
have "member \<circ> fold (\<lambda>x. Fset \<circ> List_Set.remove x \<circ> member) xs = |
|
217 |
fold List_Set.remove xs \<circ> member" |
|
218 |
by (rule fold_apply) (simp add: expand_fun_eq) |
|
219 |
then have "fold List_Set.remove xs (member A) = |
|
220 |
member (fold (\<lambda>x. Fset \<circ> List_Set.remove x \<circ> member) xs A)" |
|
221 |
by (simp add: expand_fun_eq) |
|
222 |
then have "inf A (Coset xs) = fold remove xs A" |
|
223 |
by (simp add: Diff_eq [symmetric] minus_set *) |
|
224 |
moreover have "\<And>x y :: 'a. Fset.remove y \<circ> Fset.remove x = Fset.remove x \<circ> Fset.remove y" |
|
225 |
by (auto simp add: List_Set.remove_def * intro: ext) |
|
226 |
ultimately show "inf A (Coset xs) = foldr remove xs A" |
|
227 |
by (simp add: foldr_fold) |
|
31807 | 228 |
qed |
229 |
||
230 |
lemma subtract_remove [code]: |
|
37023 | 231 |
"A - Set xs = foldr remove xs A" |
34048 | 232 |
"A - Coset xs = Set (List.filter (member A) xs)" |
37023 | 233 |
by (simp_all only: diff_eq compl_Set compl_Coset inter_project) |
32880 | 234 |
|
235 |
lemma union_insert [code]: |
|
37023 | 236 |
"sup (Set xs) A = foldr insert xs A" |
34048 | 237 |
"sup (Coset xs) A = Coset (List.filter (Not \<circ> member A) xs)" |
32880 | 238 |
proof - |
37023 | 239 |
have *: "\<And>x::'a. insert = (\<lambda>x. Fset \<circ> Set.insert x \<circ> member)" |
240 |
by (simp add: expand_fun_eq) |
|
241 |
have "member \<circ> fold (\<lambda>x. Fset \<circ> Set.insert x \<circ> member) xs = |
|
242 |
fold Set.insert xs \<circ> member" |
|
243 |
by (rule fold_apply) (simp add: expand_fun_eq) |
|
244 |
then have "fold Set.insert xs (member A) = |
|
245 |
member (fold (\<lambda>x. Fset \<circ> Set.insert x \<circ> member) xs A)" |
|
246 |
by (simp add: expand_fun_eq) |
|
247 |
then have "sup (Set xs) A = fold insert xs A" |
|
248 |
by (simp add: union_set *) |
|
249 |
moreover have "\<And>x y :: 'a. Fset.insert y \<circ> Fset.insert x = Fset.insert x \<circ> Fset.insert y" |
|
250 |
by (auto simp add: * intro: ext) |
|
251 |
ultimately show "sup (Set xs) A = foldr insert xs A" |
|
252 |
by (simp add: foldr_fold) |
|
34048 | 253 |
show "sup (Coset xs) A = Coset (List.filter (Not \<circ> member A) xs)" |
32880 | 254 |
by (auto simp add: Coset_def) |
31807 | 255 |
qed |
256 |
||
34048 | 257 |
context complete_lattice |
258 |
begin |
|
31807 | 259 |
|
34048 | 260 |
definition Infimum :: "'a fset \<Rightarrow> 'a" where |
261 |
[simp]: "Infimum A = Inf (member A)" |
|
31807 | 262 |
|
34048 | 263 |
lemma Infimum_inf [code]: |
37023 | 264 |
"Infimum (Set As) = foldr inf As top" |
34048 | 265 |
"Infimum (Coset []) = bot" |
37023 | 266 |
by (simp_all add: Inf_set_foldr Inf_UNIV) |
31807 | 267 |
|
34048 | 268 |
definition Supremum :: "'a fset \<Rightarrow> 'a" where |
269 |
[simp]: "Supremum A = Sup (member A)" |
|
270 |
||
271 |
lemma Supremum_sup [code]: |
|
37023 | 272 |
"Supremum (Set As) = foldr sup As bot" |
34048 | 273 |
"Supremum (Coset []) = top" |
37023 | 274 |
by (simp_all add: Sup_set_foldr Sup_UNIV) |
34048 | 275 |
|
276 |
end |
|
31807 | 277 |
|
278 |
||
279 |
subsection {* Misc operations *} |
|
280 |
||
281 |
lemma size_fset [code]: |
|
282 |
"fset_size f A = 0" |
|
283 |
"size A = 0" |
|
284 |
by (cases A, simp) (cases A, simp) |
|
285 |
||
286 |
lemma fset_case_code [code]: |
|
287 |
"fset_case f A = f (member A)" |
|
288 |
by (cases A) simp |
|
289 |
||
290 |
lemma fset_rec_code [code]: |
|
291 |
"fset_rec f A = f (member A)" |
|
292 |
by (cases A) simp |
|
293 |
||
31846 | 294 |
|
295 |
subsection {* Simplified simprules *} |
|
296 |
||
297 |
lemma is_empty_simp [simp]: |
|
298 |
"is_empty A \<longleftrightarrow> member A = {}" |
|
299 |
by (simp add: List_Set.is_empty_def) |
|
300 |
declare is_empty_def [simp del] |
|
301 |
||
302 |
lemma remove_simp [simp]: |
|
303 |
"remove x A = Fset (member A - {x})" |
|
304 |
by (simp add: List_Set.remove_def) |
|
305 |
declare remove_def [simp del] |
|
306 |
||
31847 | 307 |
lemma filter_simp [simp]: |
308 |
"filter P A = Fset {x \<in> member A. P x}" |
|
31846 | 309 |
by (simp add: List_Set.project_def) |
31847 | 310 |
declare filter_def [simp del] |
31846 | 311 |
|
312 |
declare mem_def [simp del] |
|
313 |
||
31849 | 314 |
|
36176
3fe7e97ccca8
replaced generic 'hide' command by more conventional 'hide_class', 'hide_type', 'hide_const', 'hide_fact' -- frees some popular keywords;
wenzelm
parents:
34976
diff
changeset
|
315 |
hide_const (open) is_empty insert remove map filter forall exists card |
34048 | 316 |
Inter Union |
31849 | 317 |
|
31807 | 318 |
end |