equal
deleted
inserted
replaced
167 Hence all lists are of the form @{const Nil}, or @{term"Cons x Nil"}, |
167 Hence all lists are of the form @{const Nil}, or @{term"Cons x Nil"}, |
168 or @{term"Cons x (Cons y Nil)"}, etc. |
168 or @{term"Cons x (Cons y Nil)"}, etc. |
169 \item \isacom{datatype} requires no quotation marks on the |
169 \item \isacom{datatype} requires no quotation marks on the |
170 left-hand side, but on the right-hand side each of the argument |
170 left-hand side, but on the right-hand side each of the argument |
171 types of a constructor needs to be enclosed in quotation marks, unless |
171 types of a constructor needs to be enclosed in quotation marks, unless |
172 it is just an identifier (e.g.\ @{typ nat} or @{typ 'a}). |
172 it is just an identifier (e.g., @{typ nat} or @{typ 'a}). |
173 \end{itemize} |
173 \end{itemize} |
174 We also define two standard functions, append and reverse: *} |
174 We also define two standard functions, append and reverse: *} |
175 |
175 |
176 fun app :: "'a list \<Rightarrow> 'a list \<Rightarrow> 'a list" where |
176 fun app :: "'a list \<Rightarrow> 'a list \<Rightarrow> 'a list" where |
177 "app Nil ys = ys" | |
177 "app Nil ys = ys" | |
219 \subsubsection{Structural Induction for Lists} |
219 \subsubsection{Structural Induction for Lists} |
220 |
220 |
221 Just as for natural numbers, there is a proof principle of induction for |
221 Just as for natural numbers, there is a proof principle of induction for |
222 lists. Induction over a list is essentially induction over the length of |
222 lists. Induction over a list is essentially induction over the length of |
223 the list, although the length remains implicit. To prove that some property |
223 the list, although the length remains implicit. To prove that some property |
224 @{text P} holds for all lists @{text xs}, i.e.\ \mbox{@{prop"P(xs)"}}, |
224 @{text P} holds for all lists @{text xs}, i.e., \mbox{@{prop"P(xs)"}}, |
225 you need to prove |
225 you need to prove |
226 \begin{enumerate} |
226 \begin{enumerate} |
227 \item the base case @{prop"P(Nil)"} and |
227 \item the base case @{prop"P(Nil)"} and |
228 \item the inductive case @{prop"P(Cons x xs)"} under the assumption @{prop"P(xs)"}, for some arbitrary but fixed @{text x} and @{text xs}. |
228 \item the inductive case @{prop"P(Cons x xs)"} under the assumption @{prop"P(xs)"}, for some arbitrary but fixed @{text x} and @{text xs}. |
229 \end{enumerate} |
229 \end{enumerate} |