doc-src/TutorialI/fp.tex
changeset 10654 458068404143
parent 10608 620647438780
child 10795 9e888d60d3e5
equal deleted inserted replaced
10653:55f33da63366 10654:458068404143
   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}