equal
deleted
inserted
replaced
24 notation (xsymbols) |
24 notation (xsymbols) |
25 Melem (infix "\<in>#" 50) |
25 Melem (infix "\<in>#" 50) |
26 |
26 |
27 lemma multiset_ext_iff: |
27 lemma multiset_ext_iff: |
28 "M = N \<longleftrightarrow> (\<forall>a. count M a = count N a)" |
28 "M = N \<longleftrightarrow> (\<forall>a. count M a = count N a)" |
29 by (simp only: count_inject [symmetric] expand_fun_eq) |
29 by (simp only: count_inject [symmetric] ext_iff) |
30 |
30 |
31 lemma multiset_ext: |
31 lemma multiset_ext: |
32 "(\<And>x. count A x = count B x) \<Longrightarrow> A = B" |
32 "(\<And>x. count A x = count B x) \<Longrightarrow> A = B" |
33 using multiset_ext_iff by auto |
33 using multiset_ext_iff by auto |
34 |
34 |
579 apply (rule count_inverse [THEN subst]) |
579 apply (rule count_inverse [THEN subst]) |
580 apply (rule count [THEN rep_multiset_induct]) |
580 apply (rule count [THEN rep_multiset_induct]) |
581 apply (rule empty [unfolded defns]) |
581 apply (rule empty [unfolded defns]) |
582 apply (subgoal_tac "f(b := f b + 1) = (\<lambda>a. f a + (if a=b then 1 else 0))") |
582 apply (subgoal_tac "f(b := f b + 1) = (\<lambda>a. f a + (if a=b then 1 else 0))") |
583 prefer 2 |
583 prefer 2 |
584 apply (simp add: expand_fun_eq) |
584 apply (simp add: ext_iff) |
585 apply (erule ssubst) |
585 apply (erule ssubst) |
586 apply (erule Abs_multiset_inverse [THEN subst]) |
586 apply (erule Abs_multiset_inverse [THEN subst]) |
587 apply (drule add') |
587 apply (drule add') |
588 apply (simp add: aux) |
588 apply (simp add: aux) |
589 done |
589 done |
881 then show "x \<in> dom (map_of xs)" by auto |
881 then show "x \<in> dom (map_of xs)" by auto |
882 qed |
882 qed |
883 with finite_dom_map_of [of xs] have "finite ?A" |
883 with finite_dom_map_of [of xs] have "finite ?A" |
884 by (auto intro: finite_subset) |
884 by (auto intro: finite_subset) |
885 then show ?thesis |
885 then show ?thesis |
886 by (simp add: count_of_def expand_fun_eq multiset_def) |
886 by (simp add: count_of_def ext_iff multiset_def) |
887 qed |
887 qed |
888 |
888 |
889 lemma count_simps [simp]: |
889 lemma count_simps [simp]: |
890 "count_of [] = (\<lambda>_. 0)" |
890 "count_of [] = (\<lambda>_. 0)" |
891 "count_of ((x, n) # xs) = (\<lambda>y. if x = y then n else count_of xs y)" |
891 "count_of ((x, n) # xs) = (\<lambda>y. if x = y then n else count_of xs y)" |
892 by (simp_all add: count_of_def expand_fun_eq) |
892 by (simp_all add: count_of_def ext_iff) |
893 |
893 |
894 lemma count_of_empty: |
894 lemma count_of_empty: |
895 "x \<notin> fst ` set xs \<Longrightarrow> count_of xs x = 0" |
895 "x \<notin> fst ` set xs \<Longrightarrow> count_of xs x = 0" |
896 by (induct xs) (simp_all add: count_of_def) |
896 by (induct xs) (simp_all add: count_of_def) |
897 |
897 |