Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Example how to use predsort(:Compare, +List, -Sorted) in prolog

I want to order a custom list. The list I want to order will be in this form...

[n(_,2,_),n(_,1,_),n(_,3,_)]  

I have wrote a comparator

cheaper(n(_,C1,_),n(_,C2,_)) :-
        C1>C2.  

How do I use this with predsort. I wrote a sorting algorithm using bubble sort, but I have very large lists so it very slow.

Is it possible to do

predsort(cheaper, [n(_,2,_),n(_,1,_),n(_,3,_)] , X).

Thank you :)

like image 222
user1724416 Avatar asked Dec 16 '22 13:12

user1724416


2 Answers

Try this :

cheaper(>, n(_,C1,_),n(_,C2,_)) :-
        C1>C2.

cheaper(<, n(_,C1,_),n(_,C2,_)) :-
        C1<C2.

cheaper(=, n(_,C1,_),n(_,C2,_)) :-
        C1=C2.

Be aware that predsort works like sort, there are no doubles ! If you want to keep doubles, try

cheaper(>, n(_,C1,_),n(_,C2,_)) :-
        C1>C2.

cheaper(<, n(_,C1,_),n(_,C2,_)) :-
        C1=<C2.
like image 166
joel76 Avatar answered Jan 28 '23 05:01

joel76


Joel has shown the basic case (+1), but to get better performance, avoid repeating the test:

cheaper(R, n(_,C1,_),n(_,C2,_)) :-
        C1>C2 -> R = > ; R = < .

edit

Now SWI-Prolog has another builtin sort/4, that for simple cases avoids the penalties related to calls of user defined predicates:

?- sort(2,@=<,[n(_,2,_),n(_,1,_),n(_,3,_)],S).
S = [n(_2578, 1, _2582), n(_2564, 2, _2568), n(_2592, 3, _2596)].
like image 44
CapelliC Avatar answered Jan 28 '23 03:01

CapelliC