doc-src/TutorialI/Recdef/examples.thy
changeset 9792 bbefb6ce5cb2
parent 9541 d17c0b34d5c8
child 9933 9feb1e0c4cb3
equal deleted inserted replaced
9791:a39e5d43de55 9792:bbefb6ce5cb2
    11   "fib 0 = 0"
    11   "fib 0 = 0"
    12   "fib 1 = 1"
    12   "fib 1 = 1"
    13   "fib (Suc(Suc x)) = fib x + fib (Suc x)";
    13   "fib (Suc(Suc x)) = fib x + fib (Suc x)";
    14 
    14 
    15 text{*\noindent
    15 text{*\noindent
    16 The definition of \isa{fib} is accompanied by a \bfindex{measure function}
    16 The definition of @{term"fib"} is accompanied by a \bfindex{measure function}
    17 @{term"%n. n"} which maps the argument of \isa{fib} to a
    17 @{term"%n. n"} which maps the argument of @{term"fib"} to a
    18 natural number. The requirement is that in each equation the measure of the
    18 natural number. The requirement is that in each equation the measure of the
    19 argument on the left-hand side is strictly greater than the measure of the
    19 argument on the left-hand side is strictly greater than the measure of the
    20 argument of each recursive call. In the case of \isa{fib} this is
    20 argument of each recursive call. In the case of @{term"fib"} this is
    21 obviously true because the measure function is the identity and
    21 obviously true because the measure function is the identity and
    22 @{term"Suc(Suc x)"} is strictly greater than both \isa{x} and
    22 @{term"Suc(Suc x)"} is strictly greater than both @{term"x"} and
    23 @{term"Suc x"}.
    23 @{term"Suc x"}.
    24 
    24 
    25 Slightly more interesting is the insertion of a fixed element
    25 Slightly more interesting is the insertion of a fixed element
    26 between any two elements of a list:
    26 between any two elements of a list:
    27 *}
    27 *}
    53 recdef sep1 "measure (\\<lambda>(a,xs). length xs)"
    53 recdef sep1 "measure (\\<lambda>(a,xs). length xs)"
    54   "sep1(a, x#y#zs) = x # a # sep1(a,y#zs)"
    54   "sep1(a, x#y#zs) = x # a # sep1(a,y#zs)"
    55   "sep1(a, xs)     = xs";
    55   "sep1(a, xs)     = xs";
    56 
    56 
    57 text{*\noindent
    57 text{*\noindent
    58 This defines exactly the same function as \isa{sep} above, i.e.\
    58 This defines exactly the same function as @{term"sep"} above, i.e.\
    59 \isa{sep1 = sep}.
    59 @{prop"sep1 = sep"}.
    60 
    60 
    61 \begin{warn}
    61 \begin{warn}
    62   \isacommand{recdef} only takes the first argument of a (curried)
    62   \isacommand{recdef} only takes the first argument of a (curried)
    63   recursive function into account. This means both the termination measure
    63   recursive function into account. This means both the termination measure
    64   and pattern matching can only use that first argument. In general, you will
    64   and pattern matching can only use that first argument. In general, you will
    82   "swap12 (x#y#zs) = y#x#zs"
    82   "swap12 (x#y#zs) = y#x#zs"
    83   "swap12 zs       = zs";
    83   "swap12 zs       = zs";
    84 
    84 
    85 text{*\noindent
    85 text{*\noindent
    86 For non-recursive functions the termination measure degenerates to the empty
    86 For non-recursive functions the termination measure degenerates to the empty
    87 set \isa{\{\}}.
    87 set @{term"{}"}.
    88 *}
    88 *}
    89 
    89 
    90 (*<*)
    90 (*<*)
    91 end
    91 end
    92 (*>*)
    92 (*>*)