1.1 --- a/src/HOL/Random.thy Tue May 19 13:57:51 2009 +0200
1.2 +++ b/src/HOL/Random.thy Tue May 19 16:54:55 2009 +0200
1.3 @@ -3,7 +3,7 @@
1.4 header {* A HOL random engine *}
1.5
1.6 theory Random
1.7 -imports Code_Index List
1.8 +imports Code_Numeral List
1.9 begin
1.10
1.11 notation fcomp (infixl "o>" 60)
1.12 @@ -12,21 +12,21 @@
1.13
1.14 subsection {* Auxiliary functions *}
1.15
1.16 -definition inc_shift :: "index \<Rightarrow> index \<Rightarrow> index" where
1.17 +definition inc_shift :: "code_numeral \<Rightarrow> code_numeral \<Rightarrow> code_numeral" where
1.18 "inc_shift v k = (if v = k then 1 else k + 1)"
1.19
1.20 -definition minus_shift :: "index \<Rightarrow> index \<Rightarrow> index \<Rightarrow> index" where
1.21 +definition minus_shift :: "code_numeral \<Rightarrow> code_numeral \<Rightarrow> code_numeral \<Rightarrow> code_numeral" where
1.22 "minus_shift r k l = (if k < l then r + k - l else k - l)"
1.23
1.24 -fun log :: "index \<Rightarrow> index \<Rightarrow> index" where
1.25 +fun log :: "code_numeral \<Rightarrow> code_numeral \<Rightarrow> code_numeral" where
1.26 "log b i = (if b \<le> 1 \<or> i < b then 1 else 1 + log b (i div b))"
1.27
1.28
1.29 subsection {* Random seeds *}
1.30
1.31 -types seed = "index \<times> index"
1.32 +types seed = "code_numeral \<times> code_numeral"
1.33
1.34 -primrec "next" :: "seed \<Rightarrow> index \<times> seed" where
1.35 +primrec "next" :: "seed \<Rightarrow> code_numeral \<times> seed" where
1.36 "next (v, w) = (let
1.37 k = v div 53668;
1.38 v' = minus_shift 2147483563 (40014 * (v mod 53668)) (k * 12211);
1.39 @@ -55,10 +55,10 @@
1.40
1.41 subsection {* Base selectors *}
1.42
1.43 -fun iterate :: "index \<Rightarrow> ('b \<Rightarrow> 'a \<Rightarrow> 'b \<times> 'a) \<Rightarrow> 'b \<Rightarrow> 'a \<Rightarrow> 'b \<times> 'a" where
1.44 +fun iterate :: "code_numeral \<Rightarrow> ('b \<Rightarrow> 'a \<Rightarrow> 'b \<times> 'a) \<Rightarrow> 'b \<Rightarrow> 'a \<Rightarrow> 'b \<times> 'a" where
1.45 "iterate k f x = (if k = 0 then Pair x else f x o\<rightarrow> iterate (k - 1) f)"
1.46
1.47 -definition range :: "index \<Rightarrow> seed \<Rightarrow> index \<times> seed" where
1.48 +definition range :: "code_numeral \<Rightarrow> seed \<Rightarrow> code_numeral \<times> seed" where
1.49 "range k = iterate (log 2147483561 k)
1.50 (\<lambda>l. next o\<rightarrow> (\<lambda>v. Pair (v + l * 2147483561))) 1
1.51 o\<rightarrow> (\<lambda>v. Pair (v mod k))"
1.52 @@ -68,23 +68,23 @@
1.53 by (simp add: range_def scomp_apply split_def del: log.simps iterate.simps)
1.54
1.55 definition select :: "'a list \<Rightarrow> seed \<Rightarrow> 'a \<times> seed" where
1.56 - "select xs = range (Code_Index.of_nat (length xs))
1.57 - o\<rightarrow> (\<lambda>k. Pair (nth xs (Code_Index.nat_of k)))"
1.58 + "select xs = range (Code_Numeral.of_nat (length xs))
1.59 + o\<rightarrow> (\<lambda>k. Pair (nth xs (Code_Numeral.nat_of k)))"
1.60
1.61 lemma select:
1.62 assumes "xs \<noteq> []"
1.63 shows "fst (select xs s) \<in> set xs"
1.64 proof -
1.65 - from assms have "Code_Index.of_nat (length xs) > 0" by simp
1.66 + from assms have "Code_Numeral.of_nat (length xs) > 0" by simp
1.67 with range have
1.68 - "fst (range (Code_Index.of_nat (length xs)) s) < Code_Index.of_nat (length xs)" by best
1.69 + "fst (range (Code_Numeral.of_nat (length xs)) s) < Code_Numeral.of_nat (length xs)" by best
1.70 then have
1.71 - "Code_Index.nat_of (fst (range (Code_Index.of_nat (length xs)) s)) < length xs" by simp
1.72 + "Code_Numeral.nat_of (fst (range (Code_Numeral.of_nat (length xs)) s)) < length xs" by simp
1.73 then show ?thesis
1.74 by (simp add: scomp_apply split_beta select_def)
1.75 qed
1.76
1.77 -primrec pick :: "(index \<times> 'a) list \<Rightarrow> index \<Rightarrow> 'a" where
1.78 +primrec pick :: "(code_numeral \<times> 'a) list \<Rightarrow> code_numeral \<Rightarrow> 'a" where
1.79 "pick (x # xs) i = (if i < fst x then snd x else pick xs (i - fst x))"
1.80
1.81 lemma pick_member:
1.82 @@ -96,14 +96,14 @@
1.83 by (induct xs) (auto simp add: expand_fun_eq)
1.84
1.85 lemma pick_same:
1.86 - "l < length xs \<Longrightarrow> Random.pick (map (Pair 1) xs) (Code_Index.of_nat l) = nth xs l"
1.87 + "l < length xs \<Longrightarrow> Random.pick (map (Pair 1) xs) (Code_Numeral.of_nat l) = nth xs l"
1.88 proof (induct xs arbitrary: l)
1.89 case Nil then show ?case by simp
1.90 next
1.91 case (Cons x xs) then show ?case by (cases l) simp_all
1.92 qed
1.93
1.94 -definition select_weight :: "(index \<times> 'a) list \<Rightarrow> seed \<Rightarrow> 'a \<times> seed" where
1.95 +definition select_weight :: "(code_numeral \<times> 'a) list \<Rightarrow> seed \<Rightarrow> 'a \<times> seed" where
1.96 "select_weight xs = range (listsum (map fst xs))
1.97 o\<rightarrow> (\<lambda>k. Pair (pick xs k))"
1.98
1.99 @@ -130,16 +130,16 @@
1.100 assumes "xs \<noteq> []"
1.101 shows "Random.select_weight (map (Pair 1) xs) = Random.select xs"
1.102 proof -
1.103 - have less: "\<And>s. fst (Random.range (Code_Index.of_nat (length xs)) s) < Code_Index.of_nat (length xs)"
1.104 + have less: "\<And>s. fst (Random.range (Code_Numeral.of_nat (length xs)) s) < Code_Numeral.of_nat (length xs)"
1.105 using assms by (intro range) simp
1.106 - moreover have "listsum (map fst (map (Pair 1) xs)) = Code_Index.of_nat (length xs)"
1.107 + moreover have "listsum (map fst (map (Pair 1) xs)) = Code_Numeral.of_nat (length xs)"
1.108 by (induct xs) simp_all
1.109 ultimately show ?thesis
1.110 by (auto simp add: select_weight_def select_def scomp_def split_def
1.111 expand_fun_eq pick_same [symmetric])
1.112 qed
1.113
1.114 -definition select_default :: "index \<Rightarrow> 'a \<Rightarrow> 'a \<Rightarrow> seed \<Rightarrow> 'a \<times> seed" where
1.115 +definition select_default :: "code_numeral \<Rightarrow> 'a \<Rightarrow> 'a \<Rightarrow> seed \<Rightarrow> 'a \<times> seed" where
1.116 [code del]: "select_default k x y = range k
1.117 o\<rightarrow> (\<lambda>l. Pair (if l + 1 < k then x else y))"
1.118
1.119 @@ -153,7 +153,7 @@
1.120 else range k o\<rightarrow> (\<lambda>l. Pair (if l + 1 < k then x else y)))"
1.121 proof
1.122 fix s
1.123 - have "snd (range (Code_Index.of_nat 0) s) = snd (range (Code_Index.of_nat 1) s)"
1.124 + have "snd (range (Code_Numeral.of_nat 0) s) = snd (range (Code_Numeral.of_nat 1) s)"
1.125 by (simp add: range_def scomp_Pair scomp_apply split_beta)
1.126 then show "select_default k x y s = (if k = 0
1.127 then range 1 o\<rightarrow> (\<lambda>_. Pair y)