|
9493
|
1 |
\begin{isabelle}%
|
|
|
2 |
%
|
|
|
3 |
\begin{isamarkuptext}%
|
|
|
4 |
\noindent In Exercise~\ref{ex:Tree} we defined a function
|
|
|
5 |
\isa{flatten} from trees to lists. The straightforward version of
|
|
|
6 |
\isa{flatten} is based on \isa{\at} and is thus, like \isa{rev}, quadratic.
|
|
|
7 |
A linear time version of \isa{flatten} again reqires an extra
|
|
|
8 |
argument, the accumulator:%
|
|
|
9 |
\end{isamarkuptext}%
|
|
9541
|
10 |
\isacommand{consts}\ flatten2\ ::\ {"}'a\ tree\ =>\ 'a\ list\ =>\ 'a\ list{"}%
|
|
9493
|
11 |
\begin{isamarkuptext}%
|
|
|
12 |
\noindent Define \isa{flatten2} and prove%
|
|
|
13 |
\end{isamarkuptext}%
|
|
9541
|
14 |
\isacommand{lemma}\ {"}flatten2\ t\ []\ =\ flatten\ t{"}\end{isabelle}%
|
|
9493
|
15 |
%%% Local Variables:
|
|
|
16 |
%%% mode: latex
|
|
|
17 |
%%% TeX-master: "root"
|
|
|
18 |
%%% End:
|