src/HOL/Random.thy
changeset 31205 98370b26c2ce
parent 31203 5c8fb4fd67e0
child 31261 900ebbc35e30
     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)