src/Doc/Tutorial/Datatype/Nested.thy
changeset 69597 ff784d5a5bfb
parent 69505 cc2d676d5395
child 76987 4c275405faae
equal deleted inserted replaced
69596:c8a2755bf220 69597:ff784d5a5bfb
    15 datatype ('v,'f)"term" = Var 'v | App 'f "('v,'f)term list"
    15 datatype ('v,'f)"term" = Var 'v | App 'f "('v,'f)term list"
    16 
    16 
    17 text\<open>\noindent
    17 text\<open>\noindent
    18 Note that we need to quote \<open>term\<close> on the left to avoid confusion with
    18 Note that we need to quote \<open>term\<close> on the left to avoid confusion with
    19 the Isabelle command \isacommand{term}.
    19 the Isabelle command \isacommand{term}.
    20 Parameter @{typ"'v"} is the type of variables and @{typ"'f"} the type of
    20 Parameter \<^typ>\<open>'v\<close> is the type of variables and \<^typ>\<open>'f\<close> the type of
    21 function symbols.
    21 function symbols.
    22 A mathematical term like $f(x,g(y))$ becomes @{term"App f [Var x, App g
    22 A mathematical term like $f(x,g(y))$ becomes \<^term>\<open>App f [Var x, App g
    23   [Var y]]"}, where @{term f}, @{term g}, @{term x}, @{term y} are
    23   [Var y]]\<close>, where \<^term>\<open>f\<close>, \<^term>\<open>g\<close>, \<^term>\<open>x\<close>, \<^term>\<open>y\<close> are
    24 suitable values, e.g.\ numbers or strings.
    24 suitable values, e.g.\ numbers or strings.
    25 
    25 
    26 What complicates the definition of \<open>term\<close> is the nested occurrence of
    26 What complicates the definition of \<open>term\<close> is the nested occurrence of
    27 \<open>term\<close> inside \<open>list\<close> on the right-hand side. In principle,
    27 \<open>term\<close> inside \<open>list\<close> on the right-hand side. In principle,
    28 nested recursion can be eliminated in favour of mutual recursion by unfolding
    28 nested recursion can be eliminated in favour of mutual recursion by unfolding
    69                   substs Var ts = (ts::('v,'f)term list)"
    69                   substs Var ts = (ts::('v,'f)term list)"
    70 apply(induct_tac t and ts rule: subst.induct substs.induct, simp_all)
    70 apply(induct_tac t and ts rule: subst.induct substs.induct, simp_all)
    71 done
    71 done
    72 
    72 
    73 text\<open>\noindent
    73 text\<open>\noindent
    74 Note that @{term Var} is the identity substitution because by definition it
    74 Note that \<^term>\<open>Var\<close> is the identity substitution because by definition it
    75 leaves variables unchanged: @{prop"subst Var (Var x) = Var x"}. Note also
    75 leaves variables unchanged: \<^prop>\<open>subst Var (Var x) = Var x\<close>. Note also
    76 that the type annotations are necessary because otherwise there is nothing in
    76 that the type annotations are necessary because otherwise there is nothing in
    77 the goal to enforce that both halves of the goal talk about the same type
    77 the goal to enforce that both halves of the goal talk about the same type
    78 parameters \<open>('v,'f)\<close>. As a result, induction would fail
    78 parameters \<open>('v,'f)\<close>. As a result, induction would fail
    79 because the two halves of the goal would be unrelated.
    79 because the two halves of the goal would be unrelated.
    80 
    80 
    85 Correct this statement (you will find that it does not type-check),
    85 Correct this statement (you will find that it does not type-check),
    86 strengthen it, and prove it. (Note: \<open>\<circ>\<close> is function composition;
    86 strengthen it, and prove it. (Note: \<open>\<circ>\<close> is function composition;
    87 its definition is found in theorem @{thm[source]o_def}).
    87 its definition is found in theorem @{thm[source]o_def}).
    88 \end{exercise}
    88 \end{exercise}
    89 \begin{exercise}\label{ex:trev-trev}
    89 \begin{exercise}\label{ex:trev-trev}
    90   Define a function @{term trev} of type @{typ"('v,'f)term => ('v,'f)term"}
    90   Define a function \<^term>\<open>trev\<close> of type \<^typ>\<open>('v,'f)term => ('v,'f)term\<close>
    91 that recursively reverses the order of arguments of all function symbols in a
    91 that recursively reverses the order of arguments of all function symbols in a
    92   term. Prove that @{prop"trev(trev t) = t"}.
    92   term. Prove that \<^prop>\<open>trev(trev t) = t\<close>.
    93 \end{exercise}
    93 \end{exercise}
    94 
    94 
    95 The experienced functional programmer may feel that our definition of
    95 The experienced functional programmer may feel that our definition of
    96 @{term subst} is too complicated in that @{const substs} is
    96 \<^term>\<open>subst\<close> is too complicated in that \<^const>\<open>substs\<close> is
    97 unnecessary. The @{term App}-case can be defined directly as
    97 unnecessary. The \<^term>\<open>App\<close>-case can be defined directly as
    98 @{term[display]"subst s (App f ts) = App f (map (subst s) ts)"}
    98 @{term[display]"subst s (App f ts) = App f (map (subst s) ts)"}
    99 where @{term"map"} is the standard list function such that
    99 where \<^term>\<open>map\<close> is the standard list function such that
   100 \<open>map f [x1,...,xn] = [f x1,...,f xn]\<close>. This is true, but Isabelle
   100 \<open>map f [x1,...,xn] = [f x1,...,f xn]\<close>. This is true, but Isabelle
   101 insists on the conjunctive format. Fortunately, we can easily \emph{prove}
   101 insists on the conjunctive format. Fortunately, we can easily \emph{prove}
   102 that the suggested equation holds:
   102 that the suggested equation holds:
   103 \<close>
   103 \<close>
   104 (*<*)
   104 (*<*)
   138 simplification rule:
   138 simplification rule:
   139 \<close>
   139 \<close>
   140 
   140 
   141 declare subst_App [simp del]
   141 declare subst_App [simp del]
   142 
   142 
   143 text\<open>\noindent The advantage is that now we have replaced @{const
   143 text\<open>\noindent The advantage is that now we have replaced \<^const>\<open>substs\<close> by \<^const>\<open>map\<close>, we can profit from the large number of
   144 substs} by @{const map}, we can profit from the large number of
   144 pre-proved lemmas about \<^const>\<open>map\<close>.  Unfortunately, inductive proofs
   145 pre-proved lemmas about @{const map}.  Unfortunately, inductive proofs
       
   146 about type \<open>term\<close> are still awkward because they expect a
   145 about type \<open>term\<close> are still awkward because they expect a
   147 conjunction. One could derive a new induction principle as well (see
   146 conjunction. One could derive a new induction principle as well (see
   148 \S\ref{sec:derive-ind}), but simpler is to stop using
   147 \S\ref{sec:derive-ind}), but simpler is to stop using
   149 \isacommand{primrec} and to define functions with \isacommand{fun}
   148 \isacommand{primrec} and to define functions with \isacommand{fun}
   150 instead.  Simple uses of \isacommand{fun} are described in
   149 instead.  Simple uses of \isacommand{fun} are described in