equal
deleted
inserted
replaced
11 qsort :: "[['a,'a] => bool, 'a list] => 'a list" |
11 qsort :: "[['a,'a] => bool, 'a list] => 'a list" |
12 |
12 |
13 rules |
13 rules |
14 |
14 |
15 qsort_Nil "qsort le [] = []" |
15 qsort_Nil "qsort le [] = []" |
16 qsort_Cons "qsort le (x#xs) = qsort le [y:xs . ~le x y] @ \ |
16 qsort_Cons "qsort le (x#xs) = qsort le [y:xs . ~le x y] @ |
17 \ (x# qsort le [y:xs . le x y])" |
17 (x# qsort le [y:xs . le x y])" |
18 |
18 |
19 (* computational induction. |
19 (* computational induction. |
20 The dependence of p on x but not xs is intentional. |
20 The dependence of p on x but not xs is intentional. |
21 *) |
21 *) |
22 qsort_ind |
22 qsort_ind |
23 "[| P([]); \ |
23 "[| P([]); |
24 \ !!x xs. [| P([y:xs . ~p x y]); P([y:xs . p x y]) |] ==> \ |
24 !!x xs. [| P([y:xs . ~p x y]); P([y:xs . p x y]) |] ==> |
25 \ P(x#xs) |] \ |
25 P(x#xs) |] |
26 \ ==> P(xs)" |
26 ==> P(xs)" |
27 end |
27 end |