src/HOL/Codatatype/More_BNFs.thy
changeset 49434 433dc7e028c8
parent 49316 a1b0654e7c90
child 49440 4ff2976f4056
equal deleted inserted replaced
49433:1095f240146a 49434:433dc7e028c8
    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