Re: [eclipse-users] Question about setof/3

Ulrich Scholz wrote:
> 
> I need to sort the result of bagof/3 according to a user-supplied function.
> I thought of something like the Java function "sort(List,Comparator)" in
> java.util.Collections, e.g., a predicate sort/3 with 
> sort(+Comparator,+Random,-Sorted).  I did not find anything similar in the
> Referendce Manual.
> 
> Can you suggest me some code that I could reuse?

Below is a mergesort that does this.  However, I want to stress
that the Eclipse sorting builtins (sort/2,4, msort, keysort, etc)
are significantly faster and it is often preferable to use
a pattern like

my_sort(Random, Sorted) :-
	add_keys(Random, KeyedRandom),
	keysort(KeyedRandom, SortedRandom),
	strip_keys(SortedRandom, SOrted).

   add_keys(SortedRandom) :-
	( foreach(X,Random), foreach(K-X,KeyedRandom) do
		compute_user_key(X, K)
	).

   strip_keys(Random, KeyedRandom) :-
	( foreach(_-X,SortedRandom), foreach(X,Sorted) do
		true
	).

Note also that you can use sort/4 to sort on individual
arguments of compound terms, and that such sorts are stable,
i.e. you can use consecutive calls to sort/4 to achieve
more complex ordering criteria.


% merge sort taking an arbitrary comparison predicate,
% whose signature must correspond to the compare/3 builtin.
%
% ?- predsort(compare, [8,4,6,2],L).
% L = [2, 4, 6, 8]
% Yes (0.00s cpu)

predsort(_, [], []) :- !.
predsort(_, [X], [X]) :- !.
predsort(Pred, [X,Y|L], Sorted) :-
	halve(L, [Y|L], Front, Back),
	predsort(Pred, [X|Front], F),
	predsort(Pred, Back, B),
	predmerge(Pred, F, B, Sorted).


halve([_,_|Count], [H|T], [H|F], B) :- !,
	halve(Count, T, F, B).
halve(_, B, [], B).


predmerge(Pred, [H1|T1], [H2|T2], [Hm|Tm]) :- !,
	functor(Call, Pred, 3),
	arg(1, Call, R),
	arg(2, Call, H1),
	arg(3, Call, H2),
	call(Call),
	(   R = (<) -> Hm = H1, predmerge(Pred, T1, [H2|T2], Tm)
	;   R = (>) -> Hm = H2, predmerge(Pred, [H1|T1], T2, Tm)
	;              Hm = H1, predmerge(Pred, T1, T2, Tm)
	).
predmerge(_, [], L, L) :- !.
predmerge(_, L, [], L).