equal
deleted
inserted
replaced
93 consts find :: "('a \<Rightarrow> 'a) \<times> 'a \<Rightarrow> 'a" |
93 consts find :: "('a \<Rightarrow> 'a) \<times> 'a \<Rightarrow> 'a" |
94 recdef find "same_fst (\<lambda>f. wf(step1 f)) step1" |
94 recdef find "same_fst (\<lambda>f. wf(step1 f)) step1" |
95 "find(f,x) = (if wf(step1 f) |
95 "find(f,x) = (if wf(step1 f) |
96 then if f x = x then x else find(f, f x) |
96 then if f x = x then x else find(f, f x) |
97 else arbitrary)" |
97 else arbitrary)" |
98 (hints recdef_simp:same_fst_def step1_def) |
98 (hints recdef_simp: step1_def) |
99 |
99 |
100 text{*\noindent |
100 text{*\noindent |
101 The recursion equation itself should be clear enough: it is our aborted |
101 The recursion equation itself should be clear enough: it is our aborted |
102 first attempt augmented with a check that there are no non-trivial loops. |
102 first attempt augmented with a check that there are no non-trivial loops. |
103 To express the required well-founded relation we employ the |
103 To express the required well-founded relation we employ the |
113 @{thm[display]wf_same_fst[no_vars]} |
113 @{thm[display]wf_same_fst[no_vars]} |
114 is known to the well-foundedness prover of \isacommand{recdef}. Thus |
114 is known to the well-foundedness prover of \isacommand{recdef}. Thus |
115 well-foundedness of the relation given to \isacommand{recdef} is immediate. |
115 well-foundedness of the relation given to \isacommand{recdef} is immediate. |
116 Furthermore, each recursive call descends along that relation: the first |
116 Furthermore, each recursive call descends along that relation: the first |
117 argument stays unchanged and the second one descends along @{term"step1 |
117 argument stays unchanged and the second one descends along @{term"step1 |
118 f"}. The proof merely requires unfolding of some definitions, as specified in |
118 f"}. The proof requires unfolding the definition of @{term step1}, |
119 the \isacommand{hints} above. |
119 as specified in the \isacommand{hints} above. |
120 |
120 |
121 Normally you will then derive the following conditional variant of and from |
121 Normally you will then derive the following conditional variant of and from |
122 the recursion equation |
122 the recursion equation |
123 *} |
123 *} |
124 |
124 |