136 Reasoning about such underdefined functions is like that for other |
136 Reasoning about such underdefined functions is like that for other |
137 recursive functions. Here is a simple example of recursion induction: |
137 recursive functions. Here is a simple example of recursion induction: |
138 *} |
138 *} |
139 |
139 |
140 lemma "wf(step1 f) \<longrightarrow> f(find(f,x)) = find(f,x)" |
140 lemma "wf(step1 f) \<longrightarrow> f(find(f,x)) = find(f,x)" |
141 apply(induct_tac f x rule:find.induct); |
141 apply(induct_tac f x rule: find.induct); |
142 apply simp |
142 apply simp |
143 done |
143 done |
144 |
144 |
145 subsubsection{*The {\tt\slshape while} Combinator*} |
145 subsubsection{*The {\tt\slshape while} Combinator*} |
146 |
146 |
191 \<exists>y. while (\<lambda>(x,x'). x' \<noteq> x) (\<lambda>(x,x'). (x',f x')) (x,f x) = (y,y) \<and> |
191 \<exists>y. while (\<lambda>(x,x'). x' \<noteq> x) (\<lambda>(x,x'). (x',f x')) (x,f x) = (y,y) \<and> |
192 f y = y" |
192 f y = y" |
193 apply(rule_tac P = "\<lambda>(x,x'). x' = f x" and |
193 apply(rule_tac P = "\<lambda>(x,x'). x' = f x" and |
194 r = "inv_image (step1 f) fst" in while_rule); |
194 r = "inv_image (step1 f) fst" in while_rule); |
195 apply auto |
195 apply auto |
196 apply(simp add:inv_image_def step1_def) |
196 apply(simp add: inv_image_def step1_def) |
197 done |
197 done |
198 |
198 |
199 text{* |
199 text{* |
200 The theorem itself is a simple consequence of this lemma: |
200 The theorem itself is a simple consequence of this lemma: |
201 *} |
201 *} |
202 |
202 |
203 theorem "wf(step1 f) \<Longrightarrow> f(find2 f x) = find2 f x" |
203 theorem "wf(step1 f) \<Longrightarrow> f(find2 f x) = find2 f x" |
204 apply(drule_tac x = x in lem) |
204 apply(drule_tac x = x in lem) |
205 apply(auto simp add:find2_def) |
205 apply(auto simp add: find2_def) |
206 done |
206 done |
207 |
207 |
208 text{* Let us conclude this section on partial functions by a |
208 text{* Let us conclude this section on partial functions by a |
209 discussion of the merits of the @{term while} combinator. We have |
209 discussion of the merits of the @{term while} combinator. We have |
210 already seen that the advantage of not having to |
210 already seen that the advantage of not having to |