src/HOL/List.ML
changeset 9747 043098ba5098
parent 9700 71364b487232
child 9763 252c690690b0
equal deleted inserted replaced
9746:64b803edef39 9747:043098ba5098
   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];