equal
deleted
inserted
replaced
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 |