src/HOL/Library/ExecutableSet.thy
changeset 23394 474ff28210c0
parent 22921 475ff421a6a3
equal deleted inserted replaced
23393:31781b2de73d 23394:474ff28210c0
    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