src/HOL/List.ML
changeset 5132 24f992a25adc
parent 5129 99ffd3dfb180
child 5162 53e505c6019c
equal deleted inserted replaced
5131:dd4ac220b8b4 5132:24f992a25adc
    19 qed "neq_Nil_conv";
    19 qed "neq_Nil_conv";
    20 
    20 
    21 (* Induction over the length of a list: *)
    21 (* Induction over the length of a list: *)
    22 val [prem] = Goal
    22 val [prem] = Goal
    23   "(!!xs. (!ys. length ys < length xs --> P ys) ==> P xs) ==> P(xs)";
    23   "(!!xs. (!ys. length ys < length xs --> P ys) ==> P xs) ==> P(xs)";
    24 by(rtac measure_induct 1 THEN etac prem 1);
    24 by (rtac measure_induct 1 THEN etac prem 1);
    25 qed "length_induct";
    25 qed "length_induct";
    26 
    26 
    27 
    27 
    28 (** "lists": the list-forming operator over sets **)
    28 (** "lists": the list-forming operator over sets **)
    29 
    29 
   182  [same_append_eq RS iffD2, append1_eq_conv RS iffD2, append_same_eq RS iffD2];
   182  [same_append_eq RS iffD2, append1_eq_conv RS iffD2, append_same_eq RS iffD2];
   183 AddSDs
   183 AddSDs
   184  [same_append_eq RS iffD1, append1_eq_conv RS iffD1, append_same_eq RS iffD1];
   184  [same_append_eq RS iffD1, append1_eq_conv RS iffD1, append_same_eq RS iffD1];
   185 
   185 
   186 Goal "(xs @ ys = ys) = (xs=[])";
   186 Goal "(xs @ ys = ys) = (xs=[])";
   187 by(cut_inst_tac [("zs","[]")] append_same_eq 1);
   187 by (cut_inst_tac [("zs","[]")] append_same_eq 1);
   188 by (Auto_tac);
   188 by (Auto_tac);
   189 qed "append_self_conv2";
   189 qed "append_self_conv2";
   190 
   190 
   191 Goal "(ys = xs @ ys) = (xs=[])";
   191 Goal "(ys = xs @ ys) = (xs=[])";
   192 by(simp_tac (simpset() addsimps
   192 by (simp_tac (simpset() addsimps
   193      [simplify (simpset()) (read_instantiate[("ys","[]")]append_same_eq)]) 1);
   193      [simplify (simpset()) (read_instantiate[("ys","[]")]append_same_eq)]) 1);
   194 by(Blast_tac 1);
   194 by (Blast_tac 1);
   195 qed "self_append_conv2";
   195 qed "self_append_conv2";
   196 AddIffs [append_self_conv2,self_append_conv2];
   196 AddIffs [append_self_conv2,self_append_conv2];
   197 
   197 
   198 Goal "xs ~= [] --> hd xs # tl xs = xs";
   198 Goal "xs ~= [] --> hd xs # tl xs = xs";
   199 by (induct_tac "xs" 1);
   199 by (induct_tac "xs" 1);
   307 by (Auto_tac);
   307 by (Auto_tac);
   308 qed "Nil_is_rev_conv";
   308 qed "Nil_is_rev_conv";
   309 AddIffs [Nil_is_rev_conv];
   309 AddIffs [Nil_is_rev_conv];
   310 
   310 
   311 val prems = Goal "[| P []; !!x xs. P xs ==> P(xs@[x]) |] ==> P xs";
   311 val prems = Goal "[| P []; !!x xs. P xs ==> P(xs@[x]) |] ==> P xs";
   312 by(stac (rev_rev_ident RS sym) 1);
   312 by (stac (rev_rev_ident RS sym) 1);
   313 br(read_instantiate [("P","%xs. ?P(rev xs)")]list.induct)1;
   313 br(read_instantiate [("P","%xs. ?P(rev xs)")]list.induct)1;
   314 by(ALLGOALS Simp_tac);
   314 by (ALLGOALS Simp_tac);
   315 brs prems 1;
   315 by (resolve_tac prems 1);
   316 bes prems 1;
   316 by (eresolve_tac prems 1);
   317 qed "rev_induct";
   317 qed "rev_induct";
   318 
   318 
   319 Goal  "(xs = [] --> P) -->  (!ys y. xs = ys@[y] --> P) --> P";
   319 Goal  "(xs = [] --> P) -->  (!ys y. xs = ys@[y] --> P) --> P";
   320 by(res_inst_tac [("xs","xs")] rev_induct 1);
   320 by (res_inst_tac [("xs","xs")] rev_induct 1);
   321 by(Auto_tac);
   321 by (Auto_tac);
   322 bind_thm ("rev_exhaust",
   322 bind_thm ("rev_exhaust",
   323   impI RSN (2,allI RSN (2,allI RSN (2,impI RS (result() RS mp RS mp)))));
   323   impI RSN (2,allI RSN (2,allI RSN (2,impI RS (result() RS mp RS mp)))));
   324 
   324 
   325 
   325 
   326 (** mem **)
   326 (** mem **)