src/HOL/Library/Cset.thy
changeset 46146 6baea4fca6bd
parent 46133 d9fe85d3d2cd
child 46884 154dc6ec0041
equal deleted inserted replaced
46145:0ec0af1c651d 46146:6baea4fca6bd
   274   "Cset.set = (\<lambda>xs. fold insert xs Cset.empty)"
   274   "Cset.set = (\<lambda>xs. fold insert xs Cset.empty)"
   275 proof (rule ext, rule Cset.set_eqI)
   275 proof (rule ext, rule Cset.set_eqI)
   276   fix xs :: "'a list"
   276   fix xs :: "'a list"
   277   show "member (Cset.set xs) = member (fold insert xs Cset.empty)"
   277   show "member (Cset.set xs) = member (fold insert xs Cset.empty)"
   278     by (simp add: fold_commute_apply [symmetric, where ?h = Set and ?g = Set.insert]
   278     by (simp add: fold_commute_apply [symmetric, where ?h = Set and ?g = Set.insert]
   279       fun_eq_iff Cset.set_def union_set [symmetric])
   279       fun_eq_iff Cset.set_def union_set_fold [symmetric])
   280 qed
   280 qed
   281 
   281 
   282 lemma single_code [code]:
   282 lemma single_code [code]:
   283   "single a = insert a Cset.empty"
   283   "single a = insert a Cset.empty"
   284   by (simp add: Cset.single_def)
   284   by (simp add: Cset.single_def)
   294 lemma inter_project:
   294 lemma inter_project:
   295   "inf A (Cset.set xs) = Cset.set (List.filter (Cset.member A) xs)"
   295   "inf A (Cset.set xs) = Cset.set (List.filter (Cset.member A) xs)"
   296   "inf A (Cset.coset xs) = foldr Cset.remove xs A"
   296   "inf A (Cset.coset xs) = foldr Cset.remove xs A"
   297 proof -
   297 proof -
   298   show "inf A (Cset.set xs) = Cset.set (List.filter (member A) xs)"
   298   show "inf A (Cset.set xs) = Cset.set (List.filter (member A) xs)"
   299     by (simp add: inter project_def Cset.set_def member_def)
   299     by (simp add: project_def Cset.set_def member_def) auto
   300   have *: "\<And>x::'a. Cset.remove = (\<lambda>x. Set \<circ> Set.remove x \<circ> set_of)"
   300   have *: "\<And>x::'a. Cset.remove = (\<lambda>x. Set \<circ> Set.remove x \<circ> set_of)"
   301     by (simp add: fun_eq_iff Set.remove_def)
   301     by (simp add: fun_eq_iff Set.remove_def)
   302   have "set_of \<circ> fold (\<lambda>x. Set \<circ> Set.remove x \<circ> set_of) xs =
   302   have "set_of \<circ> fold (\<lambda>x. Set \<circ> Set.remove x \<circ> set_of) xs =
   303     fold Set.remove xs \<circ> set_of"
   303     fold Set.remove xs \<circ> set_of"
   304     by (rule fold_commute) (simp add: fun_eq_iff)
   304     by (rule fold_commute) (simp add: fun_eq_iff)
   305   then have "fold Set.remove xs (set_of A) = 
   305   then have "fold Set.remove xs (set_of A) = 
   306     set_of (fold (\<lambda>x. Set \<circ> Set.remove x \<circ> set_of) xs A)"
   306     set_of (fold (\<lambda>x. Set \<circ> Set.remove x \<circ> set_of) xs A)"
   307     by (simp add: fun_eq_iff)
   307     by (simp add: fun_eq_iff)
   308   then have "inf A (Cset.coset xs) = fold Cset.remove xs A"
   308   then have "inf A (Cset.coset xs) = fold Cset.remove xs A"
   309     by (simp add: Diff_eq [symmetric] minus_set *)
   309     by (simp add: Diff_eq [symmetric] minus_set_fold *)
   310   moreover have "\<And>x y :: 'a. Cset.remove y \<circ> Cset.remove x = Cset.remove x \<circ> Cset.remove y"
   310   moreover have "\<And>x y :: 'a. Cset.remove y \<circ> Cset.remove x = Cset.remove x \<circ> Cset.remove y"
   311     by (auto simp add: Set.remove_def *)
   311     by (auto simp add: Set.remove_def *)
   312   ultimately show "inf A (Cset.coset xs) = foldr Cset.remove xs A"
   312   ultimately show "inf A (Cset.coset xs) = foldr Cset.remove xs A"
   313     by (simp add: foldr_fold)
   313     by (simp add: foldr_fold)
   314 qed
   314 qed
   324     by (rule fold_commute) (simp add: fun_eq_iff)
   324     by (rule fold_commute) (simp add: fun_eq_iff)
   325   then have "fold Set.insert xs (set_of A) =
   325   then have "fold Set.insert xs (set_of A) =
   326     set_of (fold (\<lambda>x. Set \<circ> Set.insert x \<circ> set_of) xs A)"
   326     set_of (fold (\<lambda>x. Set \<circ> Set.insert x \<circ> set_of) xs A)"
   327     by (simp add: fun_eq_iff)
   327     by (simp add: fun_eq_iff)
   328   then have "sup (Cset.set xs) A = fold Cset.insert xs A"
   328   then have "sup (Cset.set xs) A = fold Cset.insert xs A"
   329     by (simp add: union_set *)
   329     by (simp add: union_set_fold *)
   330   moreover have "\<And>x y :: 'a. Cset.insert y \<circ> Cset.insert x = Cset.insert x \<circ> Cset.insert y"
   330   moreover have "\<And>x y :: 'a. Cset.insert y \<circ> Cset.insert x = Cset.insert x \<circ> Cset.insert y"
   331     by (auto simp add: *)
   331     by (auto simp add: *)
   332   ultimately show "sup (Cset.set xs) A = foldr Cset.insert xs A"
   332   ultimately show "sup (Cset.set xs) A = foldr Cset.insert xs A"
   333     by (simp add: foldr_fold)
   333     by (simp add: foldr_fold)
   334   show "sup (Cset.coset xs) A = Cset.coset (List.filter (Not \<circ> member A) xs)"
   334   show "sup (Cset.coset xs) A = Cset.coset (List.filter (Not \<circ> member A) xs)"