module QuicksortList;
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 Bool compare_list(List l1, List l2) =
case l1 {
Nil => True;
Cons(x,xs) => case l2 {
Nil => False;
Cons(y,ys) => if x == y then compare_list(xs,ys) else x <= y;
};
};
def List quicksort_list(List l) = quicksort(compare_list)(l);
def List start(List l) = quicksort_list(l);
{
}