How to order a list of tuples in Swi-Prolog

1
votes

I have a list in swi-prolog like this:

[(5,4), (1,4), (3,12), (4,2), (5,4)]

I need to have the list organized by the second element of each "tuple", removing any repeated elements, so this list would look like this:

[(4,2), (1,4), (5,4), (3,12)]

Using the predicate sort/2, it does everything I want, except it organizes according the first element of each tuple, which I don't want.

How can I do it?

2
prologprolog-setof

2 Answers

1
votes

Inspired by http://kti.mff.cuni.cz/~bartak/prolog/sorting.html, I modified the pivot algorithm to match your needs. I tested on Sicstus Prolog and it worked.

:- use_module(library(lists)).

pivoting(_,[],[],[]).
pivoting((A,B),[(C,D)|T],[(C,D)|L],G):-D>B,pivoting((A,B),T,L,G).
pivoting((A,B),[(C,D)|T],[(C,D)|L],G):-D=B,C>A,pivoting((A,B),T,L,G).
pivoting((A,B),[(C,D)|T],L,[(C,D)|G]):-D<B,pivoting((A,B),T,L,G).
pivoting((A,B),[(C,D)|T],L,[(C,D)|G]):-D=B,C<A,pivoting((A,B),T,L,G).
pivoting((A,B),[(C,D)|T],L,G):-A=C,D=B,pivoting((A,B),T,L,G).

quick_sort(List,Sorted):-q_sort(List,[],Sorted).
q_sort([],Acc,Acc).
q_sort([H|T],Acc,Sorted):-
    pivoting(H,T,L1,L2),
    q_sort(L1,Acc,Sorted1),q_sort(L2,[H|Sorted1],Sorted).
1
votes

If you don't want to write your own sorting routine (your Prolog's sort is probably more optimized than yours would be), there might be implementation-specific predicates you can use with a comparison of your choice.

For example, SWI-Prolog has predsort/3 which takes a predicate to sort by. You can use it with a predicate that compares on the second element of a pair first:

compare_by_second(<, (A, B), (C, D)) :-
    (   B @< D
    ;   B == D,
        A @< C ).
compare_by_second(=, (A, B), (C, D)) :-
    A == C,
    B == D.
compare_by_second(>, (A, B), (C, D)) :-
    (   B @> D
    ;   B == D,
        A @> C ).

% ?- predsort(compare_by_second, [(5,4), (1,4), (3,12), (4,2), (5,4)], Sorted).
%@ Sorted = [ (4, 2), (1, 4), (5, 4), (3, 12)] ;
%@ false.