9722
|
1 |
%
|
|
2 |
\begin{isabellebody}%
|
9924
|
3 |
\def\isabellecontext{Tree}%
|
17056
|
4 |
%
|
|
5 |
\isadelimtheory
|
|
6 |
%
|
|
7 |
\endisadelimtheory
|
|
8 |
%
|
|
9 |
\isatagtheory
|
|
10 |
%
|
|
11 |
\endisatagtheory
|
|
12 |
{\isafoldtheory}%
|
|
13 |
%
|
|
14 |
\isadelimtheory
|
|
15 |
%
|
|
16 |
\endisadelimtheory
|
8749
|
17 |
%
|
|
18 |
\begin{isamarkuptext}%
|
|
19 |
\noindent
|
11456
|
20 |
Define the datatype of \rmindex{binary trees}:%
|
8749
|
21 |
\end{isamarkuptext}%
|
17175
|
22 |
\isamarkuptrue%
|
|
23 |
\isacommand{datatype}\isamarkupfalse%
|
40406
|
24 |
\ {\isaliteral{27}{\isacharprime}}a\ tree\ {\isaliteral{3D}{\isacharequal}}\ Tip\ {\isaliteral{7C}{\isacharbar}}\ Node\ {\isaliteral{22}{\isachardoublequoteopen}}{\isaliteral{27}{\isacharprime}}a\ tree{\isaliteral{22}{\isachardoublequoteclose}}\ {\isaliteral{27}{\isacharprime}}a\ {\isaliteral{22}{\isachardoublequoteopen}}{\isaliteral{27}{\isacharprime}}a\ tree{\isaliteral{22}{\isachardoublequoteclose}}%
|
8749
|
25 |
\begin{isamarkuptext}%
|
|
26 |
\noindent
|
11456
|
27 |
Define a function \isa{mirror} that mirrors a binary tree
|
10795
|
28 |
by swapping subtrees recursively. Prove%
|
8749
|
29 |
\end{isamarkuptext}%
|
17175
|
30 |
\isamarkuptrue%
|
|
31 |
\isacommand{lemma}\isamarkupfalse%
|
40406
|
32 |
\ mirror{\isaliteral{5F}{\isacharunderscore}}mirror{\isaliteral{3A}{\isacharcolon}}\ {\isaliteral{22}{\isachardoublequoteopen}}mirror{\isaliteral{28}{\isacharparenleft}}mirror\ t{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{3D}{\isacharequal}}\ t{\isaliteral{22}{\isachardoublequoteclose}}%
|
17056
|
33 |
\isadelimproof
|
|
34 |
%
|
|
35 |
\endisadelimproof
|
|
36 |
%
|
|
37 |
\isatagproof
|
|
38 |
%
|
|
39 |
\endisatagproof
|
|
40 |
{\isafoldproof}%
|
|
41 |
%
|
|
42 |
\isadelimproof
|
|
43 |
%
|
|
44 |
\endisadelimproof
|
11866
|
45 |
%
|
9493
|
46 |
\begin{isamarkuptext}%
|
|
47 |
\noindent
|
|
48 |
Define a function \isa{flatten} that flattens a tree into a list
|
|
49 |
by traversing it in infix order. Prove%
|
|
50 |
\end{isamarkuptext}%
|
17175
|
51 |
\isamarkuptrue%
|
|
52 |
\isacommand{lemma}\isamarkupfalse%
|
40406
|
53 |
\ {\isaliteral{22}{\isachardoublequoteopen}}flatten{\isaliteral{28}{\isacharparenleft}}mirror\ t{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{3D}{\isacharequal}}\ rev{\isaliteral{28}{\isacharparenleft}}flatten\ t{\isaliteral{29}{\isacharparenright}}{\isaliteral{22}{\isachardoublequoteclose}}%
|
17056
|
54 |
\isadelimproof
|
|
55 |
%
|
|
56 |
\endisadelimproof
|
|
57 |
%
|
|
58 |
\isatagproof
|
|
59 |
%
|
|
60 |
\endisatagproof
|
|
61 |
{\isafoldproof}%
|
|
62 |
%
|
|
63 |
\isadelimproof
|
|
64 |
%
|
|
65 |
\endisadelimproof
|
|
66 |
%
|
|
67 |
\isadelimtheory
|
|
68 |
%
|
|
69 |
\endisadelimtheory
|
|
70 |
%
|
|
71 |
\isatagtheory
|
|
72 |
%
|
|
73 |
\endisatagtheory
|
|
74 |
{\isafoldtheory}%
|
|
75 |
%
|
|
76 |
\isadelimtheory
|
|
77 |
%
|
|
78 |
\endisadelimtheory
|
11866
|
79 |
\end{isabellebody}%
|
9145
|
80 |
%%% Local Variables:
|
|
81 |
%%% mode: latex
|
|
82 |
%%% TeX-master: "root"
|
|
83 |
%%% End:
|