src/HOL/Library/Efficient_Nat.thy
changeset 25919 8b1c0d434824
parent 25885 6fbc3f54f819
child 25931 b1d1ab3e5a2e
equal deleted inserted replaced
25918:82dd239e0f65 25919:8b1c0d434824
     4 *)
     4 *)
     5 
     5 
     6 header {* Implementation of natural numbers by integers *}
     6 header {* Implementation of natural numbers by integers *}
     7 
     7 
     8 theory Efficient_Nat
     8 theory Efficient_Nat
     9 imports Main Code_Integer
     9 imports Main Code_Integer Code_Index
    10 begin
    10 begin
    11 
    11 
    12 text {*
    12 text {*
    13 When generating code for functions on natural numbers, the canonical
    13 When generating code for functions on natural numbers, the canonical
    14 representation using @{term "0::nat"} and @{term "Suc"} is unsuitable for
    14 representation using @{term "0::nat"} and @{term "Suc"} is unsuitable for
    53   shows "number_of k = nat_of_int (number_of k)"
    53   shows "number_of k = nat_of_int (number_of k)"
    54   unfolding nat_of_int_def [OF assms] nat_number_of_def number_of_is_id ..
    54   unfolding nat_of_int_def [OF assms] nat_number_of_def number_of_is_id ..
    55 
    55 
    56 lemma nat_of_int_of_number_of_aux:
    56 lemma nat_of_int_of_number_of_aux:
    57   fixes k
    57   fixes k
    58   assumes "Numeral.Pls \<le> k \<equiv> True"
    58   assumes "Int.Pls \<le> k \<equiv> True"
    59   shows "k \<ge> 0"
    59   shows "k \<ge> 0"
    60   using assms unfolding Pls_def by simp
    60   using assms unfolding Pls_def by simp
    61 
    61 
    62 lemma nat_of_int_int:
    62 lemma nat_of_int_int:
    63   "nat_of_int (int_of_nat n) = n"
    63   "nat_of_int (int_of_nat n) = n"
   257   let
   257   let
   258     val simplify_less = Simplifier.rewrite 
   258     val simplify_less = Simplifier.rewrite 
   259       (HOL_basic_ss addsimps (@{thms less_numeral_code} @ @{thms less_eq_numeral_code}));
   259       (HOL_basic_ss addsimps (@{thms less_numeral_code} @ @{thms less_eq_numeral_code}));
   260     fun mk_rew (t, ty) =
   260     fun mk_rew (t, ty) =
   261       if ty = HOLogic.natT andalso 0 <= HOLogic.dest_numeral t then
   261       if ty = HOLogic.natT andalso 0 <= HOLogic.dest_numeral t then
   262         Thm.capply @{cterm "(op \<le>) Numeral.Pls"} (Thm.cterm_of thy t)
   262         Thm.capply @{cterm "(op \<le>) Int.Pls"} (Thm.cterm_of thy t)
   263         |> simplify_less
   263         |> simplify_less
   264         |> (fn thm => @{thm nat_of_int_of_number_of_aux} OF [thm])
   264         |> (fn thm => @{thm nat_of_int_of_number_of_aux} OF [thm])
   265         |> (fn thm => @{thm nat_of_int_of_number_of} OF [thm])
   265         |> (fn thm => @{thm nat_of_int_of_number_of} OF [thm])
   266         |> (fn thm => @{thm eq_reflection} OF [thm])
   266         |> (fn thm => @{thm eq_reflection} OF [thm])
   267         |> SOME
   267         |> SOME
   413 
   413 
   414 
   414 
   415 subsection {* Module names *}
   415 subsection {* Module names *}
   416 
   416 
   417 code_modulename SML
   417 code_modulename SML
       
   418   Int Integer
   418   Nat Integer
   419   Nat Integer
   419   Divides Integer
   420   Divides Integer
   420   Efficient_Nat Integer
   421   Efficient_Nat Integer
   421 
   422 
   422 code_modulename OCaml
   423 code_modulename OCaml
       
   424   Int Integer
   423   Nat Integer
   425   Nat Integer
   424   Divides Integer
   426   Divides Integer
   425   Efficient_Nat Integer
   427   Efficient_Nat Integer
   426 
   428 
   427 code_modulename Haskell
   429 code_modulename Haskell
       
   430   Int Integer
   428   Nat Integer
   431   Nat Integer
   429   Divides Integer
   432   Divides Integer
   430   Efficient_Nat Integer
   433   Efficient_Nat Integer
   431 
   434 
   432 hide const nat_of_int int_of_nat
   435 hide const nat_of_int int_of_nat