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)" |