Sorting predicates in PROLOG

Help!
1

I’m using: SWI-Prolog version 8.4.3 for x64-win64

I have some predicates

p1( 301, 1, 2 ).
p2( 201, 5, 2 ).
p3( 501, 1, 5 ).
p4( 401, 1, 4 ).

I want to sort them in numerical order depending on the 3rd clause(Ascending order), if they have the same value I sort them depending on the 2nd clause(descending order)

p2( 201, 5, 2 ).
p1( 301, 1, 2 ).
p4( 401, 1, 4 ).
p3( 501, 1, 5 ).

I am new to prolog, is there any function to sort predicates ?

Do i have to write a predicate that does a query (say, via call or findall) and then calls sort on it’s output ?

Thanks for your help

2

This is cross posted on StackOverflow

Yes.

order_by/2

Note: order_by/2 will not work with your predicates because they have different names, i.e. p1, p2, …
They need to have the same functor for order_by/2 to work, e.g.

p( 201, 5, 2 ).
p( 301, 1, 2 ).
p( 401, 1, 4 ).
p( 501, 1, 5 ).
1 Like
3

I assume by “3rd clause” you mean “3rd argument” or “3rd parameter”, and that all the clauses should have the same name (“p”).

If you want to get the predicates as a list, you can do something like this:

p( 301, 1, 2 ).
p( 201, 5, 2 ).
p( 501, 1, 5 ).
p( 401, 1, 4 ).

key_value(k(C,NegB), p(A,B,C)) :-
    p(A, B, C),
    NegB is -B.

p_sort(PairsUnsorted, List) :-
    bagof(K-P, key_value(K, P), PairsUnsorted),
    keysort(PairsUnsorted, PairsSorted),
    pairs_values(PairsSorted, List).

?- p_sort(Unsorted, Sorted), maplist(writeln, Sorted).
p(201,5,2)
p(301,1,2)
p(401,1,4)
p(501,1,5)

Unsorted = [k(2,-1)-p(301,1,2),k(2,-5)-p(201,5,2),k(5,-1)-p(501,1,5),k(4,-1)-p(401,1,4)],
Sorted = [p(201,5,2),p(301,1,2),p(401,1,4),p(501,1,5)].
5

Do you mean that there are duplicate results? E.g., if the definition of p/3 is

p( 301, 1, 2 ).
p( 201, 5, 2 ).
p( 501, 1, 5 ).
p( 401, 1, 4 ).
p( 201, 5, 2 ). % duplicate

There are a few ways of removing duplicates. One of the easiest is to use setof/3 instead of bagof/3. In other situations distinct/1 can do what you want. And there are other library predicates, such as list_to_set/2 and list_to_ord_set/2.

Note that Prolog has 3 sort predicates:
sort/2 - removes duplicates (setof/3 uses this)
msort/2 does not remove duplicates
keysort/2 does not remove duplicates

1 Like
6

Thank you so much the function works perfectly.
I want to change the name of predicates from p to patient.
But i’m getting wrong results (redundant results):
I changed the p in the predicates and in the functions :


patient( 301, 1, 2 ).
patient( 201, 5, 2 ).
patient( 501, 1, 5 ).
patient( 401, 1, 4 ).

key_value(k(C,NegB), patient(A,B,C)) :-
    patient(A, B, C),
    NegB is -B.

p_sort(PairsUnsorted, List) :-
    bagof(K-P, key_value(K, P), PairsUnsorted),
    keysort(PairsUnsorted, PairsSorted),
    pairs_values(PairsSorted, List).

Am I missing anything in the function ?

Thanks

EDIT :

I think it’s because i was adding
:- dynamic patient/3., when i removed it, it worked fine.

7

I don’t see why adding the dynamic directive would do anything. Perhaps if you show a full session, and also the file(s) that you used, I could explain why you’re getting “redundant” results.

8

You were right.
I reloaded the file, and everything works fine, the dynamic was not the problem

9

Can also use order_by.

1 Like
10

how about displaying the result like this :

201 5 2
301 1 2
401 1 4
501 1 5

What can i add to get this format ?

11

Use format/2.

12

If you use sort/4 you only need:

?- findall(p(X,Y,Z), p(X,Y,Z), Ps), sort(3, @=<, Ps, Result).
Result = [p(301, 1, 2), p(201, 5, 2), p(401, 1, 4), p(501, 1, 5)].

If you want to format it maybe forall/2 and order_by/2?

?- forall(order_by([asc(Z)], p(X,Y,Z)), format("~w ~w ~w~n", [X,Y,Z])).
301 1 2
201 5 2
401 1 4
501 1 5
true.
13

How can i split the Sorted list into list of lists depending on the 3rd argument of p predicate.
I mean getting something like :

Sorted = [ [p(201,5,2),p(301,1,2) ] , [p(401,1,4)] , [p(501,1,5)] ].
14

How about this ? Sort by 3rd arguments with sort/3, then do grouping the sorted list by the 3rd arguments. Also the following seems to work, though I prefer the former.

% ?- L = [p(2,2,1), p(1,1,1), p(3,3,2)], findall(I, (member(A, L), arg(3, A, I)), Is), sort(Is, Js),
% findall(S, (member(J, Js), findall(P, (member(P, L), arg(3, P, J)), S)), T).
%@ L = [p(2, 2, 1), p(1, 1, 1), p(3, 3, 2)],
%@ Is = [1, 1, 2],
%@ Js = [1, 2],
%@ T = [[p(2, 2, 1), p(1, 1, 1)], [p(3, 3, 2)]].
15

An old school approach, ignoring the facilities of library(solution_sequences):

group_lists(L) :-
    setof(C,X^Y^p(X,Y,C),Cs),
    findall(S,(member(C,Cs),setof(p(A,B,C),p(A,B,C),S)),L).

edit

Just to showcase an application of distinct/2

group_lists(Ls) :-
    findall(L,(
      distinct(C,p(_,_,C)),
      setof(p(A,B,C),p(A,B,C),L)
    ),Ls).

Could be interesting to benchmark these 2 approaches.

edit

My benchmark shows the first approach is more efficient, even if the second one doesn’t sort the primary sequence… on 1.000.000 elements I get

?- benchmark.
% 2,000,106 inferences, 1.000 CPU in 1.062 seconds (94% CPU, 2000106 Lips)
% 10,000,113 inferences, 1.469 CPU in 1.496 seconds (98% CPU, 6808588 Lips)
16

This is perfect. My solution ignored that p/3 is a predicate, not a term.

17

I don’t really like the findall/setof/… solutions for two reasons. First of all, if something unexpectedly fails you typically loose part of the answer without any feedback and second because it involves copying. Copying ground terms is fine (just costs memory and time), but for non-ground terms it already gets harder and for terms with constraints it quickly leads to incorrect results. I’d use this instead:

group_by_arg3(Terms, Grouped) :-
    map_list_to_pairs(arg(3), Terms, Keyed),
    keysort(Keyed, Sorted),
    group_pairs_by_key(Sorted, KeyGrouped),
    pairs_values(KeyGrouped, Grouped).

See SWISH -- SWI-Prolog for SHaring

That is the solution using library predicates. Alternatively, use sort/4 to sort the list on the 3th argument and do the splitting by hand. That is faster, but requires more writing.

At a more general level, Prolog programs handling this type of data as lists and doing such operations on them smells dubious. It could be fine. It could also be you are not using Prolog as a logic programming language but merely as an imperative data processing language. Prolog can do that, but the advantage compared to modern imperative languages is small. To judge though, one needs a much more complete picture about the problem you are trying to solve.

2 Likes
18

Assuming findall(X, cond(X), S) means mathematically that S = { X | cond(X) }, if cond(X) is constraint-free, the S should be clear. However cond(X) contains constraints then as
S must inherit the suspended constraints. I feel such S like a monster which is almost impossible to be controled completely. So my use of “complete” should have been used for constraint-free condition cond(X). I could agree with most of Jan’s comment, but I like setof/3, findall/3 and become to use more frequently. BTW, I have not custom to use constraints.

19

Implemented as:

test_sort_group(Group) :-
    Patients = [patient(204,4,2),patient(203,3,2),patient(304,8,3),patient(303,7,3),patient(404,12,4),patient(403,11,4),patient(504,16,5),patient(503,15,5),patient(1,1,1),patient(506,6,5)],
    group_list_by_arg(3, Patients, Group).


group_list_by_arg(Arg, Lst, Group) :-
    % Keeping duplicates
    sort(Arg, @=<, Lst, [H|T]),
    group_list_by_arg_main_(T, Arg, H, Group).

group_list_by_arg_main_(T, Arg, H, Group) :-
    arg(Arg, H, ArgVal),
    Upto = [H|Upto0],
    group_list_by_arg_loop_(T, Arg, ArgVal, Upto0, Rem),
    group_list_by_arg_rem_(Rem, Arg, Upto, Group).

% Reached end of groups
group_list_by_arg_rem_([], _, G, G).
group_list_by_arg_rem_([_|_], _, G, G).
group_list_by_arg_rem_([H|T], Arg, _Upto, Group) :-
    % Assemble next group
    group_list_by_arg_main_(T, Arg, H, Group).

% Reached end of sorted list
group_list_by_arg_loop_([], _, _, [], []).
group_list_by_arg_loop_([H|T], Arg, ArgVal, Group, Rem) :-
    arg(Arg, H, ArgVal), !,
    % Add element to current group
    Group = [H|Group0],
    group_list_by_arg_loop_(T, Arg, ArgVal, Group0, Rem).
% Finished this group, but there may be other elements
group_list_by_arg_loop_([H|T], _Arg, _ArgVal, [], [H|T]).

?- time(bagof(G, test_sort_group(G), Gs)).
% 49 inferences, 0.000 CPU in 0.000 seconds (94% CPU, 599807 Lips)
Gs = [[patient(1,1,1)],[patient(204,4,2),patient(203,3,2)],[patient(304,8,3),patient(303,7,3)],[patient(404,12,4),patient(403,11,4)],[patient(504,16,5),patient(503,15,5),patient(506,6,5)]].
1 Like
20

I try to create an emergency system to find people on time and those late.
so my list now looks like:

[ [patient(204,4,2),patient(203,3,2)] , [patient(303,7,3),patient(302,6,3)] , [patient(404,12,4) ,patient(403,11,4)] , [patient(504,16,5),patient(503,15,5)] ]

I want for each list to find those on time using the following function:

(consultation time) * (index of patient) + (2nd argument of each patient)

consultation time is constant:
example :
consultTime(15)

[ [4 , 18] , [37, 51] , [72, 86] , [106, 120] ]

the problem is with the indices how can i preserve the same index as with a normal list i.e.:

[ [0, 1], [2, 3], [4, 5] ]

21

The more logic based solution is to have a database of patients, e.g.

patient(204, 4, 2).
patient(203, 3, 2).

and next define e.g.

patient_on_time(Patient) :-
    ...

patient_late(Patient) :-
    patient(Patient),
    \+ patient_on_time(Patient).

etc. That way you can define complex rules on patients you want to retrieve that are easy to read. In the end, if you need the set of patients that satisfy some condition you use setof/3 or you use one of the other aggregation predicates to do things such as counting, getting averages, (sorted) sets of solutions, etc.

2 Likes