9722
|
1 |
%
|
|
2 |
\begin{isabellebody}%
|
10267
|
3 |
\def\isabellecontext{Tree{\isadigit{2}}}%
|
11866
|
4 |
\isamarkupfalse%
|
9493
|
5 |
%
|
|
6 |
\begin{isamarkuptext}%
|
|
7 |
\noindent In Exercise~\ref{ex:Tree} we defined a function
|
|
8 |
\isa{flatten} from trees to lists. The straightforward version of
|
9792
|
9 |
\isa{flatten} is based on \isa{{\isacharat}} and is thus, like \isa{rev},
|
|
10 |
quadratic. A linear time version of \isa{flatten} again reqires an extra
|
9493
|
11 |
argument, the accumulator:%
|
|
12 |
\end{isamarkuptext}%
|
11866
|
13 |
\isamarkuptrue%
|
13305
|
14 |
\isacommand{consts}\ flatten{\isadigit{2}}\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequote}{\isacharprime}a\ tree\ {\isasymRightarrow}\ {\isacharprime}a\ list\ {\isasymRightarrow}\ {\isacharprime}a\ list{\isachardoublequote}\isamarkupfalse%
|
11866
|
15 |
\isamarkupfalse%
|
|
16 |
%
|
9493
|
17 |
\begin{isamarkuptext}%
|
10187
|
18 |
\noindent Define \isa{flatten{\isadigit{2}}} and prove%
|
9493
|
19 |
\end{isamarkuptext}%
|
11866
|
20 |
\isamarkuptrue%
|
|
21 |
\isamarkupfalse%
|
|
22 |
\isamarkupfalse%
|
|
23 |
\isamarkupfalse%
|
|
24 |
\isacommand{lemma}\ {\isachardoublequote}flatten{\isadigit{2}}\ t\ {\isacharbrackleft}{\isacharbrackright}\ {\isacharequal}\ flatten\ t{\isachardoublequote}\isamarkupfalse%
|
|
25 |
\isamarkupfalse%
|
|
26 |
\isamarkupfalse%
|
|
27 |
\end{isabellebody}%
|
9493
|
28 |
%%% Local Variables:
|
|
29 |
%%% mode: latex
|
|
30 |
%%% TeX-master: "root"
|
|
31 |
%%% End:
|