240 val Numb_neq_Scons = sym RS Scons_neq_Numb; |
240 val Numb_neq_Scons = sym RS Scons_neq_Numb; |
241 |
241 |
242 (** Leaf vs Numb **) |
242 (** Leaf vs Numb **) |
243 |
243 |
244 goalw Univ.thy [Leaf_def,Numb_def] "Leaf(a) ~= Numb(k)"; |
244 goalw Univ.thy [Leaf_def,Numb_def] "Leaf(a) ~= Numb(k)"; |
245 by (simp_tac (HOL_ss addsimps [Atom_Atom_eq,Inl_not_Inr]) 1); |
245 by (simp_tac (!simpset addsimps [Atom_Atom_eq,Inl_not_Inr]) 1); |
246 qed "Leaf_not_Numb"; |
246 qed "Leaf_not_Numb"; |
247 bind_thm ("Numb_not_Leaf", (Leaf_not_Numb RS not_sym)); |
247 bind_thm ("Numb_not_Leaf", (Leaf_not_Numb RS not_sym)); |
248 |
248 |
249 bind_thm ("Leaf_neq_Numb", (Leaf_not_Numb RS notE)); |
249 bind_thm ("Leaf_neq_Numb", (Leaf_not_Numb RS notE)); |
250 val Numb_neq_Leaf = sym RS Leaf_neq_Numb; |
250 val Numb_neq_Leaf = sym RS Leaf_neq_Numb; |
251 |
251 |
252 |
252 |
253 (*** ndepth -- the depth of a node ***) |
253 (*** ndepth -- the depth of a node ***) |
254 |
254 |
255 val univ_simps = [apfst_conv,Scons_not_Atom,Atom_not_Scons,Scons_Scons_eq]; |
255 Addsimps [apfst_conv,Scons_not_Atom,Atom_not_Scons,Scons_Scons_eq]; |
256 val univ_ss = nat_ss addsimps univ_simps; |
|
257 |
256 |
258 |
257 |
259 goalw Univ.thy [ndepth_def] "ndepth (Abs_Node((%k.0, x))) = 0"; |
258 goalw Univ.thy [ndepth_def] "ndepth (Abs_Node((%k.0, x))) = 0"; |
260 by (sstac [Node_K0_I RS Abs_Node_inverse, split] 1); |
259 by (sstac [Node_K0_I RS Abs_Node_inverse, split] 1); |
261 by (rtac Least_equality 1); |
260 by (rtac Least_equality 1); |
263 by (etac less_zeroE 1); |
262 by (etac less_zeroE 1); |
264 qed "ndepth_K0"; |
263 qed "ndepth_K0"; |
265 |
264 |
266 goal Univ.thy "k < Suc(LEAST x. f(x)=0) --> nat_case (Suc i) f k ~= 0"; |
265 goal Univ.thy "k < Suc(LEAST x. f(x)=0) --> nat_case (Suc i) f k ~= 0"; |
267 by (nat_ind_tac "k" 1); |
266 by (nat_ind_tac "k" 1); |
268 by (ALLGOALS (simp_tac nat_ss)); |
267 by (ALLGOALS Simp_tac); |
269 by (rtac impI 1); |
268 by (rtac impI 1); |
270 by (etac not_less_Least 1); |
269 by (etac not_less_Least 1); |
271 qed "ndepth_Push_lemma"; |
270 qed "ndepth_Push_lemma"; |
272 |
271 |
273 goalw Univ.thy [ndepth_def,Push_Node_def] |
272 goalw Univ.thy [ndepth_def,Push_Node_def] |
274 "ndepth (Push_Node i n) = Suc(ndepth(n))"; |
273 "ndepth (Push_Node i n) = Suc(ndepth(n))"; |
275 by (stac (Rep_Node RS Node_Push_I RS Abs_Node_inverse) 1); |
274 by (stac (Rep_Node RS Node_Push_I RS Abs_Node_inverse) 1); |
276 by (cut_facts_tac [rewrite_rule [Node_def] Rep_Node] 1); |
275 by (cut_facts_tac [rewrite_rule [Node_def] Rep_Node] 1); |
277 by (safe_tac set_cs); |
276 by (safe_tac set_cs); |
278 be ssubst 1; (*instantiates type variables!*) |
277 be ssubst 1; (*instantiates type variables!*) |
279 by (simp_tac univ_ss 1); |
278 by (Simp_tac 1); |
280 by (rtac Least_equality 1); |
279 by (rtac Least_equality 1); |
281 by (rewtac Push_def); |
280 by (rewtac Push_def); |
282 by (rtac (nat_case_Suc RS trans) 1); |
281 by (rtac (nat_case_Suc RS trans) 1); |
283 by (etac LeastI 1); |
282 by (etac LeastI 1); |
284 by (etac (ndepth_Push_lemma RS mp) 1); |
283 by (etac (ndepth_Push_lemma RS mp) 1); |
315 qed "ntrunc_Scons"; |
314 qed "ntrunc_Scons"; |
316 |
315 |
317 (** Injection nodes **) |
316 (** Injection nodes **) |
318 |
317 |
319 goalw Univ.thy [In0_def] "ntrunc (Suc 0) (In0 M) = {}"; |
318 goalw Univ.thy [In0_def] "ntrunc (Suc 0) (In0 M) = {}"; |
320 by (simp_tac (univ_ss addsimps [ntrunc_Scons,ntrunc_0]) 1); |
319 by (simp_tac (!simpset addsimps [ntrunc_Scons,ntrunc_0]) 1); |
321 by (rewtac Scons_def); |
320 by (rewtac Scons_def); |
322 by (safe_tac (set_cs addSIs [equalityI])); |
321 by (safe_tac (set_cs addSIs [equalityI])); |
323 qed "ntrunc_one_In0"; |
322 qed "ntrunc_one_In0"; |
324 |
323 |
325 goalw Univ.thy [In0_def] |
324 goalw Univ.thy [In0_def] |
326 "ntrunc (Suc (Suc k)) (In0 M) = In0 (ntrunc (Suc k) M)"; |
325 "ntrunc (Suc (Suc k)) (In0 M) = In0 (ntrunc (Suc k) M)"; |
327 by (simp_tac (univ_ss addsimps [ntrunc_Scons,ntrunc_Numb]) 1); |
326 by (simp_tac (!simpset addsimps [ntrunc_Scons,ntrunc_Numb]) 1); |
328 qed "ntrunc_In0"; |
327 qed "ntrunc_In0"; |
329 |
328 |
330 goalw Univ.thy [In1_def] "ntrunc (Suc 0) (In1 M) = {}"; |
329 goalw Univ.thy [In1_def] "ntrunc (Suc 0) (In1 M) = {}"; |
331 by (simp_tac (univ_ss addsimps [ntrunc_Scons,ntrunc_0]) 1); |
330 by (simp_tac (!simpset addsimps [ntrunc_Scons,ntrunc_0]) 1); |
332 by (rewtac Scons_def); |
331 by (rewtac Scons_def); |
333 by (safe_tac (set_cs addSIs [equalityI])); |
332 by (safe_tac (set_cs addSIs [equalityI])); |
334 qed "ntrunc_one_In1"; |
333 qed "ntrunc_one_In1"; |
335 |
334 |
336 goalw Univ.thy [In1_def] |
335 goalw Univ.thy [In1_def] |
337 "ntrunc (Suc (Suc k)) (In1 M) = In1 (ntrunc (Suc k) M)"; |
336 "ntrunc (Suc (Suc k)) (In1 M) = In1 (ntrunc (Suc k) M)"; |
338 by (simp_tac (univ_ss addsimps [ntrunc_Scons,ntrunc_Numb]) 1); |
337 by (simp_tac (!simpset addsimps [ntrunc_Scons,ntrunc_Numb]) 1); |
339 qed "ntrunc_In1"; |
338 qed "ntrunc_In1"; |
340 |
339 |
341 |
340 |
342 (*** Cartesian Product ***) |
341 (*** Cartesian Product ***) |
343 |
342 |
609 by (fast_tac (prod_cs addIs [equalityI, usum_In0I, usum_In1I, |
608 by (fast_tac (prod_cs addIs [equalityI, usum_In0I, usum_In1I, |
610 dsum_In0I, dsum_In1I] |
609 dsum_In0I, dsum_In1I] |
611 addSEs [usumE, dsumE]) 1); |
610 addSEs [usumE, dsumE]) 1); |
612 qed "fst_image_dsum"; |
611 qed "fst_image_dsum"; |
613 |
612 |
614 val fst_image_simps = [fst_image_diag, fst_image_dprod, fst_image_dsum]; |
613 Addsimps [fst_image_diag, fst_image_dprod, fst_image_dsum]; |
615 val fst_image_ss = univ_ss addsimps fst_image_simps; |
|