src/HOL/List.thy
changeset 54868 bab6cade3cc5
parent 54863 82acc20ded73
child 54885 3a478d0a0e87
equal deleted inserted replaced
54867:c21a2465cac1 54868:bab6cade3cc5
  5016 text{* This function maps (finite) linearly ordered sets to sorted
  5016 text{* This function maps (finite) linearly ordered sets to sorted
  5017 lists. Warning: in most cases it is not a good idea to convert from
  5017 lists. Warning: in most cases it is not a good idea to convert from
  5018 sets to lists but one should convert in the other direction (via
  5018 sets to lists but one should convert in the other direction (via
  5019 @{const set}). *}
  5019 @{const set}). *}
  5020 
  5020 
  5021 definition (in linorder) sorted_list_of_set :: "'a set \<Rightarrow> 'a list" where
  5021 context linorder
       
  5022 begin
       
  5023 
       
  5024 definition sorted_list_of_set :: "'a set \<Rightarrow> 'a list" where
  5022   "sorted_list_of_set = folding.F insort []"
  5025   "sorted_list_of_set = folding.F insort []"
  5023 
  5026 
  5024 sublocale linorder < sorted_list_of_set!: folding insort Nil
  5027 sublocale sorted_list_of_set!: folding insort Nil
  5025 where
  5028 where
  5026   "folding.F insort [] = sorted_list_of_set"
  5029   "folding.F insort [] = sorted_list_of_set"
  5027 proof -
  5030 proof -
  5028   interpret comp_fun_commute insort by (fact comp_fun_commute_insort)
  5031   interpret comp_fun_commute insort by (fact comp_fun_commute_insort)
  5029   show "folding insort" by default (fact comp_fun_commute)
  5032   show "folding insort" by default (fact comp_fun_commute)
  5030   show "folding.F insort [] = sorted_list_of_set" by (simp only: sorted_list_of_set_def)
  5033   show "folding.F insort [] = sorted_list_of_set" by (simp only: sorted_list_of_set_def)
  5031 qed
  5034 qed
  5032 
  5035 
  5033 context linorder
       
  5034 begin
       
  5035 
       
  5036 lemma sorted_list_of_set_empty:
  5036 lemma sorted_list_of_set_empty:
  5037   "sorted_list_of_set {} = []"
  5037   "sorted_list_of_set {} = []"
  5038   by (fact sorted_list_of_set.empty)
  5038   by (fact sorted_list_of_set.empty)
  5039 
  5039 
  5040 lemma sorted_list_of_set_insert [simp]:
  5040 lemma sorted_list_of_set_insert [simp]:
  5041   assumes "finite A"
  5041   "finite A \<Longrightarrow> sorted_list_of_set (insert x A) = insort x (sorted_list_of_set (A - {x}))"
  5042   shows "sorted_list_of_set (insert x A) = insort x (sorted_list_of_set (A - {x}))"
  5042   by (fact sorted_list_of_set.insert_remove)
  5043   using assms by (fact sorted_list_of_set.insert_remove)
       
  5044 
  5043 
  5045 lemma sorted_list_of_set_eq_Nil_iff [simp]:
  5044 lemma sorted_list_of_set_eq_Nil_iff [simp]:
  5046   "finite A \<Longrightarrow> sorted_list_of_set A = [] \<longleftrightarrow> A = {}"
  5045   "finite A \<Longrightarrow> sorted_list_of_set A = [] \<longleftrightarrow> A = {}"
  5047   using assms by (auto simp: sorted_list_of_set.remove)
  5046   by (auto simp: sorted_list_of_set.remove)
  5048 
  5047 
  5049 lemma sorted_list_of_set [simp]:
  5048 lemma sorted_list_of_set [simp]:
  5050   "finite A \<Longrightarrow> set (sorted_list_of_set A) = A \<and> sorted (sorted_list_of_set A) 
  5049   "finite A \<Longrightarrow> set (sorted_list_of_set A) = A \<and> sorted (sorted_list_of_set A) 
  5051     \<and> distinct (sorted_list_of_set A)"
  5050     \<and> distinct (sorted_list_of_set A)"
  5052   by (induct A rule: finite_induct) (simp_all add: set_insort sorted_insort distinct_insort)
  5051   by (induct A rule: finite_induct) (simp_all add: set_insort sorted_insort distinct_insort)