src/HOL/Library/Executable_Set.thy
changeset 26312 e9a65675e5e8
parent 25885 6fbc3f54f819
child 26816 e82229ee8f43
equal deleted inserted replaced
26311:81a0fc28b0de 26312:e9a65675e5e8
    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