equal
deleted
inserted
replaced
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 |