src/HOL/Library/Cset.thy
changeset 45970 b6d0cff57d96
parent 44563 01b2732cf4ad
child 45986 c9e50153e5ae
equal deleted inserted replaced
45969:562e99c3d316 45970:b6d0cff57d96
    22   by (fact set_of_inverse)
    22   by (fact set_of_inverse)
    23 
    23 
    24 definition member :: "'a Cset.set \<Rightarrow> 'a \<Rightarrow> bool" where
    24 definition member :: "'a Cset.set \<Rightarrow> 'a \<Rightarrow> bool" where
    25   "member A x \<longleftrightarrow> x \<in> set_of A"
    25   "member A x \<longleftrightarrow> x \<in> set_of A"
    26 
    26 
    27 lemma member_set_of:
       
    28   "set_of = member"
       
    29   by (rule ext)+ (simp add: member_def mem_def)
       
    30 
       
    31 lemma member_Set [simp]:
    27 lemma member_Set [simp]:
    32   "member (Set A) x \<longleftrightarrow> x \<in> A"
    28   "member (Set A) x \<longleftrightarrow> x \<in> A"
    33   by (simp add: member_def)
    29   by (simp add: member_def)
    34 
    30 
    35 lemma Set_inject [simp]:
    31 lemma Set_inject [simp]:
    36   "Set A = Set B \<longleftrightarrow> A = B"
    32   "Set A = Set B \<longleftrightarrow> A = B"
    37   by (simp add: Set_inject)
    33   by (simp add: Set_inject)
    38 
    34 
    39 lemma set_eq_iff:
    35 lemma set_eq_iff:
    40   "A = B \<longleftrightarrow> member A = member B"
    36   "A = B \<longleftrightarrow> member A = member B"
    41   by (auto simp add: fun_eq_iff set_of_inject [symmetric] member_def mem_def)
    37   by (auto simp add: fun_eq_iff set_of_inject [symmetric] member_def)
    42 hide_fact (open) set_eq_iff
    38 hide_fact (open) set_eq_iff
    43 
    39 
    44 lemma set_eqI:
    40 lemma set_eqI:
    45   "member A = member B \<Longrightarrow> A = B"
    41   "member A = member B \<Longrightarrow> A = B"
    46   by (simp add: Cset.set_eq_iff)
    42   by (simp add: Cset.set_eq_iff)
    74 
    70 
    75 definition minus_set :: "'a Cset.set \<Rightarrow> 'a Cset.set \<Rightarrow> 'a Cset.set" where
    71 definition minus_set :: "'a Cset.set \<Rightarrow> 'a Cset.set \<Rightarrow> 'a Cset.set" where
    76   [simp]: "A - B = Set (set_of A - set_of B)"
    72   [simp]: "A - B = Set (set_of A - set_of B)"
    77 
    73 
    78 instance proof
    74 instance proof
    79 qed (auto intro!: Cset.set_eqI simp add: member_def mem_def)
    75 qed (auto intro!: Cset.set_eqI simp add: member_def)
    80 
    76 
    81 end
    77 end
    82 
    78 
    83 instantiation Cset.set :: (type) complete_lattice
    79 instantiation Cset.set :: (type) complete_lattice
    84 begin
    80 begin
   362 lemma of_pred_code [code]:
   358 lemma of_pred_code [code]:
   363   "of_pred (Predicate.Seq f) = (case f () of
   359   "of_pred (Predicate.Seq f) = (case f () of
   364      Predicate.Empty \<Rightarrow> Cset.empty
   360      Predicate.Empty \<Rightarrow> Cset.empty
   365    | Predicate.Insert x P \<Rightarrow> Cset.insert x (of_pred P)
   361    | Predicate.Insert x P \<Rightarrow> Cset.insert x (of_pred P)
   366    | Predicate.Join P xq \<Rightarrow> sup (of_pred P) (of_seq xq))"
   362    | Predicate.Join P xq \<Rightarrow> sup (of_pred P) (of_seq xq))"
   367   apply (auto split: seq.split simp add: Predicate.Seq_def of_pred_def Cset.set_eq_iff sup_apply eval_member [symmetric] member_def [symmetric] Collect_def mem_def member_set_of)
   363   by (auto split: seq.split simp add: Predicate.Seq_def of_pred_def Cset.set_eq_iff sup_apply eval_member [symmetric] member_def [symmetric])
   368   apply (unfold Set.insert_def Collect_def sup_apply member_set_of)
       
   369   apply simp_all
       
   370   done
       
   371 
   364 
   372 lemma of_seq_code [code]:
   365 lemma of_seq_code [code]:
   373   "of_seq Predicate.Empty = Cset.empty"
   366   "of_seq Predicate.Empty = Cset.empty"
   374   "of_seq (Predicate.Insert x P) = Cset.insert x (of_pred P)"
   367   "of_seq (Predicate.Insert x P) = Cset.insert x (of_pred P)"
   375   "of_seq (Predicate.Join P xq) = sup (of_pred P) (of_seq xq)"
   368   "of_seq (Predicate.Join P xq) = sup (of_pred P) (of_seq xq)"
   376   apply (auto simp add: of_seq_def of_pred_def Cset.set_eq_iff mem_def Collect_def)
   369   by (auto simp add: of_seq_def of_pred_def Cset.set_eq_iff)
   377   apply (unfold Set.insert_def Collect_def sup_apply member_set_of)
       
   378   apply simp_all
       
   379   done
       
   380 
   370 
   381 lemma bind_set:
   371 lemma bind_set:
   382   "Cset.bind (Cset.set xs) f = fold (sup \<circ> f) xs (Cset.set [])"
   372   "Cset.bind (Cset.set xs) f = fold (sup \<circ> f) xs (Cset.set [])"
   383   by (simp add: Cset.bind_def SUPR_set_fold)
   373   by (simp add: Cset.bind_def SUPR_set_fold)
   384 hide_fact (open) bind_set
   374 hide_fact (open) bind_set
   385 
   375 
   386 lemma pred_of_cset_set:
   376 lemma pred_of_cset_set:
   387   "pred_of_cset (Cset.set xs) = foldr sup (List.map Predicate.single xs) bot"
   377   "pred_of_cset (Cset.set xs) = foldr sup (List.map Predicate.single xs) bot"
   388 proof -
   378 proof -
   389   have "pred_of_cset (Cset.set xs) = Predicate.Pred (\<lambda>x. x \<in> set xs)"
   379   have "pred_of_cset (Cset.set xs) = Predicate.Pred (\<lambda>x. x \<in> set xs)"
   390     by (simp add: Cset.pred_of_cset_def member_set)
   380     by (simp add: Cset.pred_of_cset_def)
   391   moreover have "foldr sup (List.map Predicate.single xs) bot = \<dots>"
   381   moreover have "foldr sup (List.map Predicate.single xs) bot = \<dots>"
   392     by (induct xs) (auto simp add: bot_pred_def intro: pred_eqI, simp add: mem_def)
   382     by (induct xs) (auto simp add: bot_pred_def intro: pred_eqI)
   393   ultimately show ?thesis by simp
   383   ultimately show ?thesis by simp
   394 qed
   384 qed
   395 hide_fact (open) pred_of_cset_set
   385 hide_fact (open) pred_of_cset_set
   396 
   386 
   397 no_notation bind (infixl "\<guillemotright>=" 70)
   387 no_notation bind (infixl "\<guillemotright>=" 70)