author | haftmann |
Sat, 20 Oct 2012 10:00:21 +0200 | |
changeset 49949 | be3dd2e602e8 |
parent 49948 | 744934b818c7 |
child 49950 | cd882d53ba6b |
permissions | -rw-r--r-- |
31596 | 1 |
(* Author: Florian Haftmann, TU Muenchen *) |
26348 | 2 |
|
3 |
header {* Finite types as explicit enumerations *} |
|
4 |
||
5 |
theory Enum |
|
40650
d40b347d5b0b
adding Enum to HOL-Main image and removing it from HOL-Library
bulwahn
parents:
40649
diff
changeset
|
6 |
imports Map String |
26348 | 7 |
begin |
8 |
||
9 |
subsection {* Class @{text enum} *} |
|
10 |
||
29797 | 11 |
class enum = |
26348 | 12 |
fixes enum :: "'a list" |
41078
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
13 |
fixes enum_all :: "('a \<Rightarrow> bool) \<Rightarrow> bool" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
14 |
fixes enum_ex :: "('a \<Rightarrow> bool) \<Rightarrow> bool" |
33635 | 15 |
assumes UNIV_enum: "UNIV = set enum" |
26444 | 16 |
and enum_distinct: "distinct enum" |
41078
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
17 |
assumes enum_all : "enum_all P = (\<forall> x. P x)" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
18 |
assumes enum_ex : "enum_ex P = (\<exists> x. P x)" |
26348 | 19 |
begin |
20 |
||
29797 | 21 |
subclass finite proof |
22 |
qed (simp add: UNIV_enum) |
|
26444 | 23 |
|
41078
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
24 |
lemma enum_UNIV: "set enum = UNIV" unfolding UNIV_enum .. |
26444 | 25 |
|
40683 | 26 |
lemma in_enum: "x \<in> set enum" |
41078
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
27 |
unfolding enum_UNIV by auto |
26348 | 28 |
|
29 |
lemma enum_eq_I: |
|
30 |
assumes "\<And>x. x \<in> set xs" |
|
31 |
shows "set enum = set xs" |
|
32 |
proof - |
|
33 |
from assms UNIV_eq_I have "UNIV = set xs" by auto |
|
41078
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
34 |
with enum_UNIV show ?thesis by simp |
26348 | 35 |
qed |
36 |
||
37 |
end |
|
38 |
||
39 |
||
49949 | 40 |
subsection {* Implementations using @{class enum} *} |
41 |
||
42 |
subsubsection {* Unbounded operations and quantifiers *} |
|
43 |
||
44 |
lemma Collect_code [code]: |
|
45 |
"Collect P = set (filter P enum)" |
|
46 |
by (auto simp add: enum_UNIV) |
|
47 |
||
48 |
definition card_UNIV :: "'a itself \<Rightarrow> nat" |
|
49 |
where |
|
50 |
[code del]: "card_UNIV TYPE('a) = card (UNIV :: 'a set)" |
|
51 |
||
52 |
lemma [code]: |
|
53 |
"card_UNIV TYPE('a :: enum) = card (set (Enum.enum :: 'a list))" |
|
54 |
by (simp only: card_UNIV_def enum_UNIV) |
|
55 |
||
56 |
lemma all_code [code]: "(\<forall>x. P x) \<longleftrightarrow> enum_all P" |
|
57 |
by (simp add: enum_all) |
|
58 |
||
59 |
lemma exists_code [code]: "(\<exists>x. P x) \<longleftrightarrow> enum_ex P" |
|
60 |
by (simp add: enum_ex) |
|
61 |
||
62 |
lemma exists1_code [code]: "(\<exists>!x. P x) \<longleftrightarrow> list_ex1 P enum" |
|
63 |
by (auto simp add: enum_UNIV list_ex1_iff) |
|
64 |
||
65 |
||
66 |
subsubsection {* An executable choice operator *} |
|
67 |
||
68 |
definition |
|
69 |
[code del]: "enum_the = The" |
|
70 |
||
71 |
lemma [code]: |
|
72 |
"The P = (case filter P enum of [x] => x | _ => enum_the P)" |
|
73 |
proof - |
|
74 |
{ |
|
75 |
fix a |
|
76 |
assume filter_enum: "filter P enum = [a]" |
|
77 |
have "The P = a" |
|
78 |
proof (rule the_equality) |
|
79 |
fix x |
|
80 |
assume "P x" |
|
81 |
show "x = a" |
|
82 |
proof (rule ccontr) |
|
83 |
assume "x \<noteq> a" |
|
84 |
from filter_enum obtain us vs |
|
85 |
where enum_eq: "enum = us @ [a] @ vs" |
|
86 |
and "\<forall> x \<in> set us. \<not> P x" |
|
87 |
and "\<forall> x \<in> set vs. \<not> P x" |
|
88 |
and "P a" |
|
89 |
by (auto simp add: filter_eq_Cons_iff) (simp only: filter_empty_conv[symmetric]) |
|
90 |
with `P x` in_enum[of x, unfolded enum_eq] `x \<noteq> a` show "False" by auto |
|
91 |
qed |
|
92 |
next |
|
93 |
from filter_enum show "P a" by (auto simp add: filter_eq_Cons_iff) |
|
94 |
qed |
|
95 |
} |
|
96 |
from this show ?thesis |
|
97 |
unfolding enum_the_def by (auto split: list.split) |
|
98 |
qed |
|
99 |
||
100 |
code_abort enum_the |
|
101 |
code_const enum_the (Eval "(fn p => raise Match)") |
|
102 |
||
103 |
||
104 |
subsubsection {* Equality and order on functions *} |
|
26348 | 105 |
|
38857
97775f3e8722
renamed class/constant eq to equal; tuned some instantiations
haftmann
parents:
37765
diff
changeset
|
106 |
instantiation "fun" :: (enum, equal) equal |
26513 | 107 |
begin |
26348 | 108 |
|
26513 | 109 |
definition |
38857
97775f3e8722
renamed class/constant eq to equal; tuned some instantiations
haftmann
parents:
37765
diff
changeset
|
110 |
"HOL.equal f g \<longleftrightarrow> (\<forall>x \<in> set enum. f x = g x)" |
26513 | 111 |
|
31464 | 112 |
instance proof |
41078
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
113 |
qed (simp_all add: equal_fun_def enum_UNIV fun_eq_iff) |
26513 | 114 |
|
115 |
end |
|
26348 | 116 |
|
40898
882e860a1e83
changed order of lemmas to overwrite the general code equation with the nbe-specific one
bulwahn
parents:
40683
diff
changeset
|
117 |
lemma [code]: |
41078
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
118 |
"HOL.equal f g \<longleftrightarrow> enum_all (%x. f x = g x)" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
119 |
by (auto simp add: equal enum_all fun_eq_iff) |
40898
882e860a1e83
changed order of lemmas to overwrite the general code equation with the nbe-specific one
bulwahn
parents:
40683
diff
changeset
|
120 |
|
38857
97775f3e8722
renamed class/constant eq to equal; tuned some instantiations
haftmann
parents:
37765
diff
changeset
|
121 |
lemma [code nbe]: |
97775f3e8722
renamed class/constant eq to equal; tuned some instantiations
haftmann
parents:
37765
diff
changeset
|
122 |
"HOL.equal (f :: _ \<Rightarrow> _) f \<longleftrightarrow> True" |
97775f3e8722
renamed class/constant eq to equal; tuned some instantiations
haftmann
parents:
37765
diff
changeset
|
123 |
by (fact equal_refl) |
97775f3e8722
renamed class/constant eq to equal; tuned some instantiations
haftmann
parents:
37765
diff
changeset
|
124 |
|
28562 | 125 |
lemma order_fun [code]: |
26348 | 126 |
fixes f g :: "'a\<Colon>enum \<Rightarrow> 'b\<Colon>order" |
41078
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
127 |
shows "f \<le> g \<longleftrightarrow> enum_all (\<lambda>x. f x \<le> g x)" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
128 |
and "f < g \<longleftrightarrow> f \<le> g \<and> enum_ex (\<lambda>x. f x \<noteq> g x)" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
129 |
by (simp_all add: enum_all enum_ex fun_eq_iff le_fun_def order_less_le) |
26968 | 130 |
|
131 |
||
49949 | 132 |
subsubsection {* Operations on relations *} |
133 |
||
134 |
lemma [code]: |
|
135 |
"Id = image (\<lambda>x. (x, x)) (set Enum.enum)" |
|
136 |
by (auto intro: imageI in_enum) |
|
26968 | 137 |
|
49949 | 138 |
lemma tranclp_unfold [code, no_atp]: |
139 |
"tranclp r a b \<longleftrightarrow> (a, b) \<in> trancl {(x, y). r x y}" |
|
140 |
by (simp add: trancl_def) |
|
141 |
||
142 |
lemma rtranclp_rtrancl_eq [code, no_atp]: |
|
143 |
"rtranclp r x y \<longleftrightarrow> (x, y) \<in> rtrancl {(x, y). r x y}" |
|
144 |
by (simp add: rtrancl_def) |
|
26968 | 145 |
|
49949 | 146 |
lemma max_ext_eq [code]: |
147 |
"max_ext R = {(X, Y). finite X \<and> finite Y \<and> Y \<noteq> {} \<and> (\<forall>x. x \<in> X \<longrightarrow> (\<exists>xa \<in> Y. (x, xa) \<in> R))}" |
|
148 |
by (auto simp add: max_ext.simps) |
|
149 |
||
150 |
lemma max_extp_eq [code]: |
|
151 |
"max_extp r x y \<longleftrightarrow> (x, y) \<in> max_ext {(x, y). r x y}" |
|
152 |
by (simp add: max_ext_def) |
|
26348 | 153 |
|
49949 | 154 |
lemma mlex_eq [code]: |
155 |
"f <*mlex*> R = {(x, y). f x < f y \<or> (f x \<le> f y \<and> (x, y) \<in> R)}" |
|
156 |
by (auto simp add: mlex_prod_def) |
|
157 |
||
158 |
lemma [code]: |
|
159 |
fixes xs :: "('a::finite \<times> 'a) list" |
|
160 |
shows "acc (set xs) = bacc (set xs) (card_UNIV TYPE('a))" |
|
161 |
by (simp add: card_UNIV_def acc_bacc_eq) |
|
162 |
||
163 |
lemma [code]: |
|
164 |
"accp r = (\<lambda>x. x \<in> acc {(x, y). r x y})" |
|
165 |
by (simp add: acc_def) |
|
40652 | 166 |
|
26348 | 167 |
|
49949 | 168 |
subsection {* Default instances for @{class enum} *} |
26348 | 169 |
|
26444 | 170 |
lemma map_of_zip_enum_is_Some: |
171 |
assumes "length ys = length (enum \<Colon> 'a\<Colon>enum list)" |
|
172 |
shows "\<exists>y. map_of (zip (enum \<Colon> 'a\<Colon>enum list) ys) x = Some y" |
|
173 |
proof - |
|
174 |
from assms have "x \<in> set (enum \<Colon> 'a\<Colon>enum list) \<longleftrightarrow> |
|
175 |
(\<exists>y. map_of (zip (enum \<Colon> 'a\<Colon>enum list) ys) x = Some y)" |
|
176 |
by (auto intro!: map_of_zip_is_Some) |
|
41078
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
177 |
then show ?thesis using enum_UNIV by auto |
26444 | 178 |
qed |
179 |
||
180 |
lemma map_of_zip_enum_inject: |
|
181 |
fixes xs ys :: "'b\<Colon>enum list" |
|
182 |
assumes length: "length xs = length (enum \<Colon> 'a\<Colon>enum list)" |
|
183 |
"length ys = length (enum \<Colon> 'a\<Colon>enum list)" |
|
184 |
and map_of: "the \<circ> map_of (zip (enum \<Colon> 'a\<Colon>enum list) xs) = the \<circ> map_of (zip (enum \<Colon> 'a\<Colon>enum list) ys)" |
|
185 |
shows "xs = ys" |
|
186 |
proof - |
|
187 |
have "map_of (zip (enum \<Colon> 'a list) xs) = map_of (zip (enum \<Colon> 'a list) ys)" |
|
188 |
proof |
|
189 |
fix x :: 'a |
|
190 |
from length map_of_zip_enum_is_Some obtain y1 y2 |
|
191 |
where "map_of (zip (enum \<Colon> 'a list) xs) x = Some y1" |
|
192 |
and "map_of (zip (enum \<Colon> 'a list) ys) x = Some y2" by blast |
|
47230 | 193 |
moreover from map_of |
194 |
have "the (map_of (zip (enum \<Colon> 'a\<Colon>enum list) xs) x) = the (map_of (zip (enum \<Colon> 'a\<Colon>enum list) ys) x)" |
|
26444 | 195 |
by (auto dest: fun_cong) |
196 |
ultimately show "map_of (zip (enum \<Colon> 'a\<Colon>enum list) xs) x = map_of (zip (enum \<Colon> 'a\<Colon>enum list) ys) x" |
|
197 |
by simp |
|
198 |
qed |
|
199 |
with length enum_distinct show "xs = ys" by (rule map_of_zip_inject) |
|
200 |
qed |
|
201 |
||
41078
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
202 |
definition |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
203 |
all_n_lists :: "(('a :: enum) list \<Rightarrow> bool) \<Rightarrow> nat \<Rightarrow> bool" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
204 |
where |
49948
744934b818c7
moved quite generic material from theory Enum to more appropriate places
haftmann
parents:
48123
diff
changeset
|
205 |
"all_n_lists P n = (\<forall>xs \<in> set (List.n_lists n enum). P xs)" |
41078
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
206 |
|
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
207 |
lemma [code]: |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
208 |
"all_n_lists P n = (if n = 0 then P [] else enum_all (%x. all_n_lists (%xs. P (x # xs)) (n - 1)))" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
209 |
unfolding all_n_lists_def enum_all |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
210 |
by (cases n) (auto simp add: enum_UNIV) |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
211 |
|
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
212 |
definition |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
213 |
ex_n_lists :: "(('a :: enum) list \<Rightarrow> bool) \<Rightarrow> nat \<Rightarrow> bool" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
214 |
where |
49948
744934b818c7
moved quite generic material from theory Enum to more appropriate places
haftmann
parents:
48123
diff
changeset
|
215 |
"ex_n_lists P n = (\<exists>xs \<in> set (List.n_lists n enum). P xs)" |
41078
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
216 |
|
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
217 |
lemma [code]: |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
218 |
"ex_n_lists P n = (if n = 0 then P [] else enum_ex (%x. ex_n_lists (%xs. P (x # xs)) (n - 1)))" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
219 |
unfolding ex_n_lists_def enum_ex |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
220 |
by (cases n) (auto simp add: enum_UNIV) |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
221 |
|
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
222 |
|
26444 | 223 |
instantiation "fun" :: (enum, enum) enum |
224 |
begin |
|
225 |
||
226 |
definition |
|
49948
744934b818c7
moved quite generic material from theory Enum to more appropriate places
haftmann
parents:
48123
diff
changeset
|
227 |
"enum = map (\<lambda>ys. the o map_of (zip (enum\<Colon>'a list) ys)) (List.n_lists (length (enum\<Colon>'a\<Colon>enum list)) enum)" |
26444 | 228 |
|
41078
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
229 |
definition |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
230 |
"enum_all P = all_n_lists (\<lambda>bs. P (the o map_of (zip enum bs))) (length (enum :: 'a list))" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
231 |
|
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
232 |
definition |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
233 |
"enum_ex P = ex_n_lists (\<lambda>bs. P (the o map_of (zip enum bs))) (length (enum :: 'a list))" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
234 |
|
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
235 |
|
26444 | 236 |
instance proof |
237 |
show "UNIV = set (enum \<Colon> ('a \<Rightarrow> 'b) list)" |
|
238 |
proof (rule UNIV_eq_I) |
|
239 |
fix f :: "'a \<Rightarrow> 'b" |
|
240 |
have "f = the \<circ> map_of (zip (enum \<Colon> 'a\<Colon>enum list) (map f enum))" |
|
40683 | 241 |
by (auto simp add: map_of_zip_map fun_eq_iff intro: in_enum) |
26444 | 242 |
then show "f \<in> set enum" |
40683 | 243 |
by (auto simp add: enum_fun_def set_n_lists intro: in_enum) |
26444 | 244 |
qed |
245 |
next |
|
246 |
from map_of_zip_enum_inject |
|
247 |
show "distinct (enum \<Colon> ('a \<Rightarrow> 'b) list)" |
|
248 |
by (auto intro!: inj_onI simp add: enum_fun_def |
|
249 |
distinct_map distinct_n_lists enum_distinct set_n_lists enum_all) |
|
41078
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
250 |
next |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
251 |
fix P |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
252 |
show "enum_all (P :: ('a \<Rightarrow> 'b) \<Rightarrow> bool) = (\<forall>x. P x)" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
253 |
proof |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
254 |
assume "enum_all P" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
255 |
show "\<forall>x. P x" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
256 |
proof |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
257 |
fix f :: "'a \<Rightarrow> 'b" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
258 |
have f: "f = the \<circ> map_of (zip (enum \<Colon> 'a\<Colon>enum list) (map f enum))" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
259 |
by (auto simp add: map_of_zip_map fun_eq_iff intro: in_enum) |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
260 |
from `enum_all P` have "P (the \<circ> map_of (zip enum (map f enum)))" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
261 |
unfolding enum_all_fun_def all_n_lists_def |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
262 |
apply (simp add: set_n_lists) |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
263 |
apply (erule_tac x="map f enum" in allE) |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
264 |
apply (auto intro!: in_enum) |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
265 |
done |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
266 |
from this f show "P f" by auto |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
267 |
qed |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
268 |
next |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
269 |
assume "\<forall>x. P x" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
270 |
from this show "enum_all P" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
271 |
unfolding enum_all_fun_def all_n_lists_def by auto |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
272 |
qed |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
273 |
next |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
274 |
fix P |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
275 |
show "enum_ex (P :: ('a \<Rightarrow> 'b) \<Rightarrow> bool) = (\<exists>x. P x)" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
276 |
proof |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
277 |
assume "enum_ex P" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
278 |
from this show "\<exists>x. P x" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
279 |
unfolding enum_ex_fun_def ex_n_lists_def by auto |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
280 |
next |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
281 |
assume "\<exists>x. P x" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
282 |
from this obtain f where "P f" .. |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
283 |
have f: "f = the \<circ> map_of (zip (enum \<Colon> 'a\<Colon>enum list) (map f enum))" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
284 |
by (auto simp add: map_of_zip_map fun_eq_iff intro: in_enum) |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
285 |
from `P f` this have "P (the \<circ> map_of (zip (enum \<Colon> 'a\<Colon>enum list) (map f enum)))" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
286 |
by auto |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
287 |
from this show "enum_ex P" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
288 |
unfolding enum_ex_fun_def ex_n_lists_def |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
289 |
apply (auto simp add: set_n_lists) |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
290 |
apply (rule_tac x="map f enum" in exI) |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
291 |
apply (auto intro!: in_enum) |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
292 |
done |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
293 |
qed |
26444 | 294 |
qed |
295 |
||
296 |
end |
|
297 |
||
38857
97775f3e8722
renamed class/constant eq to equal; tuned some instantiations
haftmann
parents:
37765
diff
changeset
|
298 |
lemma enum_fun_code [code]: "enum = (let enum_a = (enum \<Colon> 'a\<Colon>{enum, equal} list) |
49948
744934b818c7
moved quite generic material from theory Enum to more appropriate places
haftmann
parents:
48123
diff
changeset
|
299 |
in map (\<lambda>ys. the o map_of (zip enum_a ys)) (List.n_lists (length enum_a) enum))" |
28245
9767dd8e1e54
celver code lemma avoid type ambiguity problem with Haskell
haftmann
parents:
27487
diff
changeset
|
300 |
by (simp add: enum_fun_def Let_def) |
26444 | 301 |
|
41078
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
302 |
lemma enum_all_fun_code [code]: |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
303 |
"enum_all P = (let enum_a = (enum :: 'a::{enum, equal} list) |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
304 |
in all_n_lists (\<lambda>bs. P (the o map_of (zip enum_a bs))) (length enum_a))" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
305 |
by (simp add: enum_all_fun_def Let_def) |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
306 |
|
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
307 |
lemma enum_ex_fun_code [code]: |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
308 |
"enum_ex P = (let enum_a = (enum :: 'a::{enum, equal} list) |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
309 |
in ex_n_lists (\<lambda>bs. P (the o map_of (zip enum_a bs))) (length enum_a))" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
310 |
by (simp add: enum_ex_fun_def Let_def) |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
311 |
|
26348 | 312 |
instantiation unit :: enum |
313 |
begin |
|
314 |
||
315 |
definition |
|
316 |
"enum = [()]" |
|
317 |
||
41078
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
318 |
definition |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
319 |
"enum_all P = P ()" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
320 |
|
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
321 |
definition |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
322 |
"enum_ex P = P ()" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
323 |
|
31464 | 324 |
instance proof |
41078
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
325 |
qed (auto simp add: enum_unit_def UNIV_unit enum_all_unit_def enum_ex_unit_def intro: unit.exhaust) |
26348 | 326 |
|
327 |
end |
|
328 |
||
329 |
instantiation bool :: enum |
|
330 |
begin |
|
331 |
||
332 |
definition |
|
333 |
"enum = [False, True]" |
|
334 |
||
41078
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
335 |
definition |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
336 |
"enum_all P = (P False \<and> P True)" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
337 |
|
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
338 |
definition |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
339 |
"enum_ex P = (P False \<or> P True)" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
340 |
|
31464 | 341 |
instance proof |
41078
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
342 |
fix P |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
343 |
show "enum_all (P :: bool \<Rightarrow> bool) = (\<forall>x. P x)" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
344 |
unfolding enum_all_bool_def by (auto, case_tac x) auto |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
345 |
next |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
346 |
fix P |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
347 |
show "enum_ex (P :: bool \<Rightarrow> bool) = (\<exists>x. P x)" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
348 |
unfolding enum_ex_bool_def by (auto, case_tac x) auto |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
349 |
qed (auto simp add: enum_bool_def UNIV_bool) |
26348 | 350 |
|
351 |
end |
|
352 |
||
37678
0040bafffdef
"prod" and "sum" replace "*" and "+" respectively
haftmann
parents:
37601
diff
changeset
|
353 |
instantiation prod :: (enum, enum) enum |
26348 | 354 |
begin |
355 |
||
356 |
definition |
|
49948
744934b818c7
moved quite generic material from theory Enum to more appropriate places
haftmann
parents:
48123
diff
changeset
|
357 |
"enum = List.product enum enum" |
26348 | 358 |
|
41078
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
359 |
definition |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
360 |
"enum_all P = enum_all (%x. enum_all (%y. P (x, y)))" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
361 |
|
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
362 |
definition |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
363 |
"enum_ex P = enum_ex (%x. enum_ex (%y. P (x, y)))" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
364 |
|
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
365 |
|
26348 | 366 |
instance by default |
41078
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
367 |
(simp_all add: enum_prod_def product_list_set distinct_product |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
368 |
enum_UNIV enum_distinct enum_all_prod_def enum_all enum_ex_prod_def enum_ex) |
26348 | 369 |
|
370 |
end |
|
371 |
||
37678
0040bafffdef
"prod" and "sum" replace "*" and "+" respectively
haftmann
parents:
37601
diff
changeset
|
372 |
instantiation sum :: (enum, enum) enum |
26348 | 373 |
begin |
374 |
||
375 |
definition |
|
376 |
"enum = map Inl enum @ map Inr enum" |
|
377 |
||
41078
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
378 |
definition |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
379 |
"enum_all P = (enum_all (%x. P (Inl x)) \<and> enum_all (%x. P (Inr x)))" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
380 |
|
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
381 |
definition |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
382 |
"enum_ex P = (enum_ex (%x. P (Inl x)) \<or> enum_ex (%x. P (Inr x)))" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
383 |
|
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
384 |
instance proof |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
385 |
fix P |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
386 |
show "enum_all (P :: ('a + 'b) \<Rightarrow> bool) = (\<forall>x. P x)" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
387 |
unfolding enum_all_sum_def enum_all |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
388 |
by (auto, case_tac x) auto |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
389 |
next |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
390 |
fix P |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
391 |
show "enum_ex (P :: ('a + 'b) \<Rightarrow> bool) = (\<exists>x. P x)" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
392 |
unfolding enum_ex_sum_def enum_ex |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
393 |
by (auto, case_tac x) auto |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
394 |
qed (auto simp add: enum_UNIV enum_sum_def, case_tac x, auto intro: inj_onI simp add: distinct_map enum_distinct) |
26348 | 395 |
|
396 |
end |
|
397 |
||
398 |
instantiation nibble :: enum |
|
399 |
begin |
|
400 |
||
401 |
definition |
|
402 |
"enum = [Nibble0, Nibble1, Nibble2, Nibble3, Nibble4, Nibble5, Nibble6, Nibble7, |
|
403 |
Nibble8, Nibble9, NibbleA, NibbleB, NibbleC, NibbleD, NibbleE, NibbleF]" |
|
404 |
||
41078
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
405 |
definition |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
406 |
"enum_all P = (P Nibble0 \<and> P Nibble1 \<and> P Nibble2 \<and> P Nibble3 \<and> P Nibble4 \<and> P Nibble5 \<and> P Nibble6 \<and> P Nibble7 |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
407 |
\<and> P Nibble8 \<and> P Nibble9 \<and> P NibbleA \<and> P NibbleB \<and> P NibbleC \<and> P NibbleD \<and> P NibbleE \<and> P NibbleF)" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
408 |
|
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
409 |
definition |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
410 |
"enum_ex P = (P Nibble0 \<or> P Nibble1 \<or> P Nibble2 \<or> P Nibble3 \<or> P Nibble4 \<or> P Nibble5 \<or> P Nibble6 \<or> P Nibble7 |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
411 |
\<or> P Nibble8 \<or> P Nibble9 \<or> P NibbleA \<or> P NibbleB \<or> P NibbleC \<or> P NibbleD \<or> P NibbleE \<or> P NibbleF)" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
412 |
|
31464 | 413 |
instance proof |
41078
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
414 |
fix P |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
415 |
show "enum_all (P :: nibble \<Rightarrow> bool) = (\<forall>x. P x)" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
416 |
unfolding enum_all_nibble_def |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
417 |
by (auto, case_tac x) auto |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
418 |
next |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
419 |
fix P |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
420 |
show "enum_ex (P :: nibble \<Rightarrow> bool) = (\<exists>x. P x)" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
421 |
unfolding enum_ex_nibble_def |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
422 |
by (auto, case_tac x) auto |
31464 | 423 |
qed (simp_all add: enum_nibble_def UNIV_nibble) |
26348 | 424 |
|
425 |
end |
|
426 |
||
427 |
instantiation char :: enum |
|
428 |
begin |
|
429 |
||
430 |
definition |
|
49948
744934b818c7
moved quite generic material from theory Enum to more appropriate places
haftmann
parents:
48123
diff
changeset
|
431 |
"enum = map (split Char) (List.product enum enum)" |
26444 | 432 |
|
31482 | 433 |
lemma enum_chars [code]: |
434 |
"enum = chars" |
|
435 |
unfolding enum_char_def chars_def enum_nibble_def by simp |
|
26348 | 436 |
|
41078
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
437 |
definition |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
438 |
"enum_all P = list_all P chars" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
439 |
|
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
440 |
definition |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
441 |
"enum_ex P = list_ex P chars" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
442 |
|
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
443 |
lemma set_enum_char: "set (enum :: char list) = UNIV" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
444 |
by (auto intro: char.exhaust simp add: enum_char_def product_list_set enum_UNIV full_SetCompr_eq [symmetric]) |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
445 |
|
31464 | 446 |
instance proof |
41078
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
447 |
fix P |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
448 |
show "enum_all (P :: char \<Rightarrow> bool) = (\<forall>x. P x)" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
449 |
unfolding enum_all_char_def enum_chars[symmetric] |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
450 |
by (auto simp add: list_all_iff set_enum_char) |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
451 |
next |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
452 |
fix P |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
453 |
show "enum_ex (P :: char \<Rightarrow> bool) = (\<exists>x. P x)" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
454 |
unfolding enum_ex_char_def enum_chars[symmetric] |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
455 |
by (auto simp add: list_ex_iff set_enum_char) |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
456 |
next |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
457 |
show "distinct (enum :: char list)" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
458 |
by (auto intro: inj_onI simp add: enum_char_def product_list_set distinct_map distinct_product enum_distinct) |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
459 |
qed (auto simp add: set_enum_char) |
26348 | 460 |
|
461 |
end |
|
462 |
||
29024 | 463 |
instantiation option :: (enum) enum |
464 |
begin |
|
465 |
||
466 |
definition |
|
467 |
"enum = None # map Some enum" |
|
468 |
||
41078
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
469 |
definition |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
470 |
"enum_all P = (P None \<and> enum_all (%x. P (Some x)))" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
471 |
|
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
472 |
definition |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
473 |
"enum_ex P = (P None \<or> enum_ex (%x. P (Some x)))" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
474 |
|
31464 | 475 |
instance proof |
41078
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
476 |
fix P |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
477 |
show "enum_all (P :: 'a option \<Rightarrow> bool) = (\<forall>x. P x)" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
478 |
unfolding enum_all_option_def enum_all |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
479 |
by (auto, case_tac x) auto |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
480 |
next |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
481 |
fix P |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
482 |
show "enum_ex (P :: 'a option \<Rightarrow> bool) = (\<exists>x. P x)" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
483 |
unfolding enum_ex_option_def enum_ex |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
484 |
by (auto, case_tac x) auto |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
485 |
qed (auto simp add: enum_UNIV enum_option_def, rule option.exhaust, auto intro: simp add: distinct_map enum_distinct) |
45963
1c7e6454883e
enum type class instance for `set`; dropped misfitting code lemma for trancl
haftmann
parents:
45144
diff
changeset
|
486 |
end |
1c7e6454883e
enum type class instance for `set`; dropped misfitting code lemma for trancl
haftmann
parents:
45144
diff
changeset
|
487 |
|
1c7e6454883e
enum type class instance for `set`; dropped misfitting code lemma for trancl
haftmann
parents:
45144
diff
changeset
|
488 |
instantiation set :: (enum) enum |
1c7e6454883e
enum type class instance for `set`; dropped misfitting code lemma for trancl
haftmann
parents:
45144
diff
changeset
|
489 |
begin |
1c7e6454883e
enum type class instance for `set`; dropped misfitting code lemma for trancl
haftmann
parents:
45144
diff
changeset
|
490 |
|
1c7e6454883e
enum type class instance for `set`; dropped misfitting code lemma for trancl
haftmann
parents:
45144
diff
changeset
|
491 |
definition |
1c7e6454883e
enum type class instance for `set`; dropped misfitting code lemma for trancl
haftmann
parents:
45144
diff
changeset
|
492 |
"enum = map set (sublists enum)" |
1c7e6454883e
enum type class instance for `set`; dropped misfitting code lemma for trancl
haftmann
parents:
45144
diff
changeset
|
493 |
|
1c7e6454883e
enum type class instance for `set`; dropped misfitting code lemma for trancl
haftmann
parents:
45144
diff
changeset
|
494 |
definition |
1c7e6454883e
enum type class instance for `set`; dropped misfitting code lemma for trancl
haftmann
parents:
45144
diff
changeset
|
495 |
"enum_all P \<longleftrightarrow> (\<forall>A\<in>set enum. P (A::'a set))" |
1c7e6454883e
enum type class instance for `set`; dropped misfitting code lemma for trancl
haftmann
parents:
45144
diff
changeset
|
496 |
|
1c7e6454883e
enum type class instance for `set`; dropped misfitting code lemma for trancl
haftmann
parents:
45144
diff
changeset
|
497 |
definition |
1c7e6454883e
enum type class instance for `set`; dropped misfitting code lemma for trancl
haftmann
parents:
45144
diff
changeset
|
498 |
"enum_ex P \<longleftrightarrow> (\<exists>A\<in>set enum. P (A::'a set))" |
1c7e6454883e
enum type class instance for `set`; dropped misfitting code lemma for trancl
haftmann
parents:
45144
diff
changeset
|
499 |
|
1c7e6454883e
enum type class instance for `set`; dropped misfitting code lemma for trancl
haftmann
parents:
45144
diff
changeset
|
500 |
instance proof |
1c7e6454883e
enum type class instance for `set`; dropped misfitting code lemma for trancl
haftmann
parents:
45144
diff
changeset
|
501 |
qed (simp_all add: enum_set_def enum_all_set_def enum_ex_set_def sublists_powset distinct_set_sublists |
1c7e6454883e
enum type class instance for `set`; dropped misfitting code lemma for trancl
haftmann
parents:
45144
diff
changeset
|
502 |
enum_distinct enum_UNIV) |
29024 | 503 |
|
504 |
end |
|
505 |
||
45963
1c7e6454883e
enum type class instance for `set`; dropped misfitting code lemma for trancl
haftmann
parents:
45144
diff
changeset
|
506 |
|
40647 | 507 |
subsection {* Small finite types *} |
508 |
||
509 |
text {* We define small finite types for the use in Quickcheck *} |
|
510 |
||
511 |
datatype finite_1 = a\<^isub>1 |
|
512 |
||
40900
1d5f76d79856
adding shorter output syntax for the finite types of quickcheck
bulwahn
parents:
40898
diff
changeset
|
513 |
notation (output) a\<^isub>1 ("a\<^isub>1") |
1d5f76d79856
adding shorter output syntax for the finite types of quickcheck
bulwahn
parents:
40898
diff
changeset
|
514 |
|
40647 | 515 |
instantiation finite_1 :: enum |
516 |
begin |
|
517 |
||
518 |
definition |
|
519 |
"enum = [a\<^isub>1]" |
|
520 |
||
41078
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
521 |
definition |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
522 |
"enum_all P = P a\<^isub>1" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
523 |
|
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
524 |
definition |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
525 |
"enum_ex P = P a\<^isub>1" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
526 |
|
40647 | 527 |
instance proof |
41078
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
528 |
fix P |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
529 |
show "enum_all (P :: finite_1 \<Rightarrow> bool) = (\<forall>x. P x)" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
530 |
unfolding enum_all_finite_1_def |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
531 |
by (auto, case_tac x) auto |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
532 |
next |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
533 |
fix P |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
534 |
show "enum_ex (P :: finite_1 \<Rightarrow> bool) = (\<exists>x. P x)" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
535 |
unfolding enum_ex_finite_1_def |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
536 |
by (auto, case_tac x) auto |
40647 | 537 |
qed (auto simp add: enum_finite_1_def intro: finite_1.exhaust) |
538 |
||
29024 | 539 |
end |
40647 | 540 |
|
40651
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
541 |
instantiation finite_1 :: linorder |
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
542 |
begin |
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
543 |
|
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
544 |
definition less_eq_finite_1 :: "finite_1 \<Rightarrow> finite_1 \<Rightarrow> bool" |
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
545 |
where |
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
546 |
"less_eq_finite_1 x y = True" |
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
547 |
|
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
548 |
definition less_finite_1 :: "finite_1 \<Rightarrow> finite_1 \<Rightarrow> bool" |
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
549 |
where |
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
550 |
"less_finite_1 x y = False" |
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
551 |
|
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
552 |
instance |
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
553 |
apply (intro_classes) |
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
554 |
apply (auto simp add: less_finite_1_def less_eq_finite_1_def) |
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
555 |
apply (metis finite_1.exhaust) |
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
556 |
done |
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
557 |
|
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
558 |
end |
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
559 |
|
41085
a549ff1d4070
adding a smarter enumeration scheme for finite functions
bulwahn
parents:
41078
diff
changeset
|
560 |
hide_const (open) a\<^isub>1 |
40657 | 561 |
|
40647 | 562 |
datatype finite_2 = a\<^isub>1 | a\<^isub>2 |
563 |
||
40900
1d5f76d79856
adding shorter output syntax for the finite types of quickcheck
bulwahn
parents:
40898
diff
changeset
|
564 |
notation (output) a\<^isub>1 ("a\<^isub>1") |
1d5f76d79856
adding shorter output syntax for the finite types of quickcheck
bulwahn
parents:
40898
diff
changeset
|
565 |
notation (output) a\<^isub>2 ("a\<^isub>2") |
1d5f76d79856
adding shorter output syntax for the finite types of quickcheck
bulwahn
parents:
40898
diff
changeset
|
566 |
|
40647 | 567 |
instantiation finite_2 :: enum |
568 |
begin |
|
569 |
||
570 |
definition |
|
571 |
"enum = [a\<^isub>1, a\<^isub>2]" |
|
572 |
||
41078
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
573 |
definition |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
574 |
"enum_all P = (P a\<^isub>1 \<and> P a\<^isub>2)" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
575 |
|
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
576 |
definition |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
577 |
"enum_ex P = (P a\<^isub>1 \<or> P a\<^isub>2)" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
578 |
|
40647 | 579 |
instance proof |
41078
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
580 |
fix P |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
581 |
show "enum_all (P :: finite_2 \<Rightarrow> bool) = (\<forall>x. P x)" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
582 |
unfolding enum_all_finite_2_def |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
583 |
by (auto, case_tac x) auto |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
584 |
next |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
585 |
fix P |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
586 |
show "enum_ex (P :: finite_2 \<Rightarrow> bool) = (\<exists>x. P x)" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
587 |
unfolding enum_ex_finite_2_def |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
588 |
by (auto, case_tac x) auto |
40647 | 589 |
qed (auto simp add: enum_finite_2_def intro: finite_2.exhaust) |
590 |
||
591 |
end |
|
592 |
||
40651
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
593 |
instantiation finite_2 :: linorder |
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
594 |
begin |
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
595 |
|
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
596 |
definition less_finite_2 :: "finite_2 \<Rightarrow> finite_2 \<Rightarrow> bool" |
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
597 |
where |
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
598 |
"less_finite_2 x y = ((x = a\<^isub>1) & (y = a\<^isub>2))" |
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
599 |
|
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
600 |
definition less_eq_finite_2 :: "finite_2 \<Rightarrow> finite_2 \<Rightarrow> bool" |
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
601 |
where |
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
602 |
"less_eq_finite_2 x y = ((x = y) \<or> (x < y))" |
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
603 |
|
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
604 |
|
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
605 |
instance |
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
606 |
apply (intro_classes) |
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
607 |
apply (auto simp add: less_finite_2_def less_eq_finite_2_def) |
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
608 |
apply (metis finite_2.distinct finite_2.nchotomy)+ |
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
609 |
done |
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
610 |
|
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
611 |
end |
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
612 |
|
41085
a549ff1d4070
adding a smarter enumeration scheme for finite functions
bulwahn
parents:
41078
diff
changeset
|
613 |
hide_const (open) a\<^isub>1 a\<^isub>2 |
40657 | 614 |
|
40651
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
615 |
|
40647 | 616 |
datatype finite_3 = a\<^isub>1 | a\<^isub>2 | a\<^isub>3 |
617 |
||
40900
1d5f76d79856
adding shorter output syntax for the finite types of quickcheck
bulwahn
parents:
40898
diff
changeset
|
618 |
notation (output) a\<^isub>1 ("a\<^isub>1") |
1d5f76d79856
adding shorter output syntax for the finite types of quickcheck
bulwahn
parents:
40898
diff
changeset
|
619 |
notation (output) a\<^isub>2 ("a\<^isub>2") |
1d5f76d79856
adding shorter output syntax for the finite types of quickcheck
bulwahn
parents:
40898
diff
changeset
|
620 |
notation (output) a\<^isub>3 ("a\<^isub>3") |
1d5f76d79856
adding shorter output syntax for the finite types of quickcheck
bulwahn
parents:
40898
diff
changeset
|
621 |
|
40647 | 622 |
instantiation finite_3 :: enum |
623 |
begin |
|
624 |
||
625 |
definition |
|
626 |
"enum = [a\<^isub>1, a\<^isub>2, a\<^isub>3]" |
|
627 |
||
41078
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
628 |
definition |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
629 |
"enum_all P = (P a\<^isub>1 \<and> P a\<^isub>2 \<and> P a\<^isub>3)" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
630 |
|
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
631 |
definition |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
632 |
"enum_ex P = (P a\<^isub>1 \<or> P a\<^isub>2 \<or> P a\<^isub>3)" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
633 |
|
40647 | 634 |
instance proof |
41078
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
635 |
fix P |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
636 |
show "enum_all (P :: finite_3 \<Rightarrow> bool) = (\<forall>x. P x)" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
637 |
unfolding enum_all_finite_3_def |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
638 |
by (auto, case_tac x) auto |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
639 |
next |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
640 |
fix P |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
641 |
show "enum_ex (P :: finite_3 \<Rightarrow> bool) = (\<exists>x. P x)" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
642 |
unfolding enum_ex_finite_3_def |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
643 |
by (auto, case_tac x) auto |
40647 | 644 |
qed (auto simp add: enum_finite_3_def intro: finite_3.exhaust) |
645 |
||
646 |
end |
|
647 |
||
40651
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
648 |
instantiation finite_3 :: linorder |
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
649 |
begin |
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
650 |
|
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
651 |
definition less_finite_3 :: "finite_3 \<Rightarrow> finite_3 \<Rightarrow> bool" |
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
652 |
where |
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
653 |
"less_finite_3 x y = (case x of a\<^isub>1 => (y \<noteq> a\<^isub>1) |
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
654 |
| a\<^isub>2 => (y = a\<^isub>3)| a\<^isub>3 => False)" |
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
655 |
|
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
656 |
definition less_eq_finite_3 :: "finite_3 \<Rightarrow> finite_3 \<Rightarrow> bool" |
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
657 |
where |
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
658 |
"less_eq_finite_3 x y = ((x = y) \<or> (x < y))" |
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
659 |
|
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
660 |
|
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
661 |
instance proof (intro_classes) |
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
662 |
qed (auto simp add: less_finite_3_def less_eq_finite_3_def split: finite_3.split_asm) |
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
663 |
|
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
664 |
end |
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
665 |
|
41085
a549ff1d4070
adding a smarter enumeration scheme for finite functions
bulwahn
parents:
41078
diff
changeset
|
666 |
hide_const (open) a\<^isub>1 a\<^isub>2 a\<^isub>3 |
40657 | 667 |
|
40651
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
668 |
|
40647 | 669 |
datatype finite_4 = a\<^isub>1 | a\<^isub>2 | a\<^isub>3 | a\<^isub>4 |
670 |
||
40900
1d5f76d79856
adding shorter output syntax for the finite types of quickcheck
bulwahn
parents:
40898
diff
changeset
|
671 |
notation (output) a\<^isub>1 ("a\<^isub>1") |
1d5f76d79856
adding shorter output syntax for the finite types of quickcheck
bulwahn
parents:
40898
diff
changeset
|
672 |
notation (output) a\<^isub>2 ("a\<^isub>2") |
1d5f76d79856
adding shorter output syntax for the finite types of quickcheck
bulwahn
parents:
40898
diff
changeset
|
673 |
notation (output) a\<^isub>3 ("a\<^isub>3") |
1d5f76d79856
adding shorter output syntax for the finite types of quickcheck
bulwahn
parents:
40898
diff
changeset
|
674 |
notation (output) a\<^isub>4 ("a\<^isub>4") |
1d5f76d79856
adding shorter output syntax for the finite types of quickcheck
bulwahn
parents:
40898
diff
changeset
|
675 |
|
40647 | 676 |
instantiation finite_4 :: enum |
677 |
begin |
|
678 |
||
679 |
definition |
|
680 |
"enum = [a\<^isub>1, a\<^isub>2, a\<^isub>3, a\<^isub>4]" |
|
681 |
||
41078
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
682 |
definition |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
683 |
"enum_all P = (P a\<^isub>1 \<and> P a\<^isub>2 \<and> P a\<^isub>3 \<and> P a\<^isub>4)" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
684 |
|
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
685 |
definition |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
686 |
"enum_ex P = (P a\<^isub>1 \<or> P a\<^isub>2 \<or> P a\<^isub>3 \<or> P a\<^isub>4)" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
687 |
|
40647 | 688 |
instance proof |
41078
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
689 |
fix P |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
690 |
show "enum_all (P :: finite_4 \<Rightarrow> bool) = (\<forall>x. P x)" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
691 |
unfolding enum_all_finite_4_def |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
692 |
by (auto, case_tac x) auto |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
693 |
next |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
694 |
fix P |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
695 |
show "enum_ex (P :: finite_4 \<Rightarrow> bool) = (\<exists>x. P x)" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
696 |
unfolding enum_ex_finite_4_def |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
697 |
by (auto, case_tac x) auto |
40647 | 698 |
qed (auto simp add: enum_finite_4_def intro: finite_4.exhaust) |
699 |
||
700 |
end |
|
701 |
||
41085
a549ff1d4070
adding a smarter enumeration scheme for finite functions
bulwahn
parents:
41078
diff
changeset
|
702 |
hide_const (open) a\<^isub>1 a\<^isub>2 a\<^isub>3 a\<^isub>4 |
40651
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
703 |
|
9752ba7348b5
adding code equation for function equality; adding some instantiations for the finite types
bulwahn
parents:
40650
diff
changeset
|
704 |
|
40647 | 705 |
datatype finite_5 = a\<^isub>1 | a\<^isub>2 | a\<^isub>3 | a\<^isub>4 | a\<^isub>5 |
706 |
||
40900
1d5f76d79856
adding shorter output syntax for the finite types of quickcheck
bulwahn
parents:
40898
diff
changeset
|
707 |
notation (output) a\<^isub>1 ("a\<^isub>1") |
1d5f76d79856
adding shorter output syntax for the finite types of quickcheck
bulwahn
parents:
40898
diff
changeset
|
708 |
notation (output) a\<^isub>2 ("a\<^isub>2") |
1d5f76d79856
adding shorter output syntax for the finite types of quickcheck
bulwahn
parents:
40898
diff
changeset
|
709 |
notation (output) a\<^isub>3 ("a\<^isub>3") |
1d5f76d79856
adding shorter output syntax for the finite types of quickcheck
bulwahn
parents:
40898
diff
changeset
|
710 |
notation (output) a\<^isub>4 ("a\<^isub>4") |
1d5f76d79856
adding shorter output syntax for the finite types of quickcheck
bulwahn
parents:
40898
diff
changeset
|
711 |
notation (output) a\<^isub>5 ("a\<^isub>5") |
1d5f76d79856
adding shorter output syntax for the finite types of quickcheck
bulwahn
parents:
40898
diff
changeset
|
712 |
|
40647 | 713 |
instantiation finite_5 :: enum |
714 |
begin |
|
715 |
||
716 |
definition |
|
717 |
"enum = [a\<^isub>1, a\<^isub>2, a\<^isub>3, a\<^isub>4, a\<^isub>5]" |
|
718 |
||
41078
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
719 |
definition |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
720 |
"enum_all P = (P a\<^isub>1 \<and> P a\<^isub>2 \<and> P a\<^isub>3 \<and> P a\<^isub>4 \<and> P a\<^isub>5)" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
721 |
|
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
722 |
definition |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
723 |
"enum_ex P = (P a\<^isub>1 \<or> P a\<^isub>2 \<or> P a\<^isub>3 \<or> P a\<^isub>4 \<or> P a\<^isub>5)" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
724 |
|
40647 | 725 |
instance proof |
41078
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
726 |
fix P |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
727 |
show "enum_all (P :: finite_5 \<Rightarrow> bool) = (\<forall>x. P x)" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
728 |
unfolding enum_all_finite_5_def |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
729 |
by (auto, case_tac x) auto |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
730 |
next |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
731 |
fix P |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
732 |
show "enum_ex (P :: finite_5 \<Rightarrow> bool) = (\<exists>x. P x)" |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
733 |
unfolding enum_ex_finite_5_def |
051251fde456
adding more efficient implementations for quantifiers in Enum
bulwahn
parents:
40900
diff
changeset
|
734 |
by (auto, case_tac x) auto |
40647 | 735 |
qed (auto simp add: enum_finite_5_def intro: finite_5.exhaust) |
736 |
||
737 |
end |
|
738 |
||
46352
73b03235799a
an executable version of accessible part (only for finite types yet)
bulwahn
parents:
46336
diff
changeset
|
739 |
hide_const (open) a\<^isub>1 a\<^isub>2 a\<^isub>3 a\<^isub>4 a\<^isub>5 |
73b03235799a
an executable version of accessible part (only for finite types yet)
bulwahn
parents:
46336
diff
changeset
|
740 |
|
49948
744934b818c7
moved quite generic material from theory Enum to more appropriate places
haftmann
parents:
48123
diff
changeset
|
741 |
|
46352
73b03235799a
an executable version of accessible part (only for finite types yet)
bulwahn
parents:
46336
diff
changeset
|
742 |
subsection {* Closing up *} |
40657 | 743 |
|
41085
a549ff1d4070
adding a smarter enumeration scheme for finite functions
bulwahn
parents:
41078
diff
changeset
|
744 |
hide_type (open) finite_1 finite_2 finite_3 finite_4 finite_5 |
49948
744934b818c7
moved quite generic material from theory Enum to more appropriate places
haftmann
parents:
48123
diff
changeset
|
745 |
hide_const (open) enum enum_all enum_ex all_n_lists ex_n_lists ntrancl |
40647 | 746 |
|
747 |
end |
|
49948
744934b818c7
moved quite generic material from theory Enum to more appropriate places
haftmann
parents:
48123
diff
changeset
|
748 |