Listing of qsort.m

%   qsort
%
%   adapted from a Prolog program written by David H. D. Warren
%
%   quicksort a list of integers

:- module qsort.

:- interface.

:- import_module list, int, printlist, io.

:- pred main1(list(int)).
:- mode main1(out) is det.

:- pred main(io__state, io__state).
:- mode main(di, uo) is det.

:- pred main3(list(int), io__state, io__state).
:- mode main3(out, di, uo) is det.

:- implementation.

main --> main3(_).

main1(Out) :-
        data(Data),
        qsort(Data, Out, []).

main3(Out) -->
        { main1(Out) },
        print_list(Out).

:- pred data(list(int)).
:- mode data(out) is det.

:- pred qsort(list(int), list(int), list(int)).
:- mode qsort(in, out, in) is det.

:- pred partition(list(int), int, list(int), list(int)).
:- mode partition(in, in, out, out) is det.

data([3, 1, 2]).

qsort([X|L], R, R0) :-
        partition(L, X, L1, L2),
        qsort(L2, R1, R0),
        qsort(L1, R, [X|R1]).
qsort([], R, R).

partition([], _P, [], []).
partition([H|T], P, Lo, Hi) :-
        ( H =< P ->
                partition(T, P, Lo1, Hi),
                Lo = [H|Lo1]
        ;
                partition(T, P, Lo, Hi1),
                Hi = [H|Hi1]
        ).


%------------------------------------------------------------------------------%
:- module printlist.

:- interface.

:- import_module list, int, io.

:- pred print_list(list(int), io__state, io__state).
:- mode print_list(in, di, uo) is det.

:- implementation.

print_list(Xs) -->
        (
                { Xs = [] }
        ->
                io__write_string("[]\n")
        ;
                io__write_string("["),
                print_list_2(Xs),
                io__write_string("]\n")
        ).

:- pred print_list_2(list(int), io__state, io__state).
:- mode print_list_2(in, di, uo) is det.

print_list_2([]) --> [].
print_list_2([X|Xs]) --> 
        io__write_int(X),
        (
                { Xs = [] }
        ->
                []
        ;
                io__write_string(", "),
                print_list_2(Xs)
        ).