doc-src/TutorialI/Advanced/Partial.thy
changeset 11285 3826c51d980e
parent 11277 a2bff98d6e5d
child 11310 51e70b7bc315
equal deleted inserted replaced
11284:981ea92a86dd 11285:3826c51d980e
    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