equal
deleted
inserted
replaced
29 text \<open> |
29 text \<open> |
30 \noindent The runtime of the corresponding code grows exponential due |
30 \noindent The runtime of the corresponding code grows exponential due |
31 to two recursive calls: |
31 to two recursive calls: |
32 \<close> |
32 \<close> |
33 |
33 |
34 text %quotetypewriter \<open> |
34 text %quote \<open> |
35 @{code_stmts fib (consts) fib (Haskell)} |
35 @{code_stmts fib (consts) fib (Haskell)} |
36 \<close> |
36 \<close> |
37 |
37 |
38 text \<open> |
38 text \<open> |
39 \noindent A more efficient implementation would use dynamic |
39 \noindent A more efficient implementation would use dynamic |
66 |
66 |
67 text \<open> |
67 text \<open> |
68 \noindent The resulting code shows only linear growth of runtime: |
68 \noindent The resulting code shows only linear growth of runtime: |
69 \<close> |
69 \<close> |
70 |
70 |
71 text %quotetypewriter \<open> |
71 text %quote \<open> |
72 @{code_stmts fib (consts) fib fib_step (Haskell)} |
72 @{code_stmts fib (consts) fib fib_step (Haskell)} |
73 \<close> |
73 \<close> |
74 |
74 |
75 |
75 |
76 subsection \<open>Datatype refinement\<close> |
76 subsection \<open>Datatype refinement\<close> |
159 |
159 |
160 text \<open> |
160 text \<open> |
161 \noindent The resulting code looks as expected: |
161 \noindent The resulting code looks as expected: |
162 \<close> |
162 \<close> |
163 |
163 |
164 text %quotetypewriter \<open> |
164 text %quote \<open> |
165 @{code_stmts empty enqueue dequeue Queue case_queue (SML)} |
165 @{code_stmts empty enqueue dequeue Queue case_queue (SML)} |
166 \<close> |
166 \<close> |
167 |
167 |
168 text \<open> |
168 text \<open> |
169 The same techniques can also be applied to types which are not |
169 The same techniques can also be applied to types which are not |
258 |
258 |
259 text \<open> |
259 text \<open> |
260 \noindent Then the corresponding code is as follows: |
260 \noindent Then the corresponding code is as follows: |
261 \<close> |
261 \<close> |
262 |
262 |
263 text %quotetypewriter \<open> |
263 text %quote \<open> |
264 @{code_stmts Dlist.empty Dlist.insert Dlist.remove list_of_dlist (Haskell)} |
264 @{code_stmts Dlist.empty Dlist.insert Dlist.remove list_of_dlist (Haskell)} |
265 \<close> |
265 \<close> |
266 |
266 |
267 text \<open> |
267 text \<open> |
268 See further @{cite "Haftmann-Kraus-Kuncar-Nipkow:2013:data_refinement"} |
268 See further @{cite "Haftmann-Kraus-Kuncar-Nipkow:2013:data_refinement"} |