Re: How to sort list of sublists as per key/keys of sublist?

On 10 Jun 2009, at 7:25 pm, Levan Cheishvili wrote:

> I have the following structure:
>
> object('obj1', [id='12', color='blue']).
> object('obj4', [id='13', color='red', weight=120]).
> object('obj21', [id='15 a', color='yellow', weight=1000, price=23]).
> object('obj21', [id='16 a', color='blue', weight=200, price=230]).

I assume that that's a table of facts, so

:- type eq ---> =(atom,any).
:- pred object(atom, list(eq)).

The first thing that strikes me is that the Prolog convention for
a list of key-value pairs has been a list of Key - Value terms
since about 1979, that's 30 years.  There is a standard predicate
called keysort/2 for sorting such lists.  So why are you using
(=)/2 for your pairs instead of (-)/2?

[It's not that (-)/2 is a specially brilliant choice, although since
it is very often used with collections of pairs that are _not_ finite
maps, it's definitely better than (=)/2.  The point is just that it
is the _better-supported_ choice.]

How come you have two facts for obj21?

> I have a predicate which finds all objects with particular key, e.g.  
> objects with color='blue'.

The second thing that strikes me is that what you really have
seems to be a ternary relation,

oav(obj1, id,     12). % Object Attribute Value
oav(obj1, colour, blue).
oav(obj4, id,     13).
oav(obj4, colour, red).
oav(obj4, weight, 120).

Or possibly a collection of binary relations

id(obj1, 12).
id(obj4, 13).

colour(obj1, blue).
colour(obj4, red).

weight(obj4, 120).

All things considered, I think the binary relations are the way I'd
do it.  We can recover the other views if we really have to:

oav(Obj, id,     X) :- id(Obj, X).
oav(Obj, colour, X) :- colour(Obj, X).
oav(Obj, weight, X) :- weight(Obj, X).
oav(Obj, price,  X) :- price(Obj, X).

object(Obj, Attrs0) :-
     ( id(Obj,     I) -> Attrs0 = [id    =I|Attrs1] ; Attrs1 = Attrs0 ),
     ( colour(Obj, C) -> Attrs1 = [colour=C|Attrs2] ; Attrs2 = Attrs1 ),
     ( weight(Obj, W) -> Attrs2 = [weight=W|Attrs3] ; Attrs3 = Attrs2 ),
     ( price(Obj,  P) -> Attrs3 = [price =P|Attrs4] ; Attrs4 = Attrs3 ),
     Attrs4 = [].

If you want to find all the objects that are blue,

        setof(Obj, colour(Obj, blue), Blue_Objs)
or even
        findall(Obj, colour(Obj, blue), Blue_Objs)

is a lot easier than

        setof(Obj, ( object(Obj, Attrs), member(colour=blue, Attrs) ),
              Blue_Objs)

> My question is:
> How to write a sorting predicate which will sort objects within a  
> resulting list by one of one or many  keys(id or/and price, etc...)

There are several ways to do it.
One way is to exploit the fact that keysort is stable.
So sort by the least significant key first,
then the second least significant key,
...
and finally sort by the most significant key.

To sort a list by a particular key, simply take a list whose
elements are X and make a list whose elements are Key-X, and
sort that.  If you want to sort in decreasing order, just
reverse the result.

If you want ascending order for everything (except possibly
numbers, which you can negate), you can simply build
one super-key containing all the others.

For example, suppose you want to find all the blue objects
and sort them by decreasing price and (within the same price
level) increasing id.

     setof( key(Minus_Price,Id) - Object
          , ( colour(Object, blue),
              price(Object, Price), Minus_Price is -Price,
              id(Object, Id)
            )
          , Pairs),
     pairs_values(Pairs, Objects)

where pairs_values/2 is described in http://www.cs.otago.ac.nz/staffpriv/ok/pllib.htm

That draft library specification also calls for
sort/3 and msort/3.  There is a file which was written
for that but never included, because there seemed to be
very little interest in a standard library for Prolog.
I've attached it.  It's called msort.pl, and I've deleted
msort/2 from it because SWI Prolog already has msort/2.

With this, you would write a 3-way comparison predicate.
Using the binary relations version of your data,
you'd write

price_and_id_compare(R, Obj1, Obj2) :-
     price(Obj1, Price1),
     price(Obj2, Price2),
     compare(R1, Price2, Price1),  % note argument order!
     (   R1 == (=) ->
        id(Obj1, Id1),
        id(Obj2, Id2),
        compare(R, Id1, Id2)
     ;/* prices differ */
        R = R1
     ).

Then given a list of objects you could do

     msort(price_and_id_compare, Objects, Sorted_Objects)

if you want to keep duplicates, or sort/3 to discard them.


[msort.pl]

---

:- module(msort, [
    msort/3, % accept a comparison predicate, keep duplicates
    sort/3, % accept a comparison predicate, discard duplicates
    merge/4, % combine sorted lists keeping duplicates
    union/4, % combine sorted lists discarding duplicates
    key_compare/3, % so msort can do keysort.
    key_compare/4, % generalisation of key_compare/3,
    reverse_compare/3, % compare/3 with last two arguments swapped.
    reverse_key_compare/3,
    reverse_key_compare/4
]). % "duplicates" = "things that compare equal".

:- meta_predicate
    msort(3, +, ?), sort(3, +, ?),
    msort(+, +, -, -, 3), sort(+, +, -, -, 3),
    merge(3, +, +, ?), union(3, +, +, ?),
    merge_0(+, +, -, 3), union_0(+, +, -, 3),
    merge_1(+, +, -, 3, +), union_1(+, +, +, -, 3),
    merge_2(+, +, -, 3, +), union_2(+, +, +, +, +, -, 3),
    merge_12(+, +, -, 3, +, +, +).

/*  The plain predicates can be recovered by passing compare/3:

    msort(L, S)      :- msort(compare, L, S).
    sort( L, S)      :- sort( compare, L, S).
    merge(L1, L1, M) :- merge(compare, L1, L2, M).
ord_union(S1, S2, U) :- union(compare, S1, S2, U).
*/

/* pred
        msort(+Cmp, +List, ?List),
            msort(+integer, +List, -List, -List, +Cmp),
        sort( +Cmp, +List, ?List),
            sort( +integer, +List, -List, -List, +Cmp),
                sort2(+order, +T, +T, -List),
        merge(+Cmp, +List, +List, ?List),
            merge_0(+List, +List, -List, +Cmp),
                merge_1(+List, +List, -List, +Cmp, +T),
                merge_2(+List, +List, -List, +Cmp, +T),
                merge_12(+order, +List, -List, +Cmp, +T, +List, +T),
        union(+Cmp, +List, +List, ?List),
            union_0(+List, +List, -List, +Cmp),
                union_1(+List, +T, +List, -List, +Cmp),
                    union_2(+order, +T, +List, +T, +List, -List, +Cmp),
        key_compare(-order, +pair(X,Y), +pair(X,Y)),
        key_compare(+integer, -order, T, T),
        reverse_compare(-order, +T, +T),
        reverse_key_compare(-order, +pair(X,Y), +pair(X,Y)),
        reverse_key_compare(+integer, -order, +pair(X,Y), +pair(X,Y))
   where
        Cmp = void(-order, +T, +T),
        List = list(T).
*/


msort(C, List, Sorted) :-
    length(List, N),
    (   N >= 2 -> msort(N, List, _, S, C), Sorted = S
    ;   Sorted = List
    ).

msort(1, [X|Xs],   Xs, [X], _) :- !.
msort(2, [X,Y|Xs], Xs, S,   C) :- !,
    call(C, R, X, Y),
    (   R = (>) -> S = [Y,X]
    ;              S = [X,Y]
    ).
msort(N, Xs0, Xs, S, C) :-
    A is N // 2, Z is N - A,
    msort(A, Xs0, Xs1, S1, C),
    msort(Z, Xs1, Xs,  S2, C),
    merge_0(S1, S2, S, C).


merge(C, S1, S2, L) :-
    merge_0(S1, S2, T, C),
    L = T.

merge_0([],     L,  L, _).
merge_0([X|Xs], Ys, L, C) :-
    merge_1(Ys, Xs, L, C, X).

%   merge_1(Ys, Xs, L, C, X) -- list 1 has been taken apart

merge_1([],     Xs, [X|Xs], _, X).
merge_1([Y|Ys], Xs,   L,    C, X) :-
    call(C, R, X, Y),
    merge_12(R, Xs, L, C, X, Ys, Y).

merge_12(>, Xs, [Y|L], C, X, Ys, Y) :-
    merge_1(Ys, Xs, L, C, X).
merge_12(<, Xs, [X|L], C, X, Ys, Y) :-
    merge_2(Xs, Ys, L, C, Y).
merge_12(=, Xs, [X|L], C, X, Ys, Y) :-
    merge_2(Xs, Ys, L, C, Y).

%   merge_2(Xs, Ys, L, C, Y) -- list 2 has been taken apart

merge_2([],     Ys, [Y|Ys], _, Y).
merge_2([X|Xs], Ys,   L,    C, Y) :-
    call(C, R, X, Y),
    merge_12(R, Xs, L, C, X, Ys, Y).

sort(C, List, Sorted) :-
    length(List, N),
    (   N >= 2 -> sort(N, List, _, S, C), Sorted = S
    ;   Sorted = List
    ).

sort(1, [X|Xs],   Xs, [X], _) :- !.
sort(2, [X,Y|Xs], Xs, S,   C) :- !,
    call(C, R, X, Y),
    sort2(R, X, Y, S).
sort(N, Xs0, Xs, S, C) :-
    A is N // 2, Z is N - A,
    sort(A, Xs0, Xs1, S1, C),
    sort(Z, Xs1, Xs,  S2, C),
    union_0(S1, S2, S, C).


sort2(<, X, Y, [X,Y]).
sort2(>, X, Y, [Y,X]).
sort2(=, X, _, [X]).

union(C, S1, S2, U) :-
    union_0(S1, S2, S, C),
    U = S.

union_0([],      U,  U, _).
union_0([H1|T1], S2, U, C) :-
    union_1(S2, H1, T1, U, C).

union_1([], H1, T1, [H1|T1], _).
union_1([H2|T2], H1, T1, U, C) :-
    call(C, R, H1, H2),
    union_2(R, H1, T1, H2, T2, U, C).

union_2(<, H1, T1, H2, T2, [H1|U], C) :-
    union_1(T1, H2, T2, U, C).
union_2(>, H1, T1, H2, T2, [H2|U], C) :-
    union_1(T2, H1, T1, U, C).
union_2(=, H1, T1, _,  T2, [H1|U], C) :-
    union_0(T1, T2, U, C).


%   Utility predicate to sort in reverse without reversing the
%   list.  Since this treats as equivalent only terms that are
%   identical,
% msort(reverse_compare, L, S) <=> msort(compare, L, T), reverse(T, S)
% sort( reverse_compare, L, S) <=> sort( compare, L, T), reverse(T, S).
%   For comparisons with other notions of equality, this is NOT true.
%   For example, the corresponding equivalences involving
%   key_compare/3 and reverse_key_compare/3 do NOT hold.

reverse_compare(R, X, Y) :-
    compare(R, Y, X).

key_compare(R, X-_, Y-_) :-
    compare(R, X, Y).

key_compare(N, R, A, B) :-
    arg(N, A, X),
    arg(N, B, Y),
    compare(R, X, Y).

reverse_key_compare(R, X-_, Y-_) :-
    compare(R, Y, X).

reverse_key_compare(N, R, A, B) :-
    arg(N, A, X),
    arg(N, B, Y),
    compare(R, Y, X).

---

>
> Thanks!