72 definition |
72 definition |
73 rsp_fold :: "('a \<Rightarrow> 'b \<Rightarrow> 'b) \<Rightarrow> bool" |
73 rsp_fold :: "('a \<Rightarrow> 'b \<Rightarrow> 'b) \<Rightarrow> bool" |
74 where |
74 where |
75 "rsp_fold f \<longleftrightarrow> (\<forall>u v. f u \<circ> f v = f v \<circ> f u)" |
75 "rsp_fold f \<longleftrightarrow> (\<forall>u v. f u \<circ> f v = f v \<circ> f u)" |
76 |
76 |
|
77 lemma rsp_foldI: |
|
78 "(\<And>u v. f u \<circ> f v = f v \<circ> f u) \<Longrightarrow> rsp_fold f" |
|
79 by (simp add: rsp_fold_def) |
|
80 |
|
81 lemma rsp_foldE: |
|
82 assumes "rsp_fold f" |
|
83 obtains "f u \<circ> f v = f v \<circ> f u" |
|
84 using assms by (simp add: rsp_fold_def) |
|
85 |
77 primrec |
86 primrec |
78 fold_list :: "('a \<Rightarrow> 'b \<Rightarrow> 'b) \<Rightarrow> 'b \<Rightarrow> 'a list \<Rightarrow> 'b" |
87 fold_list :: "('a \<Rightarrow> 'b \<Rightarrow> 'b) \<Rightarrow> 'a list \<Rightarrow> 'b \<Rightarrow> 'b" |
79 where |
88 where |
80 "fold_list f z [] = z" |
89 "fold_list f [] = id" |
81 | "fold_list f z (a # xs) = |
90 | "fold_list f (a # xs) = |
82 (if (rsp_fold f) then |
91 (if rsp_fold f then |
83 if a \<in> set xs then fold_list f z xs |
92 if a \<in> set xs then fold_list f xs |
84 else f a (fold_list f z xs) |
93 else f a \<circ> fold_list f xs |
85 else z)" |
94 else id)" |
86 |
95 |
|
96 lemma fold_list_default [simp]: |
|
97 "\<not> rsp_fold f \<Longrightarrow> fold_list f xs = id" |
|
98 by (cases xs) simp_all |
|
99 |
|
100 lemma fold_list_fold_remdups: |
|
101 "rsp_fold f \<Longrightarrow> fold_list f xs = fold f (remdups xs)" |
|
102 by (induct xs) (auto elim: rsp_foldE intro: fold_commute) |
87 |
103 |
88 |
104 |
89 section {* Quotient composition lemmas *} |
105 section {* Quotient composition lemmas *} |
90 |
106 |
91 lemma list_all2_refl': |
107 lemma list_all2_refl': |
224 by (auto intro!: fun_relI) |
240 by (auto intro!: fun_relI) |
225 |
241 |
226 lemma member_commute_fold_list: |
242 lemma member_commute_fold_list: |
227 assumes a: "rsp_fold f" |
243 assumes a: "rsp_fold f" |
228 and b: "x \<in> set xs" |
244 and b: "x \<in> set xs" |
229 shows "fold_list f y xs = f x (fold_list f y (removeAll x xs))" |
245 shows "fold_list f xs = f x \<circ> fold_list f (removeAll x xs)" |
230 using a b by (induct xs) (auto simp add: rsp_fold_def fun_eq_iff) |
246 using a b by (induct xs) (auto simp add: rsp_fold_def fun_eq_iff) |
231 |
247 |
232 lemma fold_list_rsp_pre: |
248 lemma fold_list_set_equiv: |
233 assumes a: "set xs = set ys" |
249 assumes "xs \<approx> ys" |
234 shows "fold_list f z xs = fold_list f z ys" |
250 shows "fold_list f xs = fold_list f ys" |
235 using a |
251 proof (cases "rsp_fold f") |
236 apply (induct xs arbitrary: ys) |
252 case False then show ?thesis by simp |
237 apply (simp) |
253 next |
238 apply (simp (no_asm_use)) |
254 case True |
239 apply (rule conjI) |
255 then have "\<And>x y. x \<in> set (remdups xs) \<Longrightarrow> y \<in> set (remdups xs) \<Longrightarrow> f x \<circ> f y = f y \<circ> f x" |
240 apply (rule_tac [!] impI) |
256 by (rule rsp_foldE) |
241 apply (rule_tac [!] conjI) |
257 moreover from assms have "multiset_of (remdups xs) = multiset_of (remdups ys)" |
242 apply (rule_tac [!] impI) |
258 by (simp add: set_eq_iff_multiset_of_remdups_eq) |
243 apply (metis insert_absorb) |
259 ultimately have "fold f (remdups xs) = fold f (remdups ys)" |
244 apply (metis List.insert_def List.set.simps(2) List.set_insert fold_list.simps(2)) |
260 by (rule fold_multiset_equiv) |
245 apply (metis Diff_insert_absorb insertI1 member_commute_fold_list set_removeAll) |
261 with True show ?thesis by (simp add: fold_list_fold_remdups) |
246 apply(drule_tac x="removeAll a ys" in meta_spec) |
262 qed |
247 apply(auto) |
|
248 apply(drule meta_mp) |
|
249 apply(blast) |
|
250 by (metis List.set.simps(2) emptyE fold_list.simps(2) in_listsp_conv_set listsp.simps mem_def) |
|
251 |
263 |
252 lemma fold_list_rsp [quot_respect]: |
264 lemma fold_list_rsp [quot_respect]: |
253 shows "(op = ===> op = ===> op \<approx> ===> op =) fold_list fold_list" |
265 shows "(op = ===> op \<approx> ===> op =) fold_list fold_list" |
254 unfolding fun_rel_def |
266 unfolding fun_rel_def by (auto intro: fold_list_set_equiv) |
255 by(auto intro: fold_list_rsp_pre) |
|
256 |
267 |
257 lemma concat_rsp_pre: |
268 lemma concat_rsp_pre: |
258 assumes a: "list_all2 op \<approx> x x'" |
269 assumes a: "list_all2 op \<approx> x x'" |
259 and b: "x' \<approx> y'" |
270 and b: "x' \<approx> y'" |
260 and c: "list_all2 op \<approx> y' y" |
271 and c: "list_all2 op \<approx> y' y" |
901 |
912 |
902 |
913 |
903 subsection {* filter_fset *} |
914 subsection {* filter_fset *} |
904 |
915 |
905 lemma subset_filter_fset: |
916 lemma subset_filter_fset: |
906 shows "filter_fset P xs |\<subseteq>| filter_fset Q xs = (\<forall> x. x |\<in>| xs \<longrightarrow> P x \<longrightarrow> Q x)" |
917 "filter_fset P xs |\<subseteq>| filter_fset Q xs = (\<forall> x. x |\<in>| xs \<longrightarrow> P x \<longrightarrow> Q x)" |
907 by (descending) (auto) |
918 by descending auto |
908 |
919 |
909 lemma eq_filter_fset: |
920 lemma eq_filter_fset: |
910 shows "(filter_fset P xs = filter_fset Q xs) = (\<forall>x. x |\<in>| xs \<longrightarrow> P x = Q x)" |
921 "(filter_fset P xs = filter_fset Q xs) = (\<forall>x. x |\<in>| xs \<longrightarrow> P x = Q x)" |
911 by (descending) (auto) |
922 by descending auto |
912 |
923 |
913 lemma psubset_filter_fset: |
924 lemma psubset_filter_fset: |
914 shows "(\<And>x. x |\<in>| xs \<Longrightarrow> P x \<Longrightarrow> Q x) \<Longrightarrow> (x |\<in>| xs & \<not> P x & Q x) \<Longrightarrow> |
925 "(\<And>x. x |\<in>| xs \<Longrightarrow> P x \<Longrightarrow> Q x) \<Longrightarrow> (x |\<in>| xs & \<not> P x & Q x) \<Longrightarrow> |
915 filter_fset P xs |\<subset>| filter_fset Q xs" |
926 filter_fset P xs |\<subset>| filter_fset Q xs" |
916 unfolding less_fset_def by (auto simp add: subset_filter_fset eq_filter_fset) |
927 unfolding less_fset_def by (auto simp add: subset_filter_fset eq_filter_fset) |
917 |
928 |
918 |
929 |
919 subsection {* fold_fset *} |
930 subsection {* fold_fset *} |
920 |
931 |
921 lemma fold_empty_fset: |
932 lemma fold_empty_fset: |
922 shows "fold_fset f z {||} = z" |
933 "fold_fset f {||} = id" |
923 by (descending) (simp) |
934 by descending simp |
924 |
935 |
925 lemma fold_insert_fset: "fold_fset f z (insert_fset a A) = |
936 lemma fold_insert_fset: "fold_fset f (insert_fset a A) = |
926 (if rsp_fold f then if a |\<in>| A then fold_fset f z A else f a (fold_fset f z A) else z)" |
937 (if rsp_fold f then if a |\<in>| A then fold_fset f A else f a \<circ> fold_fset f A else id)" |
927 by (descending) (simp) |
938 by descending simp |
928 |
939 |
929 lemma in_commute_fold_fset: |
940 lemma in_commute_fold_fset: |
930 "\<lbrakk>rsp_fold f; h |\<in>| b\<rbrakk> \<Longrightarrow> fold_fset f z b = f h (fold_fset f z (remove_fset h b))" |
941 "rsp_fold f \<Longrightarrow> h |\<in>| b \<Longrightarrow> fold_fset f b = f h \<circ> fold_fset f (remove_fset h b)" |
931 by (descending) (simp add: member_commute_fold_list) |
942 by descending (simp add: member_commute_fold_list) |
932 |
943 |
933 |
944 |
934 subsection {* Choice in fsets *} |
945 subsection {* Choice in fsets *} |
935 |
946 |
936 lemma fset_choice: |
947 lemma fset_choice: |