src/HOL/ex/Qsort.thy
changeset 1151 c820b3cc3df0
parent 969 b051e2fc2e34
child 1376 92f83b9d17e1
equal deleted inserted replaced
1150:66512c9e6bd6 1151:c820b3cc3df0
    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