equal
deleted
inserted
replaced
29 text {* |
29 text {* |
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 *} |
32 *} |
33 |
33 |
34 text %quote {* |
34 text %quote %typewriter {* |
35 \begin{typewriter} |
35 @{code_stmts fib (consts) fib (Haskell)} |
36 @{code_stmts fib (consts) fib (Haskell)} |
|
37 \end{typewriter} |
|
38 *} |
36 *} |
39 |
37 |
40 text {* |
38 text {* |
41 \noindent A more efficient implementation would use dynamic |
39 \noindent A more efficient implementation would use dynamic |
42 programming, e.g.~sharing of common intermediate results between |
40 programming, e.g.~sharing of common intermediate results between |
69 |
67 |
70 text {* |
68 text {* |
71 \noindent The resulting code shows only linear growth of runtime: |
69 \noindent The resulting code shows only linear growth of runtime: |
72 *} |
70 *} |
73 |
71 |
74 text %quote {* |
72 text %quote %typewriter {* |
75 \begin{typewriter} |
73 @{code_stmts fib (consts) fib fib_step (Haskell)} |
76 @{code_stmts fib (consts) fib fib_step (Haskell)} |
|
77 \end{typewriter} |
|
78 *} |
74 *} |
79 |
75 |
80 |
76 |
81 subsection {* Datatype refinement *} |
77 subsection {* Datatype refinement *} |
82 |
78 |
159 |
155 |
160 text {* |
156 text {* |
161 \noindent The resulting code looks as expected: |
157 \noindent The resulting code looks as expected: |
162 *} |
158 *} |
163 |
159 |
164 text %quote {* |
160 text %quote %typewriter {* |
165 \begin{typewriter} |
161 @{code_stmts empty enqueue dequeue (SML)} |
166 @{code_stmts empty enqueue dequeue (SML)} |
|
167 \end{typewriter} |
|
168 *} |
162 *} |
169 |
163 |
170 text {* |
164 text {* |
171 The same techniques can also be applied to types which are not |
165 The same techniques can also be applied to types which are not |
172 specified as datatypes, e.g.~type @{typ int} is originally specified |
166 specified as datatypes, e.g.~type @{typ int} is originally specified |
257 |
251 |
258 text {* |
252 text {* |
259 \noindent Then the corresponding code is as follows: |
253 \noindent Then the corresponding code is as follows: |
260 *} |
254 *} |
261 |
255 |
262 text %quote {* |
256 text %quote %typewriter {* |
263 \begin{typewriter} |
257 @{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 \end{typewriter} |
|
266 *} (*(types) dlist (consts) dempty dinsert dremove list_of List.member insert remove *) |
258 *} (*(types) dlist (consts) dempty dinsert dremove list_of List.member insert remove *) |
267 |
259 |
268 text {* |
260 text {* |
269 Typical data structures implemented by representations involving |
261 Typical data structures implemented by representations involving |
270 invariants are available in the library, e.g.~theories @{theory |
262 invariants are available in the library, e.g.~theories @{theory |