src/HOL/Library/Multiset.thy
changeset 61585 a9599d3d7610
parent 61566 c3d6e570ccef
child 61605 1bf7b186542e
equal deleted inserted replaced
61584:f06e5a5a4b46 61585:a9599d3d7610
   807 end
   807 end
   808 
   808 
   809 text \<open>
   809 text \<open>
   810   A note on code generation: When defining some function containing a
   810   A note on code generation: When defining some function containing a
   811   subterm @{term "fold_mset F"}, code generation is not automatic. When
   811   subterm @{term "fold_mset F"}, code generation is not automatic. When
   812   interpreting locale @{text left_commutative} with @{text F}, the
   812   interpreting locale \<open>left_commutative\<close> with \<open>F\<close>, the
   813   would be code thms for @{const fold_mset} become thms like
   813   would be code thms for @{const fold_mset} become thms like
   814   @{term "fold_mset F z {#} = z"} where @{text F} is not a pattern but
   814   @{term "fold_mset F z {#} = z"} where \<open>F\<close> is not a pattern but
   815   contains defined symbols, i.e.\ is not a code thm. Hence a separate
   815   contains defined symbols, i.e.\ is not a code thm. Hence a separate
   816   constant with its own code thms needs to be introduced for @{text
   816   constant with its own code thms needs to be introduced for \<open>F\<close>. See the image operator below.
   817   F}. See the image operator below.
       
   818 \<close>
   817 \<close>
   819 
   818 
   820 
   819 
   821 subsection \<open>Image\<close>
   820 subsection \<open>Image\<close>
   822 
   821 
  1081   next
  1080   next
  1082     case True from True \<open>x \<notin> A\<close> show ?thesis by (induct A) auto
  1081     case True from True \<open>x \<notin> A\<close> show ?thesis by (induct A) auto
  1083   qed
  1082   qed
  1084   then show "PROP ?P" "PROP ?Q" "PROP ?R"
  1083   then show "PROP ?P" "PROP ?Q" "PROP ?R"
  1085   by (auto elim!: Set.set_insert)
  1084   by (auto elim!: Set.set_insert)
  1086 qed -- \<open>TODO: maybe define @{const mset_set} also in terms of @{const Abs_multiset}\<close>
  1085 qed \<comment> \<open>TODO: maybe define @{const mset_set} also in terms of @{const Abs_multiset}\<close>
  1087 
  1086 
  1088 lemma elem_mset_set[simp, intro]: "finite A \<Longrightarrow> x \<in># mset_set A \<longleftrightarrow> x \<in> A"
  1087 lemma elem_mset_set[simp, intro]: "finite A \<Longrightarrow> x \<in># mset_set A \<longleftrightarrow> x \<in> A"
  1089   by (induct A rule: finite_induct) simp_all
  1088   by (induct A rule: finite_induct) simp_all
  1090 
  1089 
  1091 context linorder
  1090 context linorder
  1347   "mset (sort_key k xs) = mset xs"
  1346   "mset (sort_key k xs) = mset xs"
  1348   by (induct xs) (simp_all add: ac_simps)
  1347   by (induct xs) (simp_all add: ac_simps)
  1349 
  1348 
  1350 text \<open>
  1349 text \<open>
  1351   This lemma shows which properties suffice to show that a function
  1350   This lemma shows which properties suffice to show that a function
  1352   @{text "f"} with @{text "f xs = ys"} behaves like sort.
  1351   \<open>f\<close> with \<open>f xs = ys\<close> behaves like sort.
  1353 \<close>
  1352 \<close>
  1354 
  1353 
  1355 lemma properties_for_sort_key:
  1354 lemma properties_for_sort_key:
  1356   assumes "mset ys = mset xs"
  1355   assumes "mset ys = mset xs"
  1357     and "\<And>k. k \<in> set ys \<Longrightarrow> filter (\<lambda>x. f k = f x) ys = filter (\<lambda>x. f k = f x) xs"
  1356     and "\<And>k. k \<in> set ys \<Longrightarrow> filter (\<lambda>x. f k = f x) ys = filter (\<lambda>x. f k = f x) xs"
  2104 
  2103 
  2105 declare set_mset_mset [code]
  2104 declare set_mset_mset [code]
  2106 
  2105 
  2107 declare sorted_list_of_multiset_mset [code]
  2106 declare sorted_list_of_multiset_mset [code]
  2108 
  2107 
  2109 lemma [code]: -- \<open>not very efficient, but representation-ignorant!\<close>
  2108 lemma [code]: \<comment> \<open>not very efficient, but representation-ignorant!\<close>
  2110   "mset_set A = mset (sorted_list_of_set A)"
  2109   "mset_set A = mset (sorted_list_of_set A)"
  2111   apply (cases "finite A")
  2110   apply (cases "finite A")
  2112   apply simp_all
  2111   apply simp_all
  2113   apply (induct A rule: finite_induct)
  2112   apply (induct A rule: finite_induct)
  2114   apply (simp_all add: add.commute)
  2113   apply (simp_all add: add.commute)