src/HOL/Library/IArray.thy
changeset 61115 3a4400985780
parent 60500 903bb1495239
child 63649 e690d6f2185b
equal deleted inserted replaced
61114:dcfc28144858 61115:3a4400985780
    11 
    11 
    12 Note that arrays cannot be printed directly but only by turning them into
    12 Note that arrays cannot be printed directly but only by turning them into
    13 lists first. Arrays could be converted back into lists for printing if they
    13 lists first. Arrays could be converted back into lists for printing if they
    14 were wrapped up in an additional constructor.\<close>
    14 were wrapped up in an additional constructor.\<close>
    15 
    15 
       
    16 context
       
    17 begin
       
    18 
    16 datatype 'a iarray = IArray "'a list"
    19 datatype 'a iarray = IArray "'a list"
    17 
    20 
    18 primrec list_of :: "'a iarray \<Rightarrow> 'a list" where
    21 qualified primrec list_of :: "'a iarray \<Rightarrow> 'a list" where
    19 "list_of (IArray xs) = xs"
    22 "list_of (IArray xs) = xs"
    20 hide_const (open) list_of
       
    21 
    23 
    22 definition of_fun :: "(nat \<Rightarrow> 'a) \<Rightarrow> nat \<Rightarrow> 'a iarray" where
    24 qualified definition of_fun :: "(nat \<Rightarrow> 'a) \<Rightarrow> nat \<Rightarrow> 'a iarray" where
    23 [simp]: "of_fun f n = IArray (map f [0..<n])"
    25 [simp]: "of_fun f n = IArray (map f [0..<n])"
    24 hide_const (open) of_fun
       
    25 
    26 
    26 definition sub :: "'a iarray \<Rightarrow> nat \<Rightarrow> 'a" (infixl "!!" 100) where
    27 qualified definition sub :: "'a iarray \<Rightarrow> nat \<Rightarrow> 'a" (infixl "!!" 100) where
    27 [simp]: "as !! n = IArray.list_of as ! n"
    28 [simp]: "as !! n = IArray.list_of as ! n"
    28 hide_const (open) sub
       
    29 
    29 
    30 definition length :: "'a iarray \<Rightarrow> nat" where
    30 qualified definition length :: "'a iarray \<Rightarrow> nat" where
    31 [simp]: "length as = List.length (IArray.list_of as)"
    31 [simp]: "length as = List.length (IArray.list_of as)"
    32 hide_const (open) length
       
    33 
    32 
    34 fun all :: "('a \<Rightarrow> bool) \<Rightarrow> 'a iarray \<Rightarrow> bool" where
    33 qualified fun all :: "('a \<Rightarrow> bool) \<Rightarrow> 'a iarray \<Rightarrow> bool" where
    35 "all p (IArray as) = (ALL a : set as. p a)"
    34 "all p (IArray as) = (ALL a : set as. p a)"
    36 hide_const (open) all
       
    37 
    35 
    38 fun exists :: "('a \<Rightarrow> bool) \<Rightarrow> 'a iarray \<Rightarrow> bool" where
    36 qualified fun exists :: "('a \<Rightarrow> bool) \<Rightarrow> 'a iarray \<Rightarrow> bool" where
    39 "exists p (IArray as) = (EX a : set as. p a)"
    37 "exists p (IArray as) = (EX a : set as. p a)"
    40 hide_const (open) exists
       
    41 
    38 
    42 lemma list_of_code [code]:
    39 lemma list_of_code [code]:
    43 "IArray.list_of as = map (\<lambda>n. as !! n) [0 ..< IArray.length as]"
    40 "IArray.list_of as = map (\<lambda>n. as !! n) [0 ..< IArray.length as]"
    44 by (cases as) (simp add: map_nth)
    41 by (cases as) (simp add: map_nth)
       
    42 
       
    43 end
    45 
    44 
    46 
    45 
    47 subsection "Code Generation"
    46 subsection "Code Generation"
    48 
    47 
    49 code_reserved SML Vector
    48 code_reserved SML Vector
    84 
    83 
    85 lemma [code]:
    84 lemma [code]:
    86   "HOL.equal as bs \<longleftrightarrow> HOL.equal (IArray.list_of as) (IArray.list_of bs)"
    85   "HOL.equal as bs \<longleftrightarrow> HOL.equal (IArray.list_of as) (IArray.list_of bs)"
    87   by (cases as, cases bs) (simp add: equal)
    86   by (cases as, cases bs) (simp add: equal)
    88 
    87 
    89 primrec tabulate :: "integer \<times> (integer \<Rightarrow> 'a) \<Rightarrow> 'a iarray" where
    88 context
       
    89 begin
       
    90 
       
    91 qualified primrec tabulate :: "integer \<times> (integer \<Rightarrow> 'a) \<Rightarrow> 'a iarray" where
    90   "tabulate (n, f) = IArray (map (f \<circ> integer_of_nat) [0..<nat_of_integer n])"
    92   "tabulate (n, f) = IArray (map (f \<circ> integer_of_nat) [0..<nat_of_integer n])"
    91 
    93 
    92 hide_const (open) tabulate
    94 end
    93 
    95 
    94 lemma [code]:
    96 lemma [code]:
    95   "IArray.of_fun f n = IArray.tabulate (integer_of_nat n, f \<circ> nat_of_integer)"
    97   "IArray.of_fun f n = IArray.tabulate (integer_of_nat n, f \<circ> nat_of_integer)"
    96   by simp
    98   by simp
    97 
    99 
    98 code_printing
   100 code_printing
    99   constant IArray.tabulate \<rightharpoonup> (SML) "Vector.tabulate"
   101   constant IArray.tabulate \<rightharpoonup> (SML) "Vector.tabulate"
   100 
   102 
   101 primrec sub' :: "'a iarray \<times> integer \<Rightarrow> 'a" where
   103 context
       
   104 begin
       
   105 
       
   106 qualified primrec sub' :: "'a iarray \<times> integer \<Rightarrow> 'a" where
   102   [code del]: "sub' (as, n) = IArray.list_of as ! nat_of_integer n"
   107   [code del]: "sub' (as, n) = IArray.list_of as ! nat_of_integer n"
   103 
   108 
   104 hide_const (open) sub'
   109 end
   105 
   110 
   106 lemma [code]:
   111 lemma [code]:
   107   "IArray.sub' (IArray as, n) = as ! nat_of_integer n"
   112   "IArray.sub' (IArray as, n) = as ! nat_of_integer n"
   108   by simp
   113   by simp
   109 
   114 
   112   by simp
   117   by simp
   113 
   118 
   114 code_printing
   119 code_printing
   115   constant IArray.sub' \<rightharpoonup> (SML) "Vector.sub"
   120   constant IArray.sub' \<rightharpoonup> (SML) "Vector.sub"
   116 
   121 
   117 definition length' :: "'a iarray \<Rightarrow> integer" where
   122 context
       
   123 begin
       
   124 
       
   125 qualified definition length' :: "'a iarray \<Rightarrow> integer" where
   118   [code del, simp]: "length' as = integer_of_nat (List.length (IArray.list_of as))"
   126   [code del, simp]: "length' as = integer_of_nat (List.length (IArray.list_of as))"
   119 
   127 
   120 hide_const (open) length'
   128 end
   121 
   129 
   122 lemma [code]:
   130 lemma [code]:
   123   "IArray.length' (IArray as) = integer_of_nat (List.length as)" 
   131   "IArray.length' (IArray as) = integer_of_nat (List.length as)" 
   124   by simp
   132   by simp
   125 
   133