doc-src/TutorialI/Recdef/Nested2.thy
changeset 10885 90695f46440b
parent 10654 458068404143
child 11196 bb4ede27fcb7
equal deleted inserted replaced
10884:2995639c6a09 10885:90695f46440b
    13  "trev (Var x) = Var x"
    13  "trev (Var x) = Var x"
    14  "trev (App f ts) = App f (rev(map trev ts))";
    14  "trev (App f ts) = App f (rev(map trev ts))";
    15 (*>*)
    15 (*>*)
    16 text{*\noindent
    16 text{*\noindent
    17 By making this theorem a simplification rule, \isacommand{recdef}
    17 By making this theorem a simplification rule, \isacommand{recdef}
    18 applies it automatically and the above definition of @{term"trev"}
    18 applies it automatically and the definition of @{term"trev"}
    19 succeeds now. As a reward for our effort, we can now prove the desired
    19 succeeds now. As a reward for our effort, we can now prove the desired
    20 lemma directly. The key is the fact that we no longer need the verbose
    20 lemma directly.  We no longer need the verbose
    21 induction schema for type @{text"term"} but the simpler one arising from
    21 induction schema for type @{text"term"} and can use the simpler one arising from
    22 @{term"trev"}:
    22 @{term"trev"}:
    23 *};
    23 *};
    24 
    24 
    25 lemma "trev(trev t) = t";
    25 lemma "trev(trev t) = t";
    26 apply(induct_tac t rule:trev.induct);
    26 apply(induct_tac t rule:trev.induct);
    31 *};
    31 *};
    32 
    32 
    33 by(simp_all add:rev_map sym[OF map_compose] cong:map_cong);
    33 by(simp_all add:rev_map sym[OF map_compose] cong:map_cong);
    34 
    34 
    35 text{*\noindent
    35 text{*\noindent
    36 If the proof of the induction step mystifies you, we recommend to go through
    36 If the proof of the induction step mystifies you, we recommend that you go through
    37 the chain of simplification steps in detail; you will probably need the help of
    37 the chain of simplification steps in detail; you will probably need the help of
    38 @{text"trace_simp"}. Theorem @{thm[source]map_cong} is discussed below.
    38 @{text"trace_simp"}. Theorem @{thm[source]map_cong} is discussed below.
    39 %\begin{quote}
    39 %\begin{quote}
    40 %{term[display]"trev(trev(App f ts))"}\\
    40 %{term[display]"trev(trev(App f ts))"}\\
    41 %{term[display]"App f (rev(map trev (rev(map trev ts))))"}\\
    41 %{term[display]"App f (rev(map trev (rev(map trev ts))))"}\\
    44 %{term[display]"App f (map (trev o trev) ts)"}\\
    44 %{term[display]"App f (map (trev o trev) ts)"}\\
    45 %{term[display]"App f (map (%x. x) ts)"}\\
    45 %{term[display]"App f (map (%x. x) ts)"}\\
    46 %{term[display]"App f ts"}
    46 %{term[display]"App f ts"}
    47 %\end{quote}
    47 %\end{quote}
    48 
    48 
    49 The above definition of @{term"trev"} is superior to the one in
    49 The definition of @{term"trev"} above is superior to the one in
    50 \S\ref{sec:nested-datatype} because it brings @{term"rev"} into play, about
    50 \S\ref{sec:nested-datatype} because it uses @{term"rev"}
    51 which already know a lot, in particular @{prop"rev(rev xs) = xs"}.
    51 and lets us use existing facts such as \hbox{@{prop"rev(rev xs) = xs"}}.
    52 Thus this proof is a good example of an important principle:
    52 Thus this proof is a good example of an important principle:
    53 \begin{quote}
    53 \begin{quote}
    54 \emph{Chose your definitions carefully\\
    54 \emph{Chose your definitions carefully\\
    55 because they determine the complexity of your proofs.}
    55 because they determine the complexity of your proofs.}
    56 \end{quote}
    56 \end{quote}