src/HOL/Library/FinFun.thy
changeset 63276 96bcd90415cb
parent 62390 842917225d56
child 63283 a59801b7f125
equal deleted inserted replaced
63275:ce63815d48dd 63276:96bcd90415cb
   187   hence "{b. f (a, b) \<noteq> c} \<subseteq> snd ` {ab. f ab \<noteq> c}" by auto
   187   hence "{b. f (a, b) \<noteq> c} \<subseteq> snd ` {ab. f ab \<noteq> c}" by auto
   188   hence "finite {b. f (a, b) \<noteq> c}" by(rule finite_subset)(rule finite_imageI[OF c])
   188   hence "finite {b. f (a, b) \<noteq> c}" by(rule finite_subset)(rule finite_imageI[OF c])
   189   thus "curry f a \<in> finfun" unfolding finfun_def by auto
   189   thus "curry f a \<in> finfun" unfolding finfun_def by auto
   190 qed
   190 qed
   191 
   191 
   192 bundle finfun =
   192 bundle finfun
   193   fst_finfun[simp] snd_finfun[simp] Abs_finfun_inverse[simp] 
   193 begin
   194   finfun_apply_inverse[simp] Abs_finfun_inject[simp] finfun_apply_inject[simp]
   194 
   195   Diag_finfun[simp] finfun_curry[simp]
   195 lemmas [simp] =
   196   const_finfun[iff] fun_upd_finfun[iff] finfun_apply[iff] map_of_finfun[iff]
   196   fst_finfun snd_finfun Abs_finfun_inverse
   197   finfun_left_compose[intro] fst_finfun[intro] snd_finfun[intro]
   197   finfun_apply_inverse Abs_finfun_inject finfun_apply_inject
       
   198   Diag_finfun finfun_curry
       
   199 lemmas [iff] =
       
   200   const_finfun fun_upd_finfun finfun_apply map_of_finfun
       
   201 lemmas [intro] =
       
   202   finfun_left_compose fst_finfun snd_finfun
       
   203 
       
   204 end
   198 
   205 
   199 lemma Abs_finfun_inject_finite:
   206 lemma Abs_finfun_inject_finite:
   200   fixes x y :: "'a \<Rightarrow> 'b"
   207   fixes x y :: "'a \<Rightarrow> 'b"
   201   assumes fin: "finite (UNIV :: 'a set)"
   208   assumes fin: "finite (UNIV :: 'a set)"
   202   shows "Abs_finfun x = Abs_finfun y \<longleftrightarrow> x = y"
   209   shows "Abs_finfun x = Abs_finfun y \<longleftrightarrow> x = y"
   728 locale finfun_rec_wf = finfun_rec_wf_aux + 
   735 locale finfun_rec_wf = finfun_rec_wf_aux + 
   729   assumes const_update_all:
   736   assumes const_update_all:
   730   "finite (UNIV :: 'a set) \<Longrightarrow> Finite_Set.fold (\<lambda>a. upd a b') (cnst b) (UNIV :: 'a set) = cnst b'"
   737   "finite (UNIV :: 'a set) \<Longrightarrow> Finite_Set.fold (\<lambda>a. upd a b') (cnst b) (UNIV :: 'a set) = cnst b'"
   731 begin
   738 begin
   732 
   739 
   733 lemma finfun_rec_const [simp]: includes finfun shows
   740 lemma finfun_rec_const [simp]: "finfun_rec cnst upd (K$ c) = cnst c"
   734   "finfun_rec cnst upd (K$ c) = cnst c"
   741   including finfun
   735 proof(cases "finite (UNIV :: 'a set)")
   742 proof(cases "finite (UNIV :: 'a set)")
   736   case False
   743   case False
   737   hence "finfun_default ((K$ c) :: 'a \<Rightarrow>f 'b) = c" by(simp add: finfun_default_const)
   744   hence "finfun_default ((K$ c) :: 'a \<Rightarrow>f 'b) = c" by(simp add: finfun_default_const)
   738   moreover have "(THE g :: 'a \<rightharpoonup> 'b. (K$ c) = Abs_finfun (map_default c g) \<and> finite (dom g) \<and> c \<notin> ran g) = empty"
   745   moreover have "(THE g :: 'a \<rightharpoonup> 'b. (K$ c) = Abs_finfun (map_default c g) \<and> finite (dom g) \<and> c \<notin> ran g) = empty"
   739   proof (rule the_equality)
   746   proof (rule the_equality)
   978 lemma finfun_comp2_const [code, simp]: "finfun_comp2 (K$ c) f = (K$ c)"
   985 lemma finfun_comp2_const [code, simp]: "finfun_comp2 (K$ c) f = (K$ c)"
   979   including finfun
   986   including finfun
   980 by(simp add: finfun_comp2_def finfun_const_def comp_def)
   987 by(simp add: finfun_comp2_def finfun_const_def comp_def)
   981 
   988 
   982 lemma finfun_comp2_update:
   989 lemma finfun_comp2_update:
   983   includes finfun
       
   984   assumes inj: "inj f"
   990   assumes inj: "inj f"
   985   shows "finfun_comp2 (g(b $:= c)) f = (if b \<in> range f then (finfun_comp2 g f)(inv f b $:= c) else finfun_comp2 g f)"
   991   shows "finfun_comp2 (g(b $:= c)) f = (if b \<in> range f then (finfun_comp2 g f)(inv f b $:= c) else finfun_comp2 g f)"
       
   992   including finfun
   986 proof(cases "b \<in> range f")
   993 proof(cases "b \<in> range f")
   987   case True
   994   case True
   988   from inj have "\<And>x. (op $ g)(f x := c) \<circ> f = (op $ g \<circ> f)(x := c)" by(auto intro!: ext dest: injD)
   995   from inj have "\<And>x. (op $ g)(f x := c) \<circ> f = (op $ g \<circ> f)(x := c)" by(auto intro!: ext dest: injD)
   989   with inj True show ?thesis by(auto simp add: finfun_comp2_def finfun_update_def finfun_right_compose)
   996   with inj True show ?thesis by(auto simp add: finfun_comp2_def finfun_update_def finfun_right_compose)
   990 next
   997 next