src/HOL/List.thy
changeset 62390 842917225d56
parent 62343 24106dc44def
child 62580 7011429f44f9
equal deleted inserted replaced
62380:29800666e526 62390:842917225d56
   618 
   618 
   619 fun tac ctxt [] =
   619 fun tac ctxt [] =
   620       resolve_tac ctxt [set_singleton] 1 ORELSE
   620       resolve_tac ctxt [set_singleton] 1 ORELSE
   621       resolve_tac ctxt [inst_Collect_mem_eq] 1
   621       resolve_tac ctxt [inst_Collect_mem_eq] 1
   622   | tac ctxt (If :: cont) =
   622   | tac ctxt (If :: cont) =
   623       Splitter.split_tac ctxt @{thms split_if} 1
   623       Splitter.split_tac ctxt @{thms if_split} 1
   624       THEN resolve_tac ctxt @{thms conjI} 1
   624       THEN resolve_tac ctxt @{thms conjI} 1
   625       THEN resolve_tac ctxt @{thms impI} 1
   625       THEN resolve_tac ctxt @{thms impI} 1
   626       THEN Subgoal.FOCUS (fn {prems, context = ctxt', ...} =>
   626       THEN Subgoal.FOCUS (fn {prems, context = ctxt', ...} =>
   627         CONVERSION (right_hand_set_comprehension_conv (K
   627         CONVERSION (right_hand_set_comprehension_conv (K
   628           (HOLogic.conj_conv (Conv.rewr_conv (List.last prems RS @{thm Eq_TrueI})) Conv.all_conv
   628           (HOLogic.conj_conv (Conv.rewr_conv (List.last prems RS @{thm Eq_TrueI})) Conv.all_conv
  1467   "\<lbrakk> x : set xs; ~ P x \<rbrakk> \<Longrightarrow> length(filter P xs) < length xs"
  1467   "\<lbrakk> x : set xs; ~ P x \<rbrakk> \<Longrightarrow> length(filter P xs) < length xs"
  1468 proof (induct xs)
  1468 proof (induct xs)
  1469   case Nil thus ?case by simp
  1469   case Nil thus ?case by simp
  1470 next
  1470 next
  1471   case (Cons x xs) thus ?case
  1471   case (Cons x xs) thus ?case
  1472     apply (auto split:split_if_asm)
  1472     apply (auto split:if_split_asm)
  1473     using length_filter_le[of P xs] apply arith
  1473     using length_filter_le[of P xs] apply arith
  1474   done
  1474   done
  1475 qed
  1475 qed
  1476 
  1476 
  1477 lemma length_filter_conv_card:
  1477 lemma length_filter_conv_card:
  1916 lemma append_butlast_last_id [simp]:
  1916 lemma append_butlast_last_id [simp]:
  1917   "xs \<noteq> [] ==> butlast xs @ [last xs] = xs"
  1917   "xs \<noteq> [] ==> butlast xs @ [last xs] = xs"
  1918 by (induct xs) auto
  1918 by (induct xs) auto
  1919 
  1919 
  1920 lemma in_set_butlastD: "x : set (butlast xs) ==> x : set xs"
  1920 lemma in_set_butlastD: "x : set (butlast xs) ==> x : set xs"
  1921 by (induct xs) (auto split: split_if_asm)
  1921 by (induct xs) (auto split: if_split_asm)
  1922 
  1922 
  1923 lemma in_set_butlast_appendI:
  1923 lemma in_set_butlast_appendI:
  1924   "x : set (butlast xs) | x : set (butlast ys) ==> x : set (butlast (xs @ ys))"
  1924   "x : set (butlast xs) | x : set (butlast ys) ==> x : set (butlast (xs @ ys))"
  1925 by (auto dest: in_set_butlastD simp add: butlast_append)
  1925 by (auto dest: in_set_butlastD simp add: butlast_append)
  1926 
  1926 
  2259 lemma dropWhile_last:
  2259 lemma dropWhile_last:
  2260   "x \<in> set xs \<Longrightarrow> \<not> P x \<Longrightarrow> last (dropWhile P xs) = last xs"
  2260   "x \<in> set xs \<Longrightarrow> \<not> P x \<Longrightarrow> last (dropWhile P xs) = last xs"
  2261 by (auto simp add: dropWhile_append3 in_set_conv_decomp)
  2261 by (auto simp add: dropWhile_append3 in_set_conv_decomp)
  2262 
  2262 
  2263 lemma set_dropWhileD: "x \<in> set (dropWhile P xs) \<Longrightarrow> x \<in> set xs"
  2263 lemma set_dropWhileD: "x \<in> set (dropWhile P xs) \<Longrightarrow> x \<in> set xs"
  2264 by (induct xs) (auto split: split_if_asm)
  2264 by (induct xs) (auto split: if_split_asm)
  2265 
  2265 
  2266 lemma set_takeWhileD: "x : set (takeWhile P xs) ==> x : set xs \<and> P x"
  2266 lemma set_takeWhileD: "x : set (takeWhile P xs) ==> x : set xs \<and> P x"
  2267 by (induct xs) (auto split: split_if_asm)
  2267 by (induct xs) (auto split: if_split_asm)
  2268 
  2268 
  2269 lemma takeWhile_eq_all_conv[simp]:
  2269 lemma takeWhile_eq_all_conv[simp]:
  2270   "(takeWhile P xs = xs) = (\<forall>x \<in> set xs. P x)"
  2270   "(takeWhile P xs = xs) = (\<forall>x \<in> set xs. P x)"
  2271 by(induct xs, auto)
  2271 by(induct xs, auto)
  2272 
  2272 
  3320   proof (cases "x \<in> set xs")
  3320   proof (cases "x \<in> set xs")
  3321     case False with Cons show ?thesis by simp
  3321     case False with Cons show ?thesis by simp
  3322   next
  3322   next
  3323     case True with Cons.prems
  3323     case True with Cons.prems
  3324     have "card (set xs) = Suc (length xs)"
  3324     have "card (set xs) = Suc (length xs)"
  3325       by (simp add: card_insert_if split: split_if_asm)
  3325       by (simp add: card_insert_if split: if_split_asm)
  3326     moreover have "card (set xs) \<le> length xs" by (rule card_length)
  3326     moreover have "card (set xs) \<le> length xs" by (rule card_length)
  3327     ultimately have False by simp
  3327     ultimately have False by simp
  3328     thus ?thesis ..
  3328     thus ?thesis ..
  3329   qed
  3329   qed
  3330 qed
  3330 qed
  3333 by (induct xs) (auto)
  3333 by (induct xs) (auto)
  3334 
  3334 
  3335 lemma not_distinct_decomp: "~ distinct ws ==> EX xs ys zs y. ws = xs@[y]@ys@[y]@zs"
  3335 lemma not_distinct_decomp: "~ distinct ws ==> EX xs ys zs y. ws = xs@[y]@ys@[y]@zs"
  3336 apply (induct n == "length ws" arbitrary:ws) apply simp
  3336 apply (induct n == "length ws" arbitrary:ws) apply simp
  3337 apply(case_tac ws) apply simp
  3337 apply(case_tac ws) apply simp
  3338 apply (simp split:split_if_asm)
  3338 apply (simp split:if_split_asm)
  3339 apply (metis Cons_eq_appendI eq_Nil_appendI split_list)
  3339 apply (metis Cons_eq_appendI eq_Nil_appendI split_list)
  3340 done
  3340 done
  3341 
  3341 
  3342 lemma not_distinct_conv_prefix:
  3342 lemma not_distinct_conv_prefix:
  3343   defines "dec as xs y ys \<equiv> y \<in> set xs \<and> distinct xs \<and> as = xs @ y # ys"
  3343   defines "dec as xs y ys \<equiv> y \<in> set xs \<and> distinct xs \<and> as = xs @ y # ys"
  3655   "remdups_adj (xs\<^sub>1 @ x # xs\<^sub>2) = remdups_adj (xs\<^sub>1 @ [x]) @ tl (remdups_adj (x # xs\<^sub>2))"
  3655   "remdups_adj (xs\<^sub>1 @ x # xs\<^sub>2) = remdups_adj (xs\<^sub>1 @ [x]) @ tl (remdups_adj (x # xs\<^sub>2))"
  3656 by (induct xs\<^sub>1 rule: remdups_adj.induct, simp_all)
  3656 by (induct xs\<^sub>1 rule: remdups_adj.induct, simp_all)
  3657 
  3657 
  3658 lemma remdups_adj_singleton:
  3658 lemma remdups_adj_singleton:
  3659   "remdups_adj xs = [x] \<Longrightarrow> xs = replicate (length xs) x"
  3659   "remdups_adj xs = [x] \<Longrightarrow> xs = replicate (length xs) x"
  3660 by (induct xs rule: remdups_adj.induct, auto split: split_if_asm)
  3660 by (induct xs rule: remdups_adj.induct, auto split: if_split_asm)
  3661 
  3661 
  3662 lemma remdups_adj_map_injective:
  3662 lemma remdups_adj_map_injective:
  3663   assumes "inj f"
  3663   assumes "inj f"
  3664   shows "remdups_adj (map f xs) = map f (remdups_adj xs)"
  3664   shows "remdups_adj (map f xs) = map f (remdups_adj xs)"
  3665 by (induct xs rule: remdups_adj.induct) (auto simp add: injD[OF assms])
  3665 by (induct xs rule: remdups_adj.induct) (auto simp add: injD[OF assms])
  4812   "sorted l \<Longrightarrow> sorted (remdups l)"
  4812   "sorted l \<Longrightarrow> sorted (remdups l)"
  4813 by (induct l) (auto simp: sorted_Cons)
  4813 by (induct l) (auto simp: sorted_Cons)
  4814 
  4814 
  4815 lemma sorted_remdups_adj[simp]:
  4815 lemma sorted_remdups_adj[simp]:
  4816   "sorted xs \<Longrightarrow> sorted (remdups_adj xs)"
  4816   "sorted xs \<Longrightarrow> sorted (remdups_adj xs)"
  4817 by (induct xs rule: remdups_adj.induct, simp_all split: split_if_asm add: sorted_Cons)
  4817 by (induct xs rule: remdups_adj.induct, simp_all split: if_split_asm add: sorted_Cons)
  4818 
  4818 
  4819 lemma sorted_distinct_set_unique:
  4819 lemma sorted_distinct_set_unique:
  4820 assumes "sorted xs" "distinct xs" "sorted ys" "distinct ys" "set xs = set ys"
  4820 assumes "sorted xs" "distinct xs" "sorted ys" "distinct ys" "set xs = set ys"
  4821 shows "xs = ys"
  4821 shows "xs = ys"
  4822 proof -
  4822 proof -
  6764   "Id_on (set xs) = set [(x, x). x \<leftarrow> xs]"
  6764   "Id_on (set xs) = set [(x, x). x \<leftarrow> xs]"
  6765   by (auto simp add: Id_on_def)
  6765   by (auto simp add: Id_on_def)
  6766 
  6766 
  6767 lemma [code]:
  6767 lemma [code]:
  6768   "R `` S = List.map_project (%(x, y). if x : S then Some y else None) R"
  6768   "R `` S = List.map_project (%(x, y). if x : S then Some y else None) R"
  6769 unfolding map_project_def by (auto split: prod.split split_if_asm)
  6769 unfolding map_project_def by (auto split: prod.split if_split_asm)
  6770 
  6770 
  6771 lemma trancl_set_ntrancl [code]:
  6771 lemma trancl_set_ntrancl [code]:
  6772   "trancl (set xs) = ntrancl (card (set xs) - 1) (set xs)"
  6772   "trancl (set xs) = ntrancl (card (set xs) - 1) (set xs)"
  6773   by (simp add: finite_trancl_ntranl)
  6773   by (simp add: finite_trancl_ntranl)
  6774 
  6774