70 val rel_mono_strong_of_bnf: bnf -> thm |
70 val rel_mono_strong_of_bnf: bnf -> thm |
71 val rel_eq_of_bnf: bnf -> thm |
71 val rel_eq_of_bnf: bnf -> thm |
72 val rel_flip_of_bnf: bnf -> thm |
72 val rel_flip_of_bnf: bnf -> thm |
73 val set_bd_of_bnf: bnf -> thm list |
73 val set_bd_of_bnf: bnf -> thm list |
74 val set_defs_of_bnf: bnf -> thm list |
74 val set_defs_of_bnf: bnf -> thm list |
|
75 val set_map0_of_bnf: bnf -> thm list |
75 val set_map'_of_bnf: bnf -> thm list |
76 val set_map'_of_bnf: bnf -> thm list |
76 val set_map_of_bnf: bnf -> thm list |
|
77 val wit_thms_of_bnf: bnf -> thm list |
77 val wit_thms_of_bnf: bnf -> thm list |
78 val wit_thmss_of_bnf: bnf -> thm list list |
78 val wit_thmss_of_bnf: bnf -> thm list list |
79 |
79 |
80 val mk_witness: int list * term -> thm list -> nonemptiness_witness |
80 val mk_witness: int list * term -> thm list -> nonemptiness_witness |
81 val minimize_wits: (''a list * 'b) list -> (''a list * 'b) list |
81 val minimize_wits: (''a list * 'b) list -> (''a list * 'b) list |
114 |
114 |
115 type axioms = { |
115 type axioms = { |
116 map_id0: thm, |
116 map_id0: thm, |
117 map_comp0: thm, |
117 map_comp0: thm, |
118 map_cong0: thm, |
118 map_cong0: thm, |
119 set_map: thm list, |
119 set_map0: thm list, |
120 bd_card_order: thm, |
120 bd_card_order: thm, |
121 bd_cinfinite: thm, |
121 bd_cinfinite: thm, |
122 set_bd: thm list, |
122 set_bd: thm list, |
123 map_wpull: thm, |
123 map_wpull: thm, |
124 rel_OO_Grp: thm |
124 rel_OO_Grp: thm |
125 }; |
125 }; |
126 |
126 |
127 fun mk_axioms' ((((((((id, comp), cong), nat), c_o), cinf), set_bd), wpull), rel) = |
127 fun mk_axioms' ((((((((id, comp), cong), map), c_o), cinf), set_bd), wpull), rel) = |
128 {map_id0 = id, map_comp0 = comp, map_cong0 = cong, set_map = nat, bd_card_order = c_o, |
128 {map_id0 = id, map_comp0 = comp, map_cong0 = cong, set_map0 = map, bd_card_order = c_o, |
129 bd_cinfinite = cinf, set_bd = set_bd, map_wpull = wpull, rel_OO_Grp = rel}; |
129 bd_cinfinite = cinf, set_bd = set_bd, map_wpull = wpull, rel_OO_Grp = rel}; |
130 |
130 |
131 fun dest_cons [] = raise List.Empty |
131 fun dest_cons [] = raise List.Empty |
132 | dest_cons (x :: xs) = (x, xs); |
132 | dest_cons (x :: xs) = (x, xs); |
133 |
133 |
142 ||>> chop n |
142 ||>> chop n |
143 ||>> dest_cons |
143 ||>> dest_cons |
144 ||> the_single |
144 ||> the_single |
145 |> mk_axioms'; |
145 |> mk_axioms'; |
146 |
146 |
147 fun zip_axioms mid mcomp mcong snat bdco bdinf sbd wpull rel = |
147 fun zip_axioms mid mcomp mcong smap bdco bdinf sbd wpull rel = |
148 [mid, mcomp, mcong] @ snat @ [bdco, bdinf] @ sbd @ [wpull, rel]; |
148 [mid, mcomp, mcong] @ smap @ [bdco, bdinf] @ sbd @ [wpull, rel]; |
149 |
149 |
150 fun dest_axioms {map_id0, map_comp0, map_cong0, set_map, bd_card_order, bd_cinfinite, set_bd, |
150 fun dest_axioms {map_id0, map_comp0, map_cong0, set_map0, bd_card_order, bd_cinfinite, set_bd, |
151 map_wpull, rel_OO_Grp} = |
151 map_wpull, rel_OO_Grp} = |
152 zip_axioms map_id0 map_comp0 map_cong0 set_map bd_card_order bd_cinfinite set_bd map_wpull |
152 zip_axioms map_id0 map_comp0 map_cong0 set_map0 bd_card_order bd_cinfinite set_bd map_wpull |
153 rel_OO_Grp; |
153 rel_OO_Grp; |
154 |
154 |
155 fun map_axioms f {map_id0, map_comp0, map_cong0, set_map, bd_card_order, bd_cinfinite, set_bd, |
155 fun map_axioms f {map_id0, map_comp0, map_cong0, set_map0, bd_card_order, bd_cinfinite, set_bd, |
156 map_wpull, rel_OO_Grp} = |
156 map_wpull, rel_OO_Grp} = |
157 {map_id0 = f map_id0, |
157 {map_id0 = f map_id0, |
158 map_comp0 = f map_comp0, |
158 map_comp0 = f map_comp0, |
159 map_cong0 = f map_cong0, |
159 map_cong0 = f map_cong0, |
160 set_map = map f set_map, |
160 set_map0 = map f set_map0, |
161 bd_card_order = f bd_card_order, |
161 bd_card_order = f bd_card_order, |
162 bd_cinfinite = f bd_cinfinite, |
162 bd_cinfinite = f bd_cinfinite, |
163 set_bd = map f set_bd, |
163 set_bd = map f set_bd, |
164 map_wpull = f map_wpull, |
164 map_wpull = f map_wpull, |
165 rel_OO_Grp = f rel_OO_Grp}; |
165 rel_OO_Grp = f rel_OO_Grp}; |
392 val rel_def_of_bnf = #rel_def o #defs o rep_bnf; |
392 val rel_def_of_bnf = #rel_def o #defs o rep_bnf; |
393 val rel_eq_of_bnf = Lazy.force o #rel_eq o #facts o rep_bnf; |
393 val rel_eq_of_bnf = Lazy.force o #rel_eq o #facts o rep_bnf; |
394 val rel_flip_of_bnf = Lazy.force o #rel_flip o #facts o rep_bnf; |
394 val rel_flip_of_bnf = Lazy.force o #rel_flip o #facts o rep_bnf; |
395 val set_bd_of_bnf = #set_bd o #axioms o rep_bnf; |
395 val set_bd_of_bnf = #set_bd o #axioms o rep_bnf; |
396 val set_defs_of_bnf = #set_defs o #defs o rep_bnf; |
396 val set_defs_of_bnf = #set_defs o #defs o rep_bnf; |
397 val set_map_of_bnf = #set_map o #axioms o rep_bnf; |
397 val set_map0_of_bnf = #set_map0 o #axioms o rep_bnf; |
398 val set_map'_of_bnf = map Lazy.force o #set_map' o #facts o rep_bnf; |
398 val set_map'_of_bnf = map Lazy.force o #set_map' o #facts o rep_bnf; |
399 val rel_cong_of_bnf = Lazy.force o #rel_cong o #facts o rep_bnf; |
399 val rel_cong_of_bnf = Lazy.force o #rel_cong o #facts o rep_bnf; |
400 val rel_mono_of_bnf = Lazy.force o #rel_mono o #facts o rep_bnf; |
400 val rel_mono_of_bnf = Lazy.force o #rel_mono o #facts o rep_bnf; |
401 val rel_mono_strong_of_bnf = Lazy.force o #rel_mono_strong o #facts o rep_bnf; |
401 val rel_mono_strong_of_bnf = Lazy.force o #rel_mono_strong o #facts o rep_bnf; |
402 val rel_Grp_of_bnf = Lazy.force o #rel_Grp o #facts o rep_bnf; |
402 val rel_Grp_of_bnf = Lazy.force o #rel_Grp o #facts o rep_bnf; |
516 val map_congN = "map_cong"; |
516 val map_congN = "map_cong"; |
517 val map_transferN = "map_transfer"; |
517 val map_transferN = "map_transfer"; |
518 val map_wpullN = "map_wpull"; |
518 val map_wpullN = "map_wpull"; |
519 val rel_eqN = "rel_eq"; |
519 val rel_eqN = "rel_eq"; |
520 val rel_flipN = "rel_flip"; |
520 val rel_flipN = "rel_flip"; |
521 val set_mapN = "set_map"; |
521 val set_map0N = "set_map0"; |
522 val set_map'N = "set_map'"; |
522 val set_map'N = "set_map'"; |
523 val set_bdN = "set_bd"; |
523 val set_bdN = "set_bd"; |
524 val rel_GrpN = "rel_Grp"; |
524 val rel_GrpN = "rel_Grp"; |
525 val rel_conversepN = "rel_conversep"; |
525 val rel_conversepN = "rel_conversep"; |
526 val rel_monoN = "rel_mono" |
526 val rel_monoN = "rel_mono" |
561 (map_comp0N, [#map_comp0 axioms]), |
561 (map_comp0N, [#map_comp0 axioms]), |
562 (map_id0N, [#map_id0 axioms]), |
562 (map_id0N, [#map_id0 axioms]), |
563 (map_transferN, [Lazy.force (#map_transfer facts)]), |
563 (map_transferN, [Lazy.force (#map_transfer facts)]), |
564 (map_wpullN, [#map_wpull axioms]), |
564 (map_wpullN, [#map_wpull axioms]), |
565 (rel_mono_strongN, [Lazy.force (#rel_mono_strong facts)]), |
565 (rel_mono_strongN, [Lazy.force (#rel_mono_strong facts)]), |
566 (set_mapN, #set_map axioms), |
566 (set_map0N, #set_map0 axioms), |
567 (set_bdN, #set_bd axioms)] @ |
567 (set_bdN, #set_bd axioms)] @ |
568 (witNs ~~ wit_thmss_of_bnf bnf) |
568 (witNs ~~ wit_thmss_of_bnf bnf) |
569 |> map (fn (thmN, thms) => |
569 |> map (fn (thmN, thms) => |
570 ((qualify (Binding.qualify true (Binding.name_of bnf_b) (Binding.name thmN)), []), |
570 ((qualify (Binding.qualify true (Binding.name_of bnf_b) (Binding.name thmN)), []), |
571 [(thms, [])])); |
571 [(thms, [])])); |
871 Term.list_comb (bnf_map_AsBs, fs_copy) $ x); |
871 Term.list_comb (bnf_map_AsBs, fs_copy) $ x); |
872 in |
872 in |
873 fold_rev Logic.all (x :: fs @ fs_copy) (Logic.list_implies (prems, eq)) |
873 fold_rev Logic.all (x :: fs @ fs_copy) (Logic.list_implies (prems, eq)) |
874 end; |
874 end; |
875 |
875 |
876 val set_maps_goal = |
876 val set_map0s_goal = |
877 let |
877 let |
878 fun mk_goal setA setB f = |
878 fun mk_goal setA setB f = |
879 let |
879 let |
880 val set_comp_map = |
880 val set_comp_map = |
881 HOLogic.mk_comp (setB, Term.list_comb (bnf_map_AsBs, fs)); |
881 HOLogic.mk_comp (setB, Term.list_comb (bnf_map_AsBs, fs)); |
920 (Logic.list_implies (prems, HOLogic.mk_Trueprop map_wpull)) |
920 (Logic.list_implies (prems, HOLogic.mk_Trueprop map_wpull)) |
921 end; |
921 end; |
922 |
922 |
923 val rel_OO_Grp_goal = fold_rev Logic.all Rs (mk_Trueprop_eq (Term.list_comb (rel, Rs), OO_Grp)); |
923 val rel_OO_Grp_goal = fold_rev Logic.all Rs (mk_Trueprop_eq (Term.list_comb (rel, Rs), OO_Grp)); |
924 |
924 |
925 val goals = zip_axioms map_id0_goal map_comp0_goal map_cong0_goal set_maps_goal |
925 val goals = zip_axioms map_id0_goal map_comp0_goal map_cong0_goal set_map0s_goal |
926 card_order_bd_goal cinfinite_bd_goal set_bds_goal map_wpull_goal rel_OO_Grp_goal; |
926 card_order_bd_goal cinfinite_bd_goal set_bds_goal map_wpull_goal rel_OO_Grp_goal; |
927 |
927 |
928 fun mk_wit_goals (I, wit) = |
928 fun mk_wit_goals (I, wit) = |
929 let |
929 let |
930 val xs = map (nth bs) I; |
930 val xs = map (nth bs) I; |
963 (map2 (fn h => fn set => HOLogic.mk_comp (mk_image h, set)) hs bnf_sets_As) |
963 (map2 (fn h => fn set => HOLogic.mk_comp (mk_image h, set)) hs bnf_sets_As) |
964 defT; |
964 defT; |
965 (*collect {set1 ... setm} o map f1 ... fm = collect {f1` o set1 ... fm` o setm}*) |
965 (*collect {set1 ... setm} o map f1 ... fm = collect {f1` o set1 ... fm` o setm}*) |
966 val goal = fold_rev Logic.all hs (mk_Trueprop_eq (collect_map, image_collect)); |
966 val goal = fold_rev Logic.all hs (mk_Trueprop_eq (collect_map, image_collect)); |
967 in |
967 in |
968 Goal.prove_sorry lthy [] [] goal (K (mk_collect_set_map_tac (#set_map axioms))) |
968 Goal.prove_sorry lthy [] [] goal (K (mk_collect_set_map_tac (#set_map0 axioms))) |
969 |> Thm.close_derivation |
969 |> Thm.close_derivation |
970 end; |
970 end; |
971 |
971 |
972 val collect_set_map = Lazy.lazy mk_collect_set_map; |
972 val collect_set_map = Lazy.lazy mk_collect_set_map; |
973 |
973 |
1333 |> Pretty.writeln |
1333 |> Pretty.writeln |
1334 end; |
1334 end; |
1335 |
1335 |
1336 val _ = |
1336 val _ = |
1337 Outer_Syntax.improper_command @{command_spec "print_bnfs"} |
1337 Outer_Syntax.improper_command @{command_spec "print_bnfs"} |
1338 "print all BNFs (bounded natural functors)" |
1338 "print all bounded natural functors" |
1339 (Scan.succeed (Toplevel.keep (print_bnfs o Toplevel.context_of))); |
1339 (Scan.succeed (Toplevel.keep (print_bnfs o Toplevel.context_of))); |
1340 |
1340 |
1341 val _ = |
1341 val _ = |
1342 Outer_Syntax.local_theory_to_proof @{command_spec "bnf"} |
1342 Outer_Syntax.local_theory_to_proof @{command_spec "bnf"} |
1343 "register a type as a BNF (bounded natural functor)" |
1343 "register a type as a bounded natural functor" |
1344 ((parse_opt_binding_colon -- Parse.term -- |
1344 ((parse_opt_binding_colon -- Parse.term -- |
1345 (@{keyword "["} |-- Parse.list Parse.term --| @{keyword "]"}) -- Parse.term -- |
1345 (@{keyword "["} |-- Parse.list Parse.term --| @{keyword "]"}) -- Parse.term -- |
1346 (@{keyword "["} |-- Parse.list Parse.term --| @{keyword "]"}) -- Scan.option Parse.term) |
1346 (@{keyword "["} |-- Parse.list Parse.term --| @{keyword "]"}) -- Scan.option Parse.term) |
1347 >> bnf_cmd); |
1347 >> bnf_cmd); |
1348 |
1348 |