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