src/HOL/Library/AList.thy
changeset 62390 842917225d56
parent 61585 a9599d3d7610
child 63462 c1fe30f2bc32
equal deleted inserted replaced
62380:29800666e526 62390:842917225d56
    56 
    56 
    57 lemma update_eqD: "update k v al = update k v' al' \<Longrightarrow> v = v'"
    57 lemma update_eqD: "update k v al = update k v' al' \<Longrightarrow> v = v'"
    58 proof (induct al arbitrary: al')
    58 proof (induct al arbitrary: al')
    59   case Nil
    59   case Nil
    60   then show ?case
    60   then show ?case
    61     by (cases al') (auto split: split_if_asm)
    61     by (cases al') (auto split: if_split_asm)
    62 next
    62 next
    63   case Cons
    63   case Cons
    64   then show ?case
    64   then show ?case
    65     by (cases al') (auto split: split_if_asm)
    65     by (cases al') (auto split: if_split_asm)
    66 qed
    66 qed
    67 
    67 
    68 lemma update_last [simp]: "update k v (update k v' al) = update k v al"
    68 lemma update_last [simp]: "update k v (update k v' al) = update k v al"
    69   by (induct al) auto
    69   by (induct al) auto
    70 
    70 
   291 lemma map_of_delete_aux:
   291 lemma map_of_delete_aux:
   292   "distinct (map fst xs) \<Longrightarrow> map_of (delete_aux k xs) k' = ((map_of xs)(k := None)) k'"
   292   "distinct (map fst xs) \<Longrightarrow> map_of (delete_aux k xs) k' = ((map_of xs)(k := None)) k'"
   293 by(simp add: map_of_delete_aux')
   293 by(simp add: map_of_delete_aux')
   294 
   294 
   295 lemma delete_aux_eq_Nil_conv: "delete_aux k ts = [] \<longleftrightarrow> ts = [] \<or> (\<exists>v. ts = [(k, v)])"
   295 lemma delete_aux_eq_Nil_conv: "delete_aux k ts = [] \<longleftrightarrow> ts = [] \<or> (\<exists>v. ts = [(k, v)])"
   296 by(cases ts)(auto split: split_if_asm)
   296 by(cases ts)(auto split: if_split_asm)
   297 
   297 
   298 
   298 
   299 subsection \<open>\<open>restrict\<close>\<close>
   299 subsection \<open>\<open>restrict\<close>\<close>
   300 
   300 
   301 qualified definition restrict :: "'key set \<Rightarrow> ('key \<times> 'val) list \<Rightarrow> ('key \<times> 'val) list"
   301 qualified definition restrict :: "'key set \<Rightarrow> ('key \<times> 'val) list \<Rightarrow> ('key \<times> 'val) list"
   572   by (relation "measure (length \<circ> fst)") (simp_all add: less_Suc_eq_le length_delete_le)
   572   by (relation "measure (length \<circ> fst)") (simp_all add: less_Suc_eq_le length_delete_le)
   573 
   573 
   574 lemma compose_first_None [simp]:
   574 lemma compose_first_None [simp]:
   575   assumes "map_of xs k = None"
   575   assumes "map_of xs k = None"
   576   shows "map_of (compose xs ys) k = None"
   576   shows "map_of (compose xs ys) k = None"
   577   using assms by (induct xs ys rule: compose.induct) (auto split: option.splits split_if_asm)
   577   using assms by (induct xs ys rule: compose.induct) (auto split: option.splits if_split_asm)
   578 
   578 
   579 lemma compose_conv: "map_of (compose xs ys) k = (map_of ys \<circ>\<^sub>m map_of xs) k"
   579 lemma compose_conv: "map_of (compose xs ys) k = (map_of ys \<circ>\<^sub>m map_of xs) k"
   580 proof (induct xs ys rule: compose.induct)
   580 proof (induct xs ys rule: compose.induct)
   581   case 1
   581   case 1
   582   then show ?case by simp
   582   then show ?case by simp