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