97 "unionl [] ys = ys" |
97 "unionl [] ys = ys" |
98 | "unionl xs ys = foldr insertl xs ys" |
98 | "unionl xs ys = foldr insertl xs ys" |
99 by pat_completeness auto |
99 by pat_completeness auto |
100 termination by lexicographic_order |
100 termination by lexicographic_order |
101 |
101 |
102 lemmas unionl_def = unionl.simps(2) |
102 lemmas unionl_eq = unionl.simps(2) |
103 |
103 |
104 function intersect :: "'a list \<Rightarrow> 'a list \<Rightarrow> 'a list" |
104 function intersect :: "'a list \<Rightarrow> 'a list \<Rightarrow> 'a list" |
105 where |
105 where |
106 "intersect [] ys = []" |
106 "intersect [] ys = []" |
107 | "intersect xs [] = []" |
107 | "intersect xs [] = []" |
108 | "intersect xs ys = filter (member xs) ys" |
108 | "intersect xs ys = filter (member xs) ys" |
109 by pat_completeness auto |
109 by pat_completeness auto |
110 termination by lexicographic_order |
110 termination by lexicographic_order |
111 |
111 |
112 lemmas intersect_def = intersect.simps(3) |
112 lemmas intersect_eq = intersect.simps(3) |
113 |
113 |
114 function subtract :: "'a list \<Rightarrow> 'a list \<Rightarrow> 'a list" |
114 function subtract :: "'a list \<Rightarrow> 'a list \<Rightarrow> 'a list" |
115 where |
115 where |
116 "subtract [] ys = ys" |
116 "subtract [] ys = ys" |
117 | "subtract xs [] = []" |
117 | "subtract xs [] = []" |
118 | "subtract xs ys = foldr remove1 xs ys" |
118 | "subtract xs ys = foldr remove1 xs ys" |
119 by pat_completeness auto |
119 by pat_completeness auto |
120 termination by lexicographic_order |
120 termination by lexicographic_order |
121 |
121 |
122 lemmas subtract_def = subtract.simps(3) |
122 lemmas subtract_eq = subtract.simps(3) |
123 |
123 |
124 function map_distinct :: "('a \<Rightarrow> 'b) \<Rightarrow> 'a list \<Rightarrow> 'b list" |
124 function map_distinct :: "('a \<Rightarrow> 'b) \<Rightarrow> 'a list \<Rightarrow> 'b list" |
125 where |
125 where |
126 "map_distinct f [] = []" |
126 "map_distinct f [] = []" |
127 | "map_distinct f xs = foldr (insertl o f) xs []" |
127 | "map_distinct f xs = foldr (insertl o f) xs []" |
128 by pat_completeness auto |
128 by pat_completeness auto |
129 termination by lexicographic_order |
129 termination by lexicographic_order |
130 |
130 |
131 lemmas map_distinct_def = map_distinct.simps(2) |
131 lemmas map_distinct_eq = map_distinct.simps(2) |
132 |
132 |
133 function unions :: "'a list list \<Rightarrow> 'a list" |
133 function unions :: "'a list list \<Rightarrow> 'a list" |
134 where |
134 where |
135 "unions [] = []" |
135 "unions [] = []" |
136 | "unions xs = foldr unionl xs []" |
136 | "unions xs = foldr unionl xs []" |
137 by pat_completeness auto |
137 by pat_completeness auto |
138 termination by lexicographic_order |
138 termination by lexicographic_order |
139 |
139 |
140 lemmas unions_def = unions.simps(2) |
140 lemmas unions_eq = unions.simps(2) |
141 |
141 |
142 consts intersects :: "'a list list \<Rightarrow> 'a list" |
142 consts intersects :: "'a list list \<Rightarrow> 'a list" |
143 primrec |
143 primrec |
144 "intersects (x#xs) = foldr intersect xs x" |
144 "intersects (x#xs) = foldr intersect xs x" |
145 |
145 |
167 shows "set (remove1 x xs) = set xs - {x}" |
167 shows "set (remove1 x xs) = set xs - {x}" |
168 using distnct set_remove1_eq by auto |
168 using distnct set_remove1_eq by auto |
169 |
169 |
170 lemma iso_union: |
170 lemma iso_union: |
171 "set (unionl xs ys) = set xs \<union> set ys" |
171 "set (unionl xs ys) = set xs \<union> set ys" |
172 unfolding unionl_def |
172 unfolding unionl_eq |
173 by (induct xs arbitrary: ys) (simp_all add: iso_insert) |
173 by (induct xs arbitrary: ys) (simp_all add: iso_insert) |
174 |
174 |
175 lemma iso_intersect: |
175 lemma iso_intersect: |
176 "set (intersect xs ys) = set xs \<inter> set ys" |
176 "set (intersect xs ys) = set xs \<inter> set ys" |
177 unfolding intersect_def Int_def by (simp add: Int_def iso_member) auto |
177 unfolding intersect_eq Int_def by (simp add: Int_def iso_member) auto |
178 |
178 |
179 definition |
179 definition |
180 subtract' :: "'a list \<Rightarrow> 'a list \<Rightarrow> 'a list" where |
180 subtract' :: "'a list \<Rightarrow> 'a list \<Rightarrow> 'a list" where |
181 "subtract' = flip subtract" |
181 "subtract' = flip subtract" |
182 |
182 |
183 lemma iso_subtract: |
183 lemma iso_subtract: |
184 fixes ys |
184 fixes ys |
185 assumes distnct: "distinct ys" |
185 assumes distnct: "distinct ys" |
186 shows "set (subtract' ys xs) = set ys - set xs" |
186 shows "set (subtract' ys xs) = set ys - set xs" |
187 and "distinct (subtract' ys xs)" |
187 and "distinct (subtract' ys xs)" |
188 unfolding subtract'_def flip_def subtract_def |
188 unfolding subtract'_def flip_def subtract_eq |
189 using distnct by (induct xs arbitrary: ys) auto |
189 using distnct by (induct xs arbitrary: ys) auto |
190 |
190 |
191 lemma iso_map_distinct: |
191 lemma iso_map_distinct: |
192 "set (map_distinct f xs) = image f (set xs)" |
192 "set (map_distinct f xs) = image f (set xs)" |
193 unfolding map_distinct_def by (induct xs) (simp_all add: iso_insert) |
193 unfolding map_distinct_eq by (induct xs) (simp_all add: iso_insert) |
194 |
194 |
195 lemma iso_unions: |
195 lemma iso_unions: |
196 "set (unions xss) = \<Union> set (map set xss)" |
196 "set (unions xss) = \<Union> set (map set xss)" |
197 unfolding unions_def |
197 unfolding unions_eq |
198 proof (induct xss) |
198 proof (induct xss) |
199 case Nil show ?case by simp |
199 case Nil show ?case by simp |
200 next |
200 next |
201 case (Cons xs xss) thus ?case by (induct xs) (simp_all add: iso_insert) |
201 case (Cons xs xss) thus ?case by (induct xs) (simp_all add: iso_insert) |
202 qed |
202 qed |