204 equations |
204 equations |
205 \[ f \, x@1 \, \dots \, (C \, y@1 \, \dots \, y@k)\, \dots \, x@n = r \] |
205 \[ f \, x@1 \, \dots \, (C \, y@1 \, \dots \, y@k)\, \dots \, x@n = r \] |
206 such that $C$ is a constructor of the datatype $t$ and all recursive calls of |
206 such that $C$ is a constructor of the datatype $t$ and all recursive calls of |
207 $f$ in $r$ are of the form $f \, \dots \, y@i \, \dots$ for some $i$. Thus |
207 $f$ in $r$ are of the form $f \, \dots \, y@i \, \dots$ for some $i$. Thus |
208 Isabelle immediately sees that $f$ terminates because one (fixed!) argument |
208 Isabelle immediately sees that $f$ terminates because one (fixed!) argument |
209 becomes smaller with every recursive call. There must be exactly one equation |
209 becomes smaller with every recursive call. There must be at most one equation |
210 for each constructor. Their order is immaterial. |
210 for each constructor. Their order is immaterial. |
211 A more general method for defining total recursive functions is introduced in |
211 A more general method for defining total recursive functions is introduced in |
212 {\S}\ref{sec:recdef}. |
212 {\S}\ref{sec:recdef}. |
213 |
213 |
214 \begin{exercise}\label{ex:Tree} |
214 \begin{exercise}\label{ex:Tree} |
470 that the arguments of all recursive calls are smaller in a suitable (user |
470 that the arguments of all recursive calls are smaller in a suitable (user |
471 supplied) sense. In this section we ristrict ourselves to measure functions; |
471 supplied) sense. In this section we ristrict ourselves to measure functions; |
472 more advanced termination proofs are discussed in {\S}\ref{sec:beyond-measure}. |
472 more advanced termination proofs are discussed in {\S}\ref{sec:beyond-measure}. |
473 |
473 |
474 \subsection{Defining recursive functions} |
474 \subsection{Defining recursive functions} |
475 |
475 \label{sec:recdef-examples} |
476 \input{Recdef/document/examples.tex} |
476 \input{Recdef/document/examples.tex} |
477 |
477 |
478 \subsection{Proving termination} |
478 \subsection{Proving termination} |
479 |
479 |
480 \input{Recdef/document/termination.tex} |
480 \input{Recdef/document/termination.tex} |