src/HOL/List.thy
changeset 63092 a949b2a5f51d
parent 63040 eb4ddd18d635
child 63099 af0e964aad7b
equal deleted inserted replaced
63091:54f16a0a3069 63092:a949b2a5f51d
  2295 
  2295 
  2296 lemma dropWhile_eq_drop: "dropWhile P xs = drop (length (takeWhile P xs)) xs"
  2296 lemma dropWhile_eq_drop: "dropWhile P xs = drop (length (takeWhile P xs)) xs"
  2297 by (induct xs) auto
  2297 by (induct xs) auto
  2298 
  2298 
  2299 lemma hd_dropWhile: "dropWhile P xs \<noteq> [] \<Longrightarrow> \<not> P (hd (dropWhile P xs))"
  2299 lemma hd_dropWhile: "dropWhile P xs \<noteq> [] \<Longrightarrow> \<not> P (hd (dropWhile P xs))"
  2300 using assms by (induct xs) auto
  2300 by (induct xs) auto
  2301 
  2301 
  2302 lemma takeWhile_eq_filter:
  2302 lemma takeWhile_eq_filter:
  2303   assumes "\<And> x. x \<in> set (dropWhile P xs) \<Longrightarrow> \<not> P x"
  2303   assumes "\<And> x. x \<in> set (dropWhile P xs) \<Longrightarrow> \<not> P x"
  2304   shows "takeWhile P xs = filter P xs"
  2304   shows "takeWhile P xs = filter P xs"
  2305 proof -
  2305 proof -
  4954   "\<not> P x \<Longrightarrow> filter P (insort_key f x xs) = filter P xs"
  4954   "\<not> P x \<Longrightarrow> filter P (insort_key f x xs) = filter P xs"
  4955   by (induct xs) simp_all
  4955   by (induct xs) simp_all
  4956 
  4956 
  4957 lemma filter_insort:
  4957 lemma filter_insort:
  4958   "sorted (map f xs) \<Longrightarrow> P x \<Longrightarrow> filter P (insort_key f x xs) = insort_key f x (filter P xs)"
  4958   "sorted (map f xs) \<Longrightarrow> P x \<Longrightarrow> filter P (insort_key f x xs) = insort_key f x (filter P xs)"
  4959   using assms by (induct xs)
  4959   by (induct xs) (auto simp add: sorted_Cons, subst insort_is_Cons, auto)
  4960     (auto simp add: sorted_Cons, subst insort_is_Cons, auto)
       
  4961 
  4960 
  4962 lemma filter_sort:
  4961 lemma filter_sort:
  4963   "filter P (sort_key f xs) = sort_key f (filter P xs)"
  4962   "filter P (sort_key f xs) = sort_key f (filter P xs)"
  4964   by (induct xs) (simp_all add: filter_insort_triv filter_insort)
  4963   by (induct xs) (simp_all add: filter_insort_triv filter_insort)
  4965 
  4964