equal
deleted
inserted
replaced
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} |