tuned Map, renamed lex stuff in List.
authornipkow
Mon Apr 11 12:14:23 2005 +0200 (2005-04-11)
changeset 156933a67e61c6e96
parent 15692 666ea7e62384
child 15694 3c49dbece0a8
tuned Map, renamed lex stuff in List.
src/HOL/List.ML
src/HOL/List.thy
src/HOL/Map.thy
     1.1 --- a/src/HOL/List.ML	Sun Apr 10 17:20:03 2005 +0200
     1.2 +++ b/src/HOL/List.ML	Mon Apr 11 12:14:23 2005 +0200
     1.3 @@ -90,8 +90,8 @@
     1.4  val length_zip = thm "length_zip";
     1.5  val lex_conv = thm "lex_conv";
     1.6  val lex_def = thm "lex_def";
     1.7 -val lexico_conv = thm "lexico_conv";
     1.8 -val lexico_def = thm "lexico_def";
     1.9 +val lenlex_conv = thm "lenlex_conv";
    1.10 +val lenlex_def = thm "lenlex_def";
    1.11  val lexn_conv = thm "lexn_conv";
    1.12  val lexn_length = thm "lexn_length";
    1.13  val list_all2_Cons = thm "list_all2_Cons";
    1.14 @@ -222,7 +222,7 @@
    1.15  val upt_conv_Nil = thm "upt_conv_Nil";
    1.16  val upt_rec = thm "upt_rec";
    1.17  val wf_lex = thm "wf_lex";
    1.18 -val wf_lexico = thm "wf_lexico";
    1.19 +val wf_lenlex = thm "wf_lenlex";
    1.20  val wf_lexn = thm "wf_lexn";
    1.21  val zip_Cons_Cons = thm "zip_Cons_Cons";
    1.22  val zip_Nil = thm "zip_Nil";
     2.1 --- a/src/HOL/List.thy	Sun Apr 10 17:20:03 2005 +0200
     2.2 +++ b/src/HOL/List.thy	Mon Apr 11 12:14:23 2005 +0200
     2.3 @@ -1909,8 +1909,8 @@
     2.4      "lex r == \<Union>n. lexn r n"
     2.5          --{*Holds only between lists of the same length*}
     2.6  
     2.7 -  lexico :: "('a \<times> 'a) set => ('a list \<times> 'a list) set"
     2.8 -    "lexico r == inv_image (less_than <*lex*> lex r) (%xs. (length xs, xs))"
     2.9 +  lenlex :: "('a \<times> 'a) set => ('a list \<times> 'a list) set"
    2.10 +    "lenlex r == inv_image (less_than <*lex*> lex r) (%xs. (length xs, xs))"
    2.11          --{*Compares lists by their length and then lexicographically*}
    2.12  
    2.13  
    2.14 @@ -1952,13 +1952,13 @@
    2.15      (\<exists>xys x y xs' ys'. xs = xys @ x # xs' \<and> ys = xys @ y # ys' \<and> (x, y):r)}"
    2.16  by (force simp add: lex_def lexn_conv)
    2.17  
    2.18 -lemma wf_lexico [intro!]: "wf r ==> wf (lexico r)"
    2.19 -by (unfold lexico_def) blast
    2.20 -
    2.21 -lemma lexico_conv:
    2.22 -    "lexico r = {(xs,ys). length xs < length ys |
    2.23 +lemma wf_lenlex [intro!]: "wf r ==> wf (lenlex r)"
    2.24 +by (unfold lenlex_def) blast
    2.25 +
    2.26 +lemma lenlex_conv:
    2.27 +    "lenlex r = {(xs,ys). length xs < length ys |
    2.28                   length xs = length ys \<and> (xs, ys) : lex r}"
    2.29 -by (simp add: lexico_def diag_def lex_prod_def measure_def inv_image_def)
    2.30 +by (simp add: lenlex_def diag_def lex_prod_def measure_def inv_image_def)
    2.31  
    2.32  lemma Nil_notin_lex [iff]: "([], ys) \<notin> lex r"
    2.33  by (simp add: lex_conv)
     3.1 --- a/src/HOL/Map.thy	Sun Apr 10 17:20:03 2005 +0200
     3.2 +++ b/src/HOL/Map.thy	Mon Apr 11 12:14:23 2005 +0200
     3.3 @@ -18,7 +18,7 @@
     3.4  consts
     3.5  chg_map	:: "('b => 'b) => 'a => ('a ~=> 'b) => ('a ~=> 'b)"
     3.6  map_add :: "('a ~=> 'b) => ('a ~=> 'b) => ('a ~=> 'b)" (infixl "++" 100)
     3.7 -restrict_map :: "('a ~=> 'b) => 'a set => ('a ~=> 'b)" (infixl "|^"  110)
     3.8 +restrict_map :: "('a ~=> 'b) => 'a set => ('a ~=> 'b)" (infixl "|`"  110)
     3.9  dom	:: "('a ~=> 'b) => 'a set"
    3.10  ran	:: "('a ~=> 'b) => 'b set"
    3.11  map_of	:: "('a * 'b)list => 'a ~=> 'b"
    3.12 @@ -55,7 +55,6 @@
    3.13    "_maplet"  :: "['a, 'a] => maplet"             ("_ /\<mapsto>/ _")
    3.14    "_maplets" :: "['a, 'a] => maplet"             ("_ /[\<mapsto>]/ _")
    3.15  
    3.16 -  restrict_map :: "('a ~=> 'b) => 'a set => ('a ~=> 'b)" (infixl "\<upharpoonright>" 110) --"requires amssymb!"
    3.17    map_upd_s  :: "('a ~=> 'b) => 'a set => 'b => ('a ~=> 'b)"
    3.18  				    		 ("_/'(_/{\<mapsto>}/_')" [900,0,0]900)
    3.19    map_subst :: "('a ~=> 'b) => 'b => 'b => 
    3.20 @@ -63,6 +62,9 @@
    3.21   "@chg_map" :: "('a ~=> 'b) => 'a => ('b => 'b) => ('a ~=> 'b)"
    3.22  					  ("_/'(_/\<mapsto>\<lambda>_. _')"  [900,0,0,0] 900)
    3.23  
    3.24 +syntax (latex output)
    3.25 +  restrict_map :: "('a ~=> 'b) => 'a set => ('a ~=> 'b)" ("_\<restriction>\<^bsub>_\<^esub>" [111,110] 110) --"requires amssymb!"
    3.26 +
    3.27  translations
    3.28    "empty"    => "_K None"
    3.29    "empty"    <= "%x. None"
    3.30 @@ -80,7 +82,7 @@
    3.31  chg_map_def:  "chg_map f a m == case m a of None => m | Some b => m(a|->f b)"
    3.32  
    3.33  map_add_def:   "m1++m2 == %x. case m2 x of None => m1 x | Some y => Some y"
    3.34 -restrict_map_def: "m|^A == %x. if x : A then m x else None"
    3.35 +restrict_map_def: "m|`A == %x. if x : A then m x else None"
    3.36  
    3.37  map_upds_def: "m(xs [|->] ys) == m ++ map_of (rev(zip xs ys))"
    3.38  map_upd_s_def: "m(as{|->}b) == %x. if x : as then Some b else m x"
    3.39 @@ -324,44 +326,44 @@
    3.40  
    3.41  subsection {* @{term restrict_map} *}
    3.42  
    3.43 -lemma restrict_map_to_empty[simp]: "m|^{} = empty"
    3.44 +lemma restrict_map_to_empty[simp]: "m|`{} = empty"
    3.45  by(simp add: restrict_map_def)
    3.46  
    3.47 -lemma restrict_map_empty[simp]: "empty|^D = empty"
    3.48 +lemma restrict_map_empty[simp]: "empty|`D = empty"
    3.49  by(simp add: restrict_map_def)
    3.50  
    3.51 -lemma restrict_in [simp]: "x \<in> A \<Longrightarrow> (m|^A) x = m x"
    3.52 +lemma restrict_in [simp]: "x \<in> A \<Longrightarrow> (m|`A) x = m x"
    3.53  by (auto simp: restrict_map_def)
    3.54  
    3.55 -lemma restrict_out [simp]: "x \<notin> A \<Longrightarrow> (m|^A) x = None"
    3.56 +lemma restrict_out [simp]: "x \<notin> A \<Longrightarrow> (m|`A) x = None"
    3.57  by (auto simp: restrict_map_def)
    3.58  
    3.59 -lemma ran_restrictD: "y \<in> ran (m|^A) \<Longrightarrow> \<exists>x\<in>A. m x = Some y"
    3.60 +lemma ran_restrictD: "y \<in> ran (m|`A) \<Longrightarrow> \<exists>x\<in>A. m x = Some y"
    3.61  by (auto simp: restrict_map_def ran_def split: split_if_asm)
    3.62  
    3.63 -lemma dom_restrict [simp]: "dom (m|^A) = dom m \<inter> A"
    3.64 +lemma dom_restrict [simp]: "dom (m|`A) = dom m \<inter> A"
    3.65  by (auto simp: restrict_map_def dom_def split: split_if_asm)
    3.66  
    3.67 -lemma restrict_upd_same [simp]: "m(x\<mapsto>y)|^(-{x}) = m|^(-{x})"
    3.68 +lemma restrict_upd_same [simp]: "m(x\<mapsto>y)|`(-{x}) = m|`(-{x})"
    3.69  by (rule ext, auto simp: restrict_map_def)
    3.70  
    3.71 -lemma restrict_restrict [simp]: "m|^A|^B = m|^(A\<inter>B)"
    3.72 +lemma restrict_restrict [simp]: "m|`A|`B = m|`(A\<inter>B)"
    3.73  by (rule ext, auto simp: restrict_map_def)
    3.74  
    3.75  lemma restrict_fun_upd[simp]:
    3.76 - "m(x := y)|^D = (if x \<in> D then (m|^(D-{x}))(x := y) else m|^D)"
    3.77 + "m(x := y)|`D = (if x \<in> D then (m|`(D-{x}))(x := y) else m|`D)"
    3.78  by(simp add: restrict_map_def expand_fun_eq)
    3.79  
    3.80  lemma fun_upd_None_restrict[simp]:
    3.81 -  "(m|^D)(x := None) = (if x:D then m|^(D - {x}) else m|^D)"
    3.82 +  "(m|`D)(x := None) = (if x:D then m|`(D - {x}) else m|`D)"
    3.83  by(simp add: restrict_map_def expand_fun_eq)
    3.84  
    3.85  lemma fun_upd_restrict:
    3.86 - "(m|^D)(x := y) = (m|^(D-{x}))(x := y)"
    3.87 + "(m|`D)(x := y) = (m|`(D-{x}))(x := y)"
    3.88  by(simp add: restrict_map_def expand_fun_eq)
    3.89  
    3.90  lemma fun_upd_restrict_conv[simp]:
    3.91 - "x \<in> D \<Longrightarrow> (m|^D)(x := y) = (m|^(D-{x}))(x := y)"
    3.92 + "x \<in> D \<Longrightarrow> (m|`D)(x := y) = (m|`(D-{x}))(x := y)"
    3.93  by(simp add: restrict_map_def expand_fun_eq)
    3.94  
    3.95  
    3.96 @@ -432,7 +434,7 @@
    3.97  
    3.98  lemma restrict_map_upds[simp]: "!!m ys.
    3.99   \<lbrakk> length xs = length ys; set xs \<subseteq> D \<rbrakk>
   3.100 - \<Longrightarrow> m(xs [\<mapsto>] ys)|^D = (m|^(D - set xs))(xs [\<mapsto>] ys)"
   3.101 + \<Longrightarrow> m(xs [\<mapsto>] ys)|`D = (m|`(D - set xs))(xs [\<mapsto>] ys)"
   3.102  apply (induct xs, simp)
   3.103  apply (case_tac ys, simp)
   3.104  apply(simp add:Diff_insert[symmetric] insert_absorb)