src/HOL/List.ML
changeset 5043 3fdc881e8ff9
parent 4935 1694e2daef8f
child 5077 71043526295f
equal deleted inserted replaced
5042:1f077d63a909 5043:3fdc881e8ff9
    26 qed "length_induct";
    26 qed "length_induct";
    27 
    27 
    28 
    28 
    29 (** "lists": the list-forming operator over sets **)
    29 (** "lists": the list-forming operator over sets **)
    30 
    30 
    31 Goalw lists.defs "!!A B. A<=B ==> lists A <= lists B";
    31 Goalw lists.defs "A<=B ==> lists A <= lists B";
    32 by (rtac lfp_mono 1);
    32 by (rtac lfp_mono 1);
    33 by (REPEAT (ares_tac basic_monos 1));
    33 by (REPEAT (ares_tac basic_monos 1));
    34 qed "lists_mono";
    34 qed "lists_mono";
    35 
    35 
    36 val listsE = lists.mk_cases list.simps  "x#l : lists A";
    36 val listsE = lists.mk_cases list.simps  "x#l : lists A";
    37 AddSEs [listsE];
    37 AddSEs [listsE];
    38 AddSIs lists.intrs;
    38 AddSIs lists.intrs;
    39 
    39 
    40 Goal "!!l. l: lists A ==> l: lists B --> l: lists (A Int B)";
    40 Goal "l: lists A ==> l: lists B --> l: lists (A Int B)";
    41 by (etac lists.induct 1);
    41 by (etac lists.induct 1);
    42 by (ALLGOALS Blast_tac);
    42 by (ALLGOALS Blast_tac);
    43 qed_spec_mp "lists_IntI";
    43 qed_spec_mp "lists_IntI";
    44 
    44 
    45 Goal "lists (A Int B) = lists A Int lists B";
    45 Goal "lists (A Int B) = lists A Int lists B";
    86 by (induct_tac "xs" 1);
    86 by (induct_tac "xs" 1);
    87 by (ALLGOALS Asm_simp_tac);
    87 by (ALLGOALS Asm_simp_tac);
    88 qed "length_rev";
    88 qed "length_rev";
    89 Addsimps [length_rev];
    89 Addsimps [length_rev];
    90 
    90 
    91 Goal "!!xs. xs ~= [] ==> length(tl xs) = (length xs) - 1";
    91 Goal "xs ~= [] ==> length(tl xs) = (length xs) - 1";
    92 by (exhaust_tac "xs" 1);
    92 by (exhaust_tac "xs" 1);
    93 by (ALLGOALS Asm_full_simp_tac);
    93 by (ALLGOALS Asm_full_simp_tac);
    94 qed "length_tl";
    94 qed "length_tl";
    95 Addsimps [length_tl];
    95 Addsimps [length_tl];
    96 
    96 
   207 Goal "hd(xs@ys) = (if xs=[] then hd ys else hd xs)";
   207 Goal "hd(xs@ys) = (if xs=[] then hd ys else hd xs)";
   208 by (induct_tac "xs" 1);
   208 by (induct_tac "xs" 1);
   209 by (ALLGOALS Asm_simp_tac);
   209 by (ALLGOALS Asm_simp_tac);
   210 qed "hd_append";
   210 qed "hd_append";
   211 
   211 
   212 Goal "!!xs. xs ~= [] ==> hd(xs @ ys) = hd xs";
   212 Goal "xs ~= [] ==> hd(xs @ ys) = hd xs";
   213 by (asm_simp_tac (simpset() addsimps [hd_append]
   213 by (asm_simp_tac (simpset() addsimps [hd_append]
   214                            addsplits [split_list_case]) 1);
   214                            addsplits [split_list_case]) 1);
   215 qed "hd_append2";
   215 qed "hd_append2";
   216 Addsimps [hd_append2];
   216 Addsimps [hd_append2];
   217 
   217 
   218 Goal "tl(xs@ys) = (case xs of [] => tl(ys) | z#zs => zs@ys)";
   218 Goal "tl(xs@ys) = (case xs of [] => tl(ys) | z#zs => zs@ys)";
   219 by (simp_tac (simpset() addsplits [split_list_case]) 1);
   219 by (simp_tac (simpset() addsplits [split_list_case]) 1);
   220 qed "tl_append";
   220 qed "tl_append";
   221 
   221 
   222 Goal "!!xs. xs ~= [] ==> tl(xs @ ys) = (tl xs) @ ys";
   222 Goal "xs ~= [] ==> tl(xs @ ys) = (tl xs) @ ys";
   223 by (asm_simp_tac (simpset() addsimps [tl_append]
   223 by (asm_simp_tac (simpset() addsimps [tl_append]
   224                            addsplits [split_list_case]) 1);
   224                            addsplits [split_list_case]) 1);
   225 qed "tl_append2";
   225 qed "tl_append2";
   226 Addsimps [tl_append2];
   226 Addsimps [tl_append2];
   227 
   227 
   566 Goal "x:set(butlast xs) --> x:set xs";
   566 Goal "x:set(butlast xs) --> x:set xs";
   567 by (induct_tac "xs" 1);
   567 by (induct_tac "xs" 1);
   568 by (ALLGOALS Asm_simp_tac);
   568 by (ALLGOALS Asm_simp_tac);
   569 qed_spec_mp "in_set_butlastD";
   569 qed_spec_mp "in_set_butlastD";
   570 
   570 
   571 Goal "!!xs. x:set(butlast xs) ==> x:set(butlast(xs@ys))";
   571 Goal "x:set(butlast xs) ==> x:set(butlast(xs@ys))";
   572 by (asm_simp_tac (simpset() addsimps [butlast_append]) 1);
   572 by (asm_simp_tac (simpset() addsimps [butlast_append]) 1);
   573 by (blast_tac (claset() addDs [in_set_butlastD]) 1);
   573 by (blast_tac (claset() addDs [in_set_butlastD]) 1);
   574 qed "in_set_butlast_appendI1";
   574 qed "in_set_butlast_appendI1";
   575 
   575 
   576 Goal "!!xs. x:set(butlast ys) ==> x:set(butlast(xs@ys))";
   576 Goal "x:set(butlast ys) ==> x:set(butlast(xs@ys))";
   577 by (asm_simp_tac (simpset() addsimps [butlast_append]) 1);
   577 by (asm_simp_tac (simpset() addsimps [butlast_append]) 1);
   578 by (Clarify_tac 1);
   578 by (Clarify_tac 1);
   579 by (Full_simp_tac 1);
   579 by (Full_simp_tac 1);
   580 qed "in_set_butlast_appendI2";
   580 qed "in_set_butlast_appendI2";
   581 
   581 
   790 Goal "set(replicate (Suc n) x) = {x}";
   790 Goal "set(replicate (Suc n) x) = {x}";
   791 by (induct_tac "n" 1);
   791 by (induct_tac "n" 1);
   792 by (ALLGOALS Asm_full_simp_tac);
   792 by (ALLGOALS Asm_full_simp_tac);
   793 val lemma = result();
   793 val lemma = result();
   794 
   794 
   795 Goal "!!n. n ~= 0 ==> set(replicate n x) = {x}";
   795 Goal "n ~= 0 ==> set(replicate n x) = {x}";
   796 by (fast_tac (claset() addSDs [not0_implies_Suc] addSIs [lemma]) 1);
   796 by (fast_tac (claset() addSDs [not0_implies_Suc] addSIs [lemma]) 1);
   797 qed "set_replicate";
   797 qed "set_replicate";
   798 Addsimps [set_replicate];
   798 Addsimps [set_replicate];