doc-src/TutorialI/Recdef/examples.thy
changeset 9541 d17c0b34d5c8
parent 8771 026f37a86ea7
child 9792 bbefb6ce5cb2
equal deleted inserted replaced
9540:02c51ca9c531 9541:d17c0b34d5c8
    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 \isa{fib} is accompanied by a \bfindex{measure function}
    17 \isa{\isasymlambda{}n.$\;$n} which maps the argument of \isa{fib} to a
    17 @{term"%n. n"} which maps the argument of \isa{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 \isa{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 \isa{Suc(Suc~x)} is strictly greater than both \isa{x} and
    22 @{term"Suc(Suc x)"} is strictly greater than both \isa{x} and
    23 \isa{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 *}
    28 
    28