src/HOL/Corec_Examples/Paper_Examples.thy
changeset 80914 d97fdabd9e2b
parent 67051 e7e54a0b9197
equal deleted inserted replaced
80913:46f59511b7bb 80914:d97fdabd9e2b
    12 imports "HOL-Library.BNF_Corec" "HOL-Library.FSet" Complex_Main
    12 imports "HOL-Library.BNF_Corec" "HOL-Library.FSet" Complex_Main
    13 begin
    13 begin
    14 
    14 
    15 section \<open>Examples from the introduction\<close>
    15 section \<open>Examples from the introduction\<close>
    16 
    16 
    17 codatatype 'a stream = SCons (shd: 'a) (stl: "'a stream") (infixr "\<lhd>" 65)
    17 codatatype 'a stream = SCons (shd: 'a) (stl: "'a stream") (infixr \<open>\<lhd>\<close> 65)
    18 
    18 
    19 corec "natsFrom" :: "nat \<Rightarrow> nat stream" where
    19 corec "natsFrom" :: "nat \<Rightarrow> nat stream" where
    20   "natsFrom n = n \<lhd> natsFrom (n + 1)"
    20   "natsFrom n = n \<lhd> natsFrom (n + 1)"
    21 
    21 
    22 corec (friend) add1 :: "nat stream \<Rightarrow> nat stream"
    22 corec (friend) add1 :: "nat stream \<Rightarrow> nat stream"
    27 
    27 
    28 section \<open>Examples from section 3\<close>
    28 section \<open>Examples from section 3\<close>
    29 
    29 
    30 text \<open>We curry the example functions in this section because infix syntax works only for curried functions.\<close>
    30 text \<open>We curry the example functions in this section because infix syntax works only for curried functions.\<close>
    31 
    31 
    32 corec (friend) Plus :: "nat stream \<Rightarrow> nat stream \<Rightarrow> nat stream" (infix "\<oplus>" 67) where
    32 corec (friend) Plus :: "nat stream \<Rightarrow> nat stream \<Rightarrow> nat stream" (infix \<open>\<oplus>\<close> 67) where
    33   "x\<^sub>1 \<oplus> x\<^sub>2 = (shd x\<^sub>1 + shd x\<^sub>2) \<lhd> (stl x\<^sub>1 \<oplus> stl x\<^sub>2)"
    33   "x\<^sub>1 \<oplus> x\<^sub>2 = (shd x\<^sub>1 + shd x\<^sub>2) \<lhd> (stl x\<^sub>1 \<oplus> stl x\<^sub>2)"
    34 
    34 
    35 section \<open>Examples from section 4\<close>
    35 section \<open>Examples from section 4\<close>
    36 
    36 
    37 codatatype 'a llist = LNil | LCons 'a "'a llist"
    37 codatatype 'a llist = LNil | LCons 'a "'a llist"
    41      else if even n then collatz (n div 2)
    41      else if even n then collatz (n div 2)
    42      else LCons n (collatz (3 * n + 1)))"
    42      else LCons n (collatz (3 * n + 1)))"
    43 
    43 
    44 datatype 'a nelist = NEList (hd:'a) (tl:"'a list")
    44 datatype 'a nelist = NEList (hd:'a) (tl:"'a list")
    45 
    45 
    46 primrec (transfer) snoc :: "'a list \<Rightarrow> 'a \<Rightarrow> 'a nelist" (infix "\<rhd>" 64) where
    46 primrec (transfer) snoc :: "'a list \<Rightarrow> 'a \<Rightarrow> 'a nelist" (infix \<open>\<rhd>\<close> 64) where
    47  "[] \<rhd> a = NEList a []"
    47  "[] \<rhd> a = NEList a []"
    48 |"(b # bs) \<rhd> a = NEList b (bs @ [a])"
    48 |"(b # bs) \<rhd> a = NEList b (bs @ [a])"
    49 
    49 
    50 corec (friend) inter :: "nat stream nelist \<Rightarrow> nat stream" where
    50 corec (friend) inter :: "nat stream nelist \<Rightarrow> nat stream" where
    51 "inter xss = shd (hd xss) \<lhd> inter (tl xss \<rhd> stl (hd xss))"
    51 "inter xss = shd (hd xss) \<lhd> inter (tl xss \<rhd> stl (hd xss))"
    66 where "fibA = 0 \<lhd> (1 \<lhd> fibA \<oplus> fibA)"
    66 where "fibA = 0 \<lhd> (1 \<lhd> fibA \<oplus> fibA)"
    67 
    67 
    68 corec fibB :: "nat stream"
    68 corec fibB :: "nat stream"
    69 where "fibB = (0 \<lhd> 1 \<lhd> fibB) \<oplus> (0 \<lhd> fibB)"
    69 where "fibB = (0 \<lhd> 1 \<lhd> fibB) \<oplus> (0 \<lhd> fibB)"
    70 
    70 
    71 corec (friend) times :: "nat stream \<Rightarrow> nat stream \<Rightarrow> nat stream" (infix "\<otimes>" 69)
    71 corec (friend) times :: "nat stream \<Rightarrow> nat stream \<Rightarrow> nat stream" (infix \<open>\<otimes>\<close> 69)
    72 where "xs \<otimes> ys = (shd xs * shd ys) \<lhd> xs \<otimes> stl ys \<oplus> stl xs \<otimes> ys"
    72 where "xs \<otimes> ys = (shd xs * shd ys) \<lhd> xs \<otimes> stl ys \<oplus> stl xs \<otimes> ys"
    73 
    73 
    74 corec (friend) exp :: "nat stream \<Rightarrow> nat stream"
    74 corec (friend) exp :: "nat stream \<Rightarrow> nat stream"
    75 where "exp xs = 2 ^ shd xs \<lhd> (stl xs \<otimes> exp xs)"
    75 where "exp xs = 2 ^ shd xs \<lhd> (stl xs \<otimes> exp xs)"
    76 
    76 
   104 where "facC n a i = (if i = 0 then a \<lhd> facC (n + 1) 1 (n + 1) else facC n (a * i) (i - 1))"
   104 where "facC n a i = (if i = 0 then a \<lhd> facC (n + 1) 1 (n + 1) else facC n (a * i) (i - 1))"
   105 
   105 
   106 corec catalan :: "nat \<Rightarrow> nat stream"
   106 corec catalan :: "nat \<Rightarrow> nat stream"
   107 where "catalan n = (if n > 0 then catalan (n - 1) \<oplus> (0 \<lhd> catalan (n + 1)) else 1 \<lhd> catalan 1)"
   107 where "catalan n = (if n > 0 then catalan (n - 1) \<oplus> (0 \<lhd> catalan (n + 1)) else 1 \<lhd> catalan 1)"
   108 
   108 
   109 corec (friend) heart :: "nat stream \<Rightarrow> nat stream \<Rightarrow> nat stream" (infix "\<heartsuit>" 65)
   109 corec (friend) heart :: "nat stream \<Rightarrow> nat stream \<Rightarrow> nat stream" (infix \<open>\<heartsuit>\<close> 65)
   110 where "xs \<heartsuit> ys = SCons (shd xs * shd ys) ((((xs \<heartsuit> stl ys) \<oplus> (stl xs \<otimes> ys)) \<heartsuit> ys) \<otimes> ys)"
   110 where "xs \<heartsuit> ys = SCons (shd xs * shd ys) ((((xs \<heartsuit> stl ys) \<oplus> (stl xs \<otimes> ys)) \<heartsuit> ys) \<otimes> ys)"
   111 
   111 
   112 corec (friend) g :: "'a stream \<Rightarrow> 'a stream"
   112 corec (friend) g :: "'a stream \<Rightarrow> 'a stream"
   113 where "g xs = shd xs \<lhd> g (g (stl xs))"
   113 where "g xs = shd xs \<lhd> g (g (stl xs))"
   114 
   114