equal
deleted
inserted
replaced
2613 "sort_key f xs = sort_key f [x\<leftarrow>xs. f x < f (xs ! (length xs div 2))] |
2613 "sort_key f xs = sort_key f [x\<leftarrow>xs. f x < f (xs ! (length xs div 2))] |
2614 @ [x\<leftarrow>xs. f x = f (xs ! (length xs div 2))] |
2614 @ [x\<leftarrow>xs. f x = f (xs ! (length xs div 2))] |
2615 @ sort_key f [x\<leftarrow>xs. f x > f (xs ! (length xs div 2))]" (is "sort_key f ?lhs = ?rhs") |
2615 @ sort_key f [x\<leftarrow>xs. f x > f (xs ! (length xs div 2))]" (is "sort_key f ?lhs = ?rhs") |
2616 proof (rule properties_for_sort_key) |
2616 proof (rule properties_for_sort_key) |
2617 show "mset ?rhs = mset ?lhs" |
2617 show "mset ?rhs = mset ?lhs" |
2618 by (rule multiset_eqI) (auto simp add: mset_filter) |
2618 by (rule multiset_eqI) auto |
2619 show "sorted (map f ?rhs)" |
2619 show "sorted (map f ?rhs)" |
2620 by (auto simp add: sorted_append intro: sorted_map_same) |
2620 by (auto simp add: sorted_append intro: sorted_map_same) |
2621 next |
2621 next |
2622 fix l |
2622 fix l |
2623 assume "l \<in> set ?rhs" |
2623 assume "l \<in> set ?rhs" |
3386 |
3386 |
3387 lemma [code]: "image_mset f (mset xs) = mset (map f xs)" |
3387 lemma [code]: "image_mset f (mset xs) = mset (map f xs)" |
3388 by simp |
3388 by simp |
3389 |
3389 |
3390 lemma [code]: "filter_mset f (mset xs) = mset (filter f xs)" |
3390 lemma [code]: "filter_mset f (mset xs) = mset (filter f xs)" |
3391 by (simp add: mset_filter) |
3391 by simp |
3392 |
3392 |
3393 lemma [code]: "mset xs - mset ys = mset (fold remove1 ys xs)" |
3393 lemma [code]: "mset xs - mset ys = mset (fold remove1 ys xs)" |
3394 by (rule sym, induct ys arbitrary: xs) (simp_all add: diff_add diff_right_commute diff_diff_add) |
3394 by (rule sym, induct ys arbitrary: xs) (simp_all add: diff_add diff_right_commute diff_diff_add) |
3395 |
3395 |
3396 lemma [code]: |
3396 lemma [code]: |