48 \ R(FNIL); \ |
48 \ R(FNIL); \ |
49 \ !!M N. [| M: Part (TF A) In0; N: Part (TF A) In1; R(M); R(N) \ |
49 \ !!M N. [| M: Part (TF A) In0; N: Part (TF A) In1; R(M); R(N) \ |
50 \ |] ==> R(FCONS M N) \ |
50 \ |] ==> R(FCONS M N) \ |
51 \ |] ==> R(i)"; |
51 \ |] ==> R(i)"; |
52 by (rtac ([TF_def, TF_fun_mono, major] MRS def_induct) 1); |
52 by (rtac ([TF_def, TF_fun_mono, major] MRS def_induct) 1); |
53 by (fast_tac (set_cs addIs (prems@[PartI]) |
53 by (fast_tac (!claset addIs (prems@[PartI]) |
54 addEs [usumE, uprodE, PartE]) 1); |
54 addEs [usumE, uprodE, PartE]) 1); |
55 qed "TF_induct"; |
55 qed "TF_induct"; |
56 |
56 |
57 (*This lemma replaces a use of subgoal_tac to prove tree_forest_induct*) |
57 (*This lemma replaces a use of subgoal_tac to prove tree_forest_induct*) |
58 val prems = goalw Simult.thy [Part_def] |
58 val prems = goalw Simult.thy [Part_def] |
59 "! M: TF(A). (M: Part (TF A) In0 --> P(M)) & (M: Part (TF A) In1 --> Q(M)) \ |
59 "! M: TF(A). (M: Part (TF A) In0 --> P(M)) & (M: Part (TF A) In1 --> Q(M)) \ |
60 \ ==> (! M: Part (TF A) In0. P(M)) & (! M: Part (TF A) In1. Q(M))"; |
60 \ ==> (! M: Part (TF A) In0. P(M)) & (! M: Part (TF A) In1. Q(M))"; |
61 by (cfast_tac prems 1); |
61 by (cfast_tac prems 1); |
62 qed "TF_induct_lemma"; |
62 qed "TF_induct_lemma"; |
63 |
63 |
64 val uplus_cs = set_cs addSIs [PartI] |
64 AddSIs [PartI]; |
65 addSDs [In0_inject, In1_inject] |
65 AddSDs [In0_inject, In1_inject]; |
66 addSEs [In0_neq_In1, In1_neq_In0, PartE]; |
66 AddSEs [In0_neq_In1, In1_neq_In0, PartE]; |
67 |
67 |
68 (*Could prove ~ TCONS M N : Part (TF A) In1 etc. *) |
68 (*Could prove ~ TCONS M N : Part (TF A) In1 etc. *) |
69 |
69 |
70 (*Induction on TF with separate predicates P, Q*) |
70 (*Induction on TF with separate predicates P, Q*) |
71 val prems = goalw Simult.thy TF_Rep_defs |
71 val prems = goalw Simult.thy TF_Rep_defs |
75 \ |] ==> Q(FCONS M N) \ |
75 \ |] ==> Q(FCONS M N) \ |
76 \ |] ==> (! M: Part (TF A) In0. P(M)) & (! N: Part (TF A) In1. Q(N))"; |
76 \ |] ==> (! M: Part (TF A) In0. P(M)) & (! N: Part (TF A) In1. Q(N))"; |
77 by (rtac (ballI RS TF_induct_lemma) 1); |
77 by (rtac (ballI RS TF_induct_lemma) 1); |
78 by (etac TF_induct 1); |
78 by (etac TF_induct 1); |
79 by (rewrite_goals_tac TF_Rep_defs); |
79 by (rewrite_goals_tac TF_Rep_defs); |
80 by (ALLGOALS (fast_tac (uplus_cs addIs prems))); |
80 by (ALLGOALS (fast_tac (!claset addIs prems))); |
81 (*29 secs??*) |
81 (*29 secs??*) |
82 qed "Tree_Forest_induct"; |
82 qed "Tree_Forest_induct"; |
83 |
83 |
84 (*Induction for the abstract types 'a tree, 'a forest*) |
84 (*Induction for the abstract types 'a tree, 'a forest*) |
85 val prems = goalw Simult.thy [Tcons_def,Fnil_def,Fcons_def] |
85 val prems = goalw Simult.thy [Tcons_def,Fnil_def,Fcons_def] |
89 \ |] ==> (! t. P(t)) & (! ts. Q(ts))"; |
89 \ |] ==> (! t. P(t)) & (! ts. Q(ts))"; |
90 by (res_inst_tac [("P1","%z.P(Abs_Tree(z))"), |
90 by (res_inst_tac [("P1","%z.P(Abs_Tree(z))"), |
91 ("Q1","%z.Q(Abs_Forest(z))")] |
91 ("Q1","%z.Q(Abs_Forest(z))")] |
92 (Tree_Forest_induct RS conjE) 1); |
92 (Tree_Forest_induct RS conjE) 1); |
93 (*Instantiates ?A1 to range(Leaf). *) |
93 (*Instantiates ?A1 to range(Leaf). *) |
94 by (fast_tac (set_cs addSEs [Rep_Tree_inverse RS subst, |
94 by (fast_tac (!claset addSEs [Rep_Tree_inverse RS subst, |
95 Rep_Forest_inverse RS subst] |
95 Rep_Forest_inverse RS subst] |
96 addSIs [Rep_Tree,Rep_Forest]) 4); |
96 addSIs [Rep_Tree,Rep_Forest]) 4); |
97 (*Cannot use simplifier: the rewrites work in the wrong direction!*) |
97 (*Cannot use simplifier: the rewrites work in the wrong direction!*) |
98 by (ALLGOALS (fast_tac (set_cs addSEs [Abs_Tree_inverse RS subst, |
98 by (ALLGOALS (fast_tac (!claset addSEs [Abs_Tree_inverse RS subst, |
99 Abs_Forest_inverse RS subst] |
99 Abs_Forest_inverse RS subst] |
100 addSIs prems))); |
100 addSIs prems))); |
101 qed "tree_forest_induct"; |
101 qed "tree_forest_induct"; |
102 |
102 |
103 |
103 |
129 (* c : A <*> Part (TF A) In1 |
129 (* c : A <*> Part (TF A) In1 |
130 <+> {Numb(0)} <+> Part (TF A) In0 <*> Part (TF A) In1 ==> c : TF(A) *) |
130 <+> {Numb(0)} <+> Part (TF A) In0 <*> Part (TF A) In1 ==> c : TF(A) *) |
131 val TF_I = TF_unfold RS equalityD2 RS subsetD; |
131 val TF_I = TF_unfold RS equalityD2 RS subsetD; |
132 |
132 |
133 (*For reasoning about the representation*) |
133 (*For reasoning about the representation*) |
134 val TF_Rep_cs = uplus_cs addIs [TF_I, uprodI, usum_In0I, usum_In1I] |
134 AddIs [TF_I, uprodI, usum_In0I, usum_In1I]; |
135 addSEs [Scons_inject]; |
135 AddSEs [Scons_inject]; |
136 |
136 |
137 val prems = goalw Simult.thy TF_Rep_defs |
137 val prems = goalw Simult.thy TF_Rep_defs |
138 "[| a: A; M: Part (TF A) In1 |] ==> TCONS a M : Part (TF A) In0"; |
138 "[| a: A; M: Part (TF A) In1 |] ==> TCONS a M : Part (TF A) In0"; |
139 by (fast_tac (TF_Rep_cs addIs prems) 1); |
139 by (fast_tac (!claset addIs prems) 1); |
140 qed "TCONS_I"; |
140 qed "TCONS_I"; |
141 |
141 |
142 (* FNIL is a TF(A) -- this also justifies the type definition*) |
142 (* FNIL is a TF(A) -- this also justifies the type definition*) |
143 goalw Simult.thy TF_Rep_defs "FNIL: Part (TF A) In1"; |
143 goalw Simult.thy TF_Rep_defs "FNIL: Part (TF A) In1"; |
144 by (fast_tac TF_Rep_cs 1); |
144 by (Fast_tac 1); |
145 qed "FNIL_I"; |
145 qed "FNIL_I"; |
146 |
146 |
147 val prems = goalw Simult.thy TF_Rep_defs |
147 val prems = goalw Simult.thy TF_Rep_defs |
148 "[| M: Part (TF A) In0; N: Part (TF A) In1 |] ==> \ |
148 "[| M: Part (TF A) In0; N: Part (TF A) In1 |] ==> \ |
149 \ FCONS M N : Part (TF A) In1"; |
149 \ FCONS M N : Part (TF A) In1"; |
150 by (fast_tac (TF_Rep_cs addIs prems) 1); |
150 by (fast_tac (!claset addIs prems) 1); |
151 qed "FCONS_I"; |
151 qed "FCONS_I"; |
152 |
152 |
153 (** Injectiveness of TCONS and FCONS **) |
153 (** Injectiveness of TCONS and FCONS **) |
154 |
154 |
155 goalw Simult.thy TF_Rep_defs "(TCONS K M=TCONS L N) = (K=L & M=N)"; |
155 goalw Simult.thy TF_Rep_defs "(TCONS K M=TCONS L N) = (K=L & M=N)"; |
156 by (fast_tac TF_Rep_cs 1); |
156 by (Fast_tac 1); |
157 qed "TCONS_TCONS_eq"; |
157 qed "TCONS_TCONS_eq"; |
158 bind_thm ("TCONS_inject", (TCONS_TCONS_eq RS iffD1 RS conjE)); |
158 bind_thm ("TCONS_inject", (TCONS_TCONS_eq RS iffD1 RS conjE)); |
159 |
159 |
160 goalw Simult.thy TF_Rep_defs "(FCONS K M=FCONS L N) = (K=L & M=N)"; |
160 goalw Simult.thy TF_Rep_defs "(FCONS K M=FCONS L N) = (K=L & M=N)"; |
161 by (fast_tac TF_Rep_cs 1); |
161 by (Fast_tac 1); |
162 qed "FCONS_FCONS_eq"; |
162 qed "FCONS_FCONS_eq"; |
163 bind_thm ("FCONS_inject", (FCONS_FCONS_eq RS iffD1 RS conjE)); |
163 bind_thm ("FCONS_inject", (FCONS_FCONS_eq RS iffD1 RS conjE)); |
164 |
164 |
165 (** Distinctness of TCONS, FNIL and FCONS **) |
165 (** Distinctness of TCONS, FNIL and FCONS **) |
166 |
166 |
167 goalw Simult.thy TF_Rep_defs "TCONS M N ~= FNIL"; |
167 goalw Simult.thy TF_Rep_defs "TCONS M N ~= FNIL"; |
168 by (fast_tac TF_Rep_cs 1); |
168 by (Fast_tac 1); |
169 qed "TCONS_not_FNIL"; |
169 qed "TCONS_not_FNIL"; |
170 bind_thm ("FNIL_not_TCONS", (TCONS_not_FNIL RS not_sym)); |
170 bind_thm ("FNIL_not_TCONS", (TCONS_not_FNIL RS not_sym)); |
171 |
171 |
172 bind_thm ("TCONS_neq_FNIL", (TCONS_not_FNIL RS notE)); |
172 bind_thm ("TCONS_neq_FNIL", (TCONS_not_FNIL RS notE)); |
173 val FNIL_neq_TCONS = sym RS TCONS_neq_FNIL; |
173 val FNIL_neq_TCONS = sym RS TCONS_neq_FNIL; |
174 |
174 |
175 goalw Simult.thy TF_Rep_defs "FCONS M N ~= FNIL"; |
175 goalw Simult.thy TF_Rep_defs "FCONS M N ~= FNIL"; |
176 by (fast_tac TF_Rep_cs 1); |
176 by (Fast_tac 1); |
177 qed "FCONS_not_FNIL"; |
177 qed "FCONS_not_FNIL"; |
178 bind_thm ("FNIL_not_FCONS", (FCONS_not_FNIL RS not_sym)); |
178 bind_thm ("FNIL_not_FCONS", (FCONS_not_FNIL RS not_sym)); |
179 |
179 |
180 bind_thm ("FCONS_neq_FNIL", (FCONS_not_FNIL RS notE)); |
180 bind_thm ("FCONS_neq_FNIL", (FCONS_not_FNIL RS notE)); |
181 val FNIL_neq_FCONS = sym RS FCONS_neq_FNIL; |
181 val FNIL_neq_FCONS = sym RS FCONS_neq_FNIL; |
182 |
182 |
183 goalw Simult.thy TF_Rep_defs "TCONS M N ~= FCONS K L"; |
183 goalw Simult.thy TF_Rep_defs "TCONS M N ~= FCONS K L"; |
184 by (fast_tac TF_Rep_cs 1); |
184 by (Fast_tac 1); |
185 qed "TCONS_not_FCONS"; |
185 qed "TCONS_not_FCONS"; |
186 bind_thm ("FCONS_not_TCONS", (TCONS_not_FCONS RS not_sym)); |
186 bind_thm ("FCONS_not_TCONS", (TCONS_not_FCONS RS not_sym)); |
187 |
187 |
188 bind_thm ("TCONS_neq_FCONS", (TCONS_not_FCONS RS notE)); |
188 bind_thm ("TCONS_neq_FCONS", (TCONS_not_FCONS RS notE)); |
189 val FCONS_neq_TCONS = sym RS TCONS_neq_FCONS; |
189 val FCONS_neq_TCONS = sym RS TCONS_neq_FCONS; |
192 Automatically generate symmetric forms? Always expand TF_Rep_defs? *) |
192 Automatically generate symmetric forms? Always expand TF_Rep_defs? *) |
193 |
193 |
194 (** Injectiveness of Tcons and Fcons **) |
194 (** Injectiveness of Tcons and Fcons **) |
195 |
195 |
196 (*For reasoning about abstract constructors*) |
196 (*For reasoning about abstract constructors*) |
197 val TF_cs = set_cs addSIs [Rep_Tree, Rep_Forest, TCONS_I, FNIL_I, FCONS_I] |
197 AddSIs [Rep_Tree, Rep_Forest, TCONS_I, FNIL_I, FCONS_I]; |
198 addSEs [TCONS_inject, FCONS_inject, |
198 AddSEs [TCONS_inject, FCONS_inject, |
199 TCONS_neq_FNIL, FNIL_neq_TCONS, |
199 TCONS_neq_FNIL, FNIL_neq_TCONS, |
200 FCONS_neq_FNIL, FNIL_neq_FCONS, |
200 FCONS_neq_FNIL, FNIL_neq_FCONS, |
201 TCONS_neq_FCONS, FCONS_neq_TCONS] |
201 TCONS_neq_FCONS, FCONS_neq_TCONS]; |
202 addSDs [inj_onto_Abs_Tree RS inj_ontoD, |
202 AddSDs [inj_onto_Abs_Tree RS inj_ontoD, |
203 inj_onto_Abs_Forest RS inj_ontoD, |
203 inj_onto_Abs_Forest RS inj_ontoD, |
204 inj_Rep_Tree RS injD, inj_Rep_Forest RS injD, |
204 inj_Rep_Tree RS injD, inj_Rep_Forest RS injD, |
205 Leaf_inject]; |
205 Leaf_inject]; |
206 |
206 |
207 goalw Simult.thy [Tcons_def] "(Tcons x xs=Tcons y ys) = (x=y & xs=ys)"; |
207 goalw Simult.thy [Tcons_def] "(Tcons x xs=Tcons y ys) = (x=y & xs=ys)"; |
208 by (fast_tac TF_cs 1); |
208 by (Fast_tac 1); |
209 qed "Tcons_Tcons_eq"; |
209 qed "Tcons_Tcons_eq"; |
210 bind_thm ("Tcons_inject", (Tcons_Tcons_eq RS iffD1 RS conjE)); |
210 bind_thm ("Tcons_inject", (Tcons_Tcons_eq RS iffD1 RS conjE)); |
211 |
211 |
212 goalw Simult.thy [Fcons_def,Fnil_def] "Fcons x xs ~= Fnil"; |
212 goalw Simult.thy [Fcons_def,Fnil_def] "Fcons x xs ~= Fnil"; |
213 by (fast_tac TF_cs 1); |
213 by (Fast_tac 1); |
214 qed "Fcons_not_Fnil"; |
214 qed "Fcons_not_Fnil"; |
215 |
215 |
216 bind_thm ("Fcons_neq_Fnil", Fcons_not_Fnil RS notE); |
216 bind_thm ("Fcons_neq_Fnil", Fcons_not_Fnil RS notE); |
217 val Fnil_neq_Fcons = sym RS Fcons_neq_Fnil; |
217 val Fnil_neq_Fcons = sym RS Fcons_neq_Fnil; |
218 |
218 |
219 |
219 |
220 (** Injectiveness of Fcons **) |
220 (** Injectiveness of Fcons **) |
221 |
221 |
222 goalw Simult.thy [Fcons_def] "(Fcons x xs=Fcons y ys) = (x=y & xs=ys)"; |
222 goalw Simult.thy [Fcons_def] "(Fcons x xs=Fcons y ys) = (x=y & xs=ys)"; |
223 by (fast_tac TF_cs 1); |
223 by (Fast_tac 1); |
224 qed "Fcons_Fcons_eq"; |
224 qed "Fcons_Fcons_eq"; |
225 bind_thm ("Fcons_inject", Fcons_Fcons_eq RS iffD1 RS conjE); |
225 bind_thm ("Fcons_inject", Fcons_Fcons_eq RS iffD1 RS conjE); |
226 |
226 |
227 |
227 |
228 (*** TF_rec -- by wf recursion on pred_sexp ***) |
228 (*** TF_rec -- by wf recursion on pred_sexp ***) |