src/HOL/Library/Multiset.thy
changeset 69442 fc44536fa505
parent 69260 0a9688695a1b
child 69593 3dda49e08b9d
equal deleted inserted replaced
69441:0bd51c6aaa8b 69442:fc44536fa505
  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]: