|
9645
|
1 |
(*<*)
|
|
|
2 |
theory Nested1 = Nested0:
|
|
|
3 |
(*>*)
|
|
|
4 |
consts trev :: "('a,'b)term => ('a,'b)term"
|
|
|
5 |
|
|
|
6 |
text{*\noindent
|
|
|
7 |
Although the definition of @{term"trev"} is quite natural, we will have
|
|
|
8 |
overcome a minor difficulty in convincing Isabelle of is termination.
|
|
|
9 |
It is precisely this difficulty that is the \textit{rasion d'\^etre} of
|
|
|
10 |
this subsection.
|
|
|
11 |
|
|
|
12 |
Defining @{term"trev"} by \isacommand{recdef} rather than \isacommand{primrec}
|
|
|
13 |
simplifies matters because we are now free to use the recursion equation
|
|
|
14 |
suggested at the end of \S\ref{sec:nested-datatype}:
|
|
|
15 |
*}
|
|
|
16 |
ML"Prim.Add_recdef_congs [map_cong]";
|
|
|
17 |
ML"Prim.print_recdef_congs(Context.the_context())";
|
|
|
18 |
|
|
|
19 |
recdef trev "measure size"
|
|
|
20 |
"trev (Var x) = Var x"
|
|
|
21 |
"trev (App f ts) = App f (rev(map trev ts))";
|
|
|
22 |
ML"Prim.congs []";
|
|
|
23 |
congs map_cong;
|
|
|
24 |
thm trev.simps;
|
|
|
25 |
(*<*)ML"Pretty.setmargin 60"(*>*)
|
|
|
26 |
text{*
|
|
|
27 |
FIXME: recdef should complain and generate unprovable termination condition!
|
|
|
28 |
|
|
|
29 |
The point is that the above termination condition is unprovable because it
|
|
|
30 |
ignores some crucial information: the recursive call of @{term"trev"} will
|
|
|
31 |
not involve arbitrary terms but only those in @{term"ts"}. This is expressed
|
|
|
32 |
by theorem \isa{map\_cong}:
|
|
|
33 |
\begin{quote}
|
|
|
34 |
@{thm[display]"map_cong"}
|
|
|
35 |
\end{quote}
|
|
|
36 |
*}
|
|
|
37 |
|
|
|
38 |
(*<*)
|
|
|
39 |
end
|
|
|
40 |
(*>*)
|
|
|
41 |
|
|
|
42 |
|