module QuicksortPairs;
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(Pair a, Pair b) =
case Pair(a,b) {
Pair(Pair(a1,a2), Pair(b1,b2)) => if a1 != b1 then a1 < b1 else a2 <= b2;
};
def List> quicksort_list(List> l) = quicksort(compare)(l);
def List> start(List> l) = quicksort_list(l);
{
}