partition_impl : pure (list:@T, pivot:T, ret:(2$@T))->(2$@T) =
    return ret if !list;
    (h,t) = *list;
    if h < pivot ?
        return partition_impl( t, pivot, ( [0]ret::h, [1]ret ) );
    else ?
        return partition_impl( t, pivot, ( [0]ret, [1]ret::h ) );
    .
.
partition : pure (list:@T, pivot:T)->(2$@T) =
    return partition_impl( list, pivot, (2$[]) );
.

quick_sort : pure (list:@T)->(@T) =
    if !list ? return list;.
    (h,t) = *list;
    if !t ? return list;.
    (pre,post) = partition(t, h);
    if !pre ? return h::quicksort(post);
    else if !post ? return quicksort(pre)::h;
    else return quicksort(pre)::h::quicksort(post);
    .
.