equal
deleted
inserted
replaced
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 |