equal
deleted
inserted
replaced
54 |
54 |
55 definition |
55 definition |
56 insertl :: "'a \<Rightarrow> 'a list \<Rightarrow> 'a list" where |
56 insertl :: "'a \<Rightarrow> 'a list \<Rightarrow> 'a list" where |
57 "insertl x xs = (if member xs x then xs else x#xs)" |
57 "insertl x xs = (if member xs x then xs else x#xs)" |
58 |
58 |
59 lemma |
59 lemma [code target: List]: "member [] y \<longleftrightarrow> False" |
60 [code target: List]: "member [] y \<longleftrightarrow> False" |
|
61 and [code target: List]: "member (x#xs) y \<longleftrightarrow> y = x \<or> member xs y" |
60 and [code target: List]: "member (x#xs) y \<longleftrightarrow> y = x \<or> member xs y" |
62 unfolding member_def by (induct xs) simp_all |
61 unfolding member_def by (induct xs) simp_all |
63 |
62 |
64 fun |
63 fun |
65 drop_first :: "('a \<Rightarrow> bool) \<Rightarrow> 'a list \<Rightarrow> 'a list" where |
64 drop_first :: "('a \<Rightarrow> bool) \<Rightarrow> 'a list \<Rightarrow> 'a list" where |
66 "drop_first f [] = []" |
65 "drop_first f [] = []" |
67 | "drop_first f (x#xs) = (if f x then xs else x # drop_first f xs)" |
66 | "drop_first f (x#xs) = (if f x then xs else x # drop_first f xs)" |
199 |
198 |
200 lemma iso_subtract: |
199 lemma iso_subtract: |
201 fixes ys |
200 fixes ys |
202 assumes distnct: "distinct ys" |
201 assumes distnct: "distinct ys" |
203 shows "set (subtract' ys xs) = set ys - set xs" |
202 shows "set (subtract' ys xs) = set ys - set xs" |
204 and "distinct (subtract' ys xs)" |
203 and "distinct (subtract' ys xs)" |
205 unfolding subtract'_def flip_def subtract_def |
204 unfolding subtract'_def flip_def subtract_def |
206 using distnct by (induct xs arbitrary: ys) auto |
205 using distnct by (induct xs arbitrary: ys) auto |
207 |
206 |
208 lemma iso_map_distinct: |
207 lemma iso_map_distinct: |
209 "set (map_distinct f xs) = image f (set xs)" |
208 "set (map_distinct f xs) = image f (set xs)" |
210 unfolding map_distinct_def by (induct xs) (simp_all add: iso_insert) |
209 unfolding map_distinct_def by (induct xs) (simp_all add: iso_insert) |
211 |
210 |
212 lemma iso_unions: |
211 lemma iso_unions: |
213 "set (unions xss) = \<Union> set (map set xss)" |
212 "set (unions xss) = \<Union> set (map set xss)" |
214 unfolding unions_def proof (induct xss) |
213 unfolding unions_def |
|
214 proof (induct xss) |
215 case Nil show ?case by simp |
215 case Nil show ?case by simp |
216 next |
216 next |
217 case (Cons xs xss) thus ?case by (induct xs) (simp_all add: iso_insert) |
217 case (Cons xs xss) thus ?case by (induct xs) (simp_all add: iso_insert) |
218 qed |
218 qed |
219 |
219 |