module Quicksort;
def List append(List l1, List l2) =
case l1 {
Nil => l2;
Cons(x,xs) => Cons(x, append(xs,l2));
};
def Pair, List> partition(f)(List l) =
case l {
Nil => Pair(Nil, Nil);
Cons(x,xs) => case partition(xs) {
Pair(cs,bs) => if f(x) then Pair(cs,Cons(x,bs)) else Pair(Cons(x,cs),bs);
};
};
def List quicksort(gt)(List l) =
case l {
Nil => Nil;
Cons(x,xs) => case partition((A y) => gt(x,y))(xs) {
Pair(ys,zs) => append(quicksort(ys), Cons(x,quicksort(zs)));
};
};
def List start(f)(List l) = quicksort(f)(l);
{
}