equal
deleted
inserted
replaced
20 begin |
20 begin |
21 |
21 |
22 lemma option_rec_conv_option_case: "option_rec = option_case" |
22 lemma option_rec_conv_option_case: "option_rec = option_case" |
23 by (simp add: fun_eq_iff split: option.split) |
23 by (simp add: fun_eq_iff split: option.split) |
24 |
24 |
25 bnf_def option = Option.map [Option.set] "\<lambda>_::'a option. natLeq" ["None"] |
25 bnf_def Option.map [Option.set] "\<lambda>_::'a option. natLeq" ["None"] |
26 proof - |
26 proof - |
27 show "Option.map id = id" by (simp add: fun_eq_iff Option.map_def split: option.split) |
27 show "Option.map id = id" by (simp add: fun_eq_iff Option.map_def split: option.split) |
28 next |
28 next |
29 fix f g |
29 fix f g |
30 show "Option.map (g \<circ> f) = Option.map g \<circ> Option.map f" |
30 show "Option.map (g \<circ> f) = Option.map g \<circ> Option.map f" |
188 apply (rule ordLeq_csum2) |
188 apply (rule ordLeq_csum2) |
189 by (rule Card_order_ctwo) |
189 by (rule Card_order_ctwo) |
190 qed |
190 qed |
191 qed |
191 qed |
192 |
192 |
193 bnf_def list = map [set] "\<lambda>_::'a list. natLeq" ["[]"] |
193 bnf_def map [set] "\<lambda>_::'a list. natLeq" ["[]"] |
194 proof - |
194 proof - |
195 show "map id = id" by (rule List.map.id) |
195 show "map id = id" by (rule List.map.id) |
196 next |
196 next |
197 fix f g |
197 fix f g |
198 show "map (g o f) = map g o map f" by (rule List.map.comp[symmetric]) |
198 show "map (g o f) = map g o map f" by (rule List.map.comp[symmetric]) |
353 qed |
353 qed |
354 |
354 |
355 lemma fset_to_fset: "finite A \<Longrightarrow> fset (the_inv fset A) = A" |
355 lemma fset_to_fset: "finite A \<Longrightarrow> fset (the_inv fset A) = A" |
356 by (rule f_the_inv_into_f) (auto simp: inj_on_def fset_cong dest!: finite_ex_fset) |
356 by (rule f_the_inv_into_f) (auto simp: inj_on_def fset_cong dest!: finite_ex_fset) |
357 |
357 |
358 bnf_def fset = map_fset [fset] "\<lambda>_::'a fset. natLeq" ["{||}"] |
358 bnf_def map_fset [fset] "\<lambda>_::'a fset. natLeq" ["{||}"] |
359 proof - |
359 proof - |
360 show "map_fset id = id" |
360 show "map_fset id = id" |
361 unfolding map_fset_def2 map_id o_id afset_rfset_id .. |
361 unfolding map_fset_def2 map_id o_id afset_rfset_id .. |
362 next |
362 next |
363 fix f g |
363 fix f g |
509 using csum_Cnotzero2 ctwo_Cnotzero apply blast |
509 using csum_Cnotzero2 ctwo_Cnotzero apply blast |
510 by (rule natLeq_Card_order) |
510 by (rule natLeq_Card_order) |
511 finally show ?thesis . |
511 finally show ?thesis . |
512 qed |
512 qed |
513 |
513 |
514 bnf_def cset = cIm [rcset] "\<lambda>_::'a cset. natLeq" ["cEmp"] |
514 bnf_def cIm [rcset] "\<lambda>_::'a cset. natLeq" ["cEmp"] |
515 proof - |
515 proof - |
516 show "cIm id = id" unfolding cIm_def[abs_def] id_def by auto |
516 show "cIm id = id" unfolding cIm_def[abs_def] id_def by auto |
517 next |
517 next |
518 fix f g show "cIm (g \<circ> f) = cIm g \<circ> cIm f" |
518 fix f g show "cIm (g \<circ> f) = cIm g \<circ> cIm f" |
519 unfolding cIm_def[abs_def] apply(rule ext) unfolding comp_def by auto |
519 unfolding cIm_def[abs_def] apply(rule ext) unfolding comp_def by auto |
1132 qed |
1132 qed |
1133 |
1133 |
1134 definition mset_map :: "('a \<Rightarrow> 'b) \<Rightarrow> 'a multiset \<Rightarrow> 'b multiset" where |
1134 definition mset_map :: "('a \<Rightarrow> 'b) \<Rightarrow> 'a multiset \<Rightarrow> 'b multiset" where |
1135 "mset_map h = Abs_multiset \<circ> mmap h \<circ> count" |
1135 "mset_map h = Abs_multiset \<circ> mmap h \<circ> count" |
1136 |
1136 |
1137 bnf_def mset = mset_map [set_of] "\<lambda>_::'a multiset. natLeq" ["{#}"] |
1137 bnf_def mset_map [set_of] "\<lambda>_::'a multiset. natLeq" ["{#}"] |
1138 unfolding mset_map_def |
1138 unfolding mset_map_def |
1139 proof - |
1139 proof - |
1140 show "Abs_multiset \<circ> mmap id \<circ> count = id" unfolding mmap_id by (auto simp: count_inverse) |
1140 show "Abs_multiset \<circ> mmap id \<circ> count = id" unfolding mmap_id by (auto simp: count_inverse) |
1141 next |
1141 next |
1142 fix f g |
1142 fix f g |