:- module(_,_).

% Quick-sort qsort using difference lists (no append!)
% ----------------------------------------------------

%% ** Version 1: using -/2 functor and explicit unifications
%% (for explanation)

qsort_dl1(L,SL) :-
    qsort_dl1_(L,SL-SLE),
    SLE = [].

qsort_dl1_([],SLE-SLE).
qsort_dl1_([X|L],SL-SLE) :-
    partition(L,X,S,B),
    qsort_dl1_(S,SS-SSE),
    qsort_dl1_(B,BS-BSE),
    SSE = [X|BS],
    SL = SS,
    BSE = SLE.

% Partition is exactly the same as in standard qsort:
partition([],_P,[],[]).
partition([E|R],P,[E|Smalls],Bigs) :- % Take first element E
    E < P,            % If E < P add to list of smaller ones
    partition(R,P,Smalls,Bigs).
partition([E|R],P,Smalls,[E|Bigs]) :-
    E >= P,           % If E >= P add to list of larger ones
    partition(R,P,Smalls,Bigs).

% Try:
% qsort_dl1([5,2,1,3,7,6], SL).
% Run it in the debugger!

%% ** Version 2: still using -/ functor, but with unifications inlined

qsort_dl2(L,SL) :-
    qsort_dl2_(L,SL-[]).

    
qsort_dl2_([],SLE-SLE).
qsort_dl2_([X|L],SL-SLE) :-
    partition(L,X,S,B),
    qsort_dl2_(S,SL-[X|BS]),
    qsort_dl2_(B,BS-SLE).

% Try:
% qsort_dl2([5,2,1,3,7,6], SL).

%% ** Version 3: using extra arguments, unifications inlined

qsort_dl(L,SL) :-
    qsort_dl_(L,SL,[]).
    
qsort_dl_([],SLE,SLE).
qsort_dl_([X|L],SL,SLE) :-
    partition(L,X,S,B),
    qsort_dl_(S,SL,[X|BS]),
    qsort_dl_(B,BS,SLE).

% Try:
% qsort_dl([5,2,1,3,7,6], SL).