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