equal
deleted
inserted
replaced
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 |