module Quicksort;

def List<A> append<A>(List<A> l1, List<A> l2) =
    case l1 {
    Nil => l2;
    Cons(x,xs) => Cons(x, append(xs,l2));
};

def Pair<List<A>, List<A>> partition<A>(f)(List<A> 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<A> quicksort<A>(gt)(List<A> 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<A> start<A>(f)(List<A> l) = quicksort(f)(l);

{

}