412 by (ALLGOALS Simp_tac); |
412 by (ALLGOALS Simp_tac); |
413 by (resolve_tac prems 1); |
413 by (resolve_tac prems 1); |
414 by (eresolve_tac prems 1); |
414 by (eresolve_tac prems 1); |
415 qed "rev_induct"; |
415 qed "rev_induct"; |
416 |
416 |
417 fun rev_induct_tac xs = res_inst_tac [("xs",xs)] rev_induct; |
417 val rev_induct_tac = induct_thm_tac rev_induct; |
418 |
418 |
419 Goal "(xs = [] --> P) --> (!ys y. xs = ys@[y] --> P) --> P"; |
419 Goal "(xs = [] --> P) --> (!ys y. xs = ys@[y] --> P) --> P"; |
420 by (res_inst_tac [("xs","xs")] rev_induct 1); |
420 by (rev_induct_tac "xs" 1); |
421 by Auto_tac; |
421 by Auto_tac; |
422 bind_thm ("rev_exhaust", |
422 bind_thm ("rev_exhaust", |
423 impI RSN (2,allI RSN (2,allI RSN (2,impI RS (result() RS mp RS mp))))); |
423 impI RSN (2,allI RSN (2,allI RSN (2,impI RS (result() RS mp RS mp))))); |
424 |
424 |
425 |
425 |
750 by Auto_tac; |
750 by Auto_tac; |
751 qed "butlast_snoc"; |
751 qed "butlast_snoc"; |
752 Addsimps [butlast_snoc]; |
752 Addsimps [butlast_snoc]; |
753 |
753 |
754 Goal "length(butlast xs) = length xs - 1"; |
754 Goal "length(butlast xs) = length xs - 1"; |
755 by (res_inst_tac [("xs","xs")] rev_induct 1); |
755 by (rev_induct_tac "xs" 1); |
756 by Auto_tac; |
756 by Auto_tac; |
757 qed "length_butlast"; |
757 qed "length_butlast"; |
758 Addsimps [length_butlast]; |
758 Addsimps [length_butlast]; |
759 |
759 |
760 Goal "!ys. butlast (xs@ys) = (if ys=[] then butlast xs else xs@butlast ys)"; |
760 Goal "!ys. butlast (xs@ys) = (if ys=[] then butlast xs else xs@butlast ys)"; |
1215 by (induct_tac "n" 1); |
1215 by (induct_tac "n" 1); |
1216 by Auto_tac; |
1216 by Auto_tac; |
1217 qed "map_Suc_upt"; |
1217 qed "map_Suc_upt"; |
1218 |
1218 |
1219 Goal "ALL i. i < n-m --> (map f [m..n(]) ! i = f(m+i)"; |
1219 Goal "ALL i. i < n-m --> (map f [m..n(]) ! i = f(m+i)"; |
1220 by (res_inst_tac [("m","n"),("n","m")] diff_induct 1); |
1220 by (induct_thm_tac diff_induct "n m" 1); |
1221 by (stac (map_Suc_upt RS sym) 3); |
1221 by (stac (map_Suc_upt RS sym) 3); |
1222 by (auto_tac (claset(), simpset() addsimps [less_diff_conv, nth_upt])); |
1222 by (auto_tac (claset(), simpset() addsimps [less_diff_conv, nth_upt])); |
1223 qed_spec_mp "nth_map_upt"; |
1223 qed_spec_mp "nth_map_upt"; |
1224 |
1224 |
1225 Goal "ALL xs ys. k <= length xs --> k <= length ys --> \ |
1225 Goal "ALL xs ys. k <= length xs --> k <= length ys --> \ |
1451 by Auto_tac; |
1451 by Auto_tac; |
1452 qed "sublist_nil"; |
1452 qed "sublist_nil"; |
1453 |
1453 |
1454 Goal "map fst [p:zip xs [i..i + length xs(] . snd p : A] = \ |
1454 Goal "map fst [p:zip xs [i..i + length xs(] . snd p : A] = \ |
1455 \ map fst [p:zip xs [0..length xs(] . snd p + i : A]"; |
1455 \ map fst [p:zip xs [0..length xs(] . snd p + i : A]"; |
1456 by (res_inst_tac [("xs","xs")] rev_induct 1); |
1456 by (rev_induct_tac "xs" 1); |
1457 by (asm_simp_tac (simpset() addsimps [add_commute]) 2); |
1457 by (asm_simp_tac (simpset() addsimps [add_commute]) 2); |
1458 by (Simp_tac 1); |
1458 by (Simp_tac 1); |
1459 qed "sublist_shift_lemma"; |
1459 qed "sublist_shift_lemma"; |
1460 |
1460 |
1461 Goalw [sublist_def] |
1461 Goalw [sublist_def] |
1462 "sublist (l@l') A = sublist l A @ sublist l' {j. j + length l : A}"; |
1462 "sublist (l@l') A = sublist l A @ sublist l' {j. j + length l : A}"; |
1463 by (res_inst_tac [("xs","l'")] rev_induct 1); |
1463 by (rev_induct_tac "l'" 1); |
1464 by (Simp_tac 1); |
1464 by (Simp_tac 1); |
1465 by (asm_simp_tac (simpset() addsimps [inst "i" "0" upt_add_eq_append, |
1465 by (asm_simp_tac (simpset() addsimps [inst "i" "0" upt_add_eq_append, |
1466 zip_append, sublist_shift_lemma]) 1); |
1466 zip_append, sublist_shift_lemma]) 1); |
1467 by (asm_simp_tac (simpset() addsimps [add_commute]) 1); |
1467 by (asm_simp_tac (simpset() addsimps [add_commute]) 1); |
1468 qed "sublist_append"; |
1468 qed "sublist_append"; |
1469 |
1469 |
1470 Addsimps [sublist_empty, sublist_nil]; |
1470 Addsimps [sublist_empty, sublist_nil]; |
1471 |
1471 |
1472 Goal "sublist (x#l) A = (if 0:A then [x] else []) @ sublist l {j. Suc j : A}"; |
1472 Goal "sublist (x#l) A = (if 0:A then [x] else []) @ sublist l {j. Suc j : A}"; |
1473 by (res_inst_tac [("xs","l")] rev_induct 1); |
1473 by (rev_induct_tac "l" 1); |
1474 by (asm_simp_tac (simpset() delsimps [append_Cons] |
1474 by (asm_simp_tac (simpset() delsimps [append_Cons] |
1475 addsimps [append_Cons RS sym, sublist_append]) 2); |
1475 addsimps [append_Cons RS sym, sublist_append]) 2); |
1476 by (simp_tac (simpset() addsimps [sublist_def]) 1); |
1476 by (simp_tac (simpset() addsimps [sublist_def]) 1); |
1477 qed "sublist_Cons"; |
1477 qed "sublist_Cons"; |
1478 |
1478 |
1480 by (simp_tac (simpset() addsimps [sublist_Cons]) 1); |
1480 by (simp_tac (simpset() addsimps [sublist_Cons]) 1); |
1481 qed "sublist_singleton"; |
1481 qed "sublist_singleton"; |
1482 Addsimps [sublist_singleton]; |
1482 Addsimps [sublist_singleton]; |
1483 |
1483 |
1484 Goal "sublist l {..n(} = take n l"; |
1484 Goal "sublist l {..n(} = take n l"; |
1485 by (res_inst_tac [("xs","l")] rev_induct 1); |
1485 by (rev_induct_tac "l" 1); |
1486 by (asm_simp_tac (simpset() addsplits [nat_diff_split] |
1486 by (asm_simp_tac (simpset() addsplits [nat_diff_split] |
1487 addsimps [sublist_append]) 2); |
1487 addsimps [sublist_append]) 2); |
1488 by (Simp_tac 1); |
1488 by (Simp_tac 1); |
1489 qed "sublist_upt_eq_take"; |
1489 qed "sublist_upt_eq_take"; |
1490 Addsimps [sublist_upt_eq_take]; |
1490 Addsimps [sublist_upt_eq_take]; |