Subject: Re: [SWIPL] keysort

From: "Richard A. O'Keefe" <[email-masked]>
Date: Tue, 20 Feb 2001 11:33:53 +1300 (NZDT)

Cecilia Wong <[email-masked]> wrote:
	I intend to use the "keysort" predicate to sort a list according to =
	one of the arguments in the list.

Lists do not have "arguments", they have "elements".
When I was learning to drive, my mother often told me

  "Look where you're driving, or you'll drive where you're looking".

In the same way, as programmers, it is important that we say exactly
what we mean, or else we'll do what we say, not what we mean.
If one talks about "arguments" of a list, one will eventually try to
get at them using arg/3.

	For example, I have the list
	[[a,b,2], [a,c,3], [a,b,1], [b,a,5], [d,c,4], [f,r,6]].

I must say that the elements of this list strike me as EXTREMELY odd.
They are all the same length, and their elements are NOT all the same
type.  This is the hallmark of something that should not be a list.

Assuming for the sake of argument that they represent weighted edges in
a graph, a better representation (requiring less space to store it and
less time to process it) would be
	[edge(a,b,2), edge(a,c,3), edge(a,b,1),
	 edge(b,a,5), edge(d,c,4), edge(f,r,6)].
Whatever they represent, a compound term with a well-chosen word to label
it would be a better choice than a list.

	And I want the resultant list to be sorted like this:
	[[a,b,1], [a,b,2], [a,c,3], [d,c,4], [b,a,5], [f,r,6]],

That is, the key for comparison is to be the last ELEMENT of each list.

	Can this predicate help?
	
Yes, but not directly.

	I am really confused about the syntax of using keysort/2.

It is the same as the syntax of any other predicate.

	As the manual stated, "List is a list of Key-Value pairs
	(e.g. terms of the functor `-' with arity 2)".

Admittedly the English is rather poor there.  It should be "i.e.,"
(= "that is,") not "e.g." (= "for example,").  It should be

	List is a proper list whose elements are Key-Value pairs,
	that is, terms whose principal functor is (-)/2, whose
	first argument is the sorting key, and whose second argument
	is the satellite data to be carried along with the key.

	Can anyone give an example on how to use this predicate?
	
How about an example for your problem?

    last_sort(L0, L) :-
	last_keys(L0, L1),
	keysort(L1, L2),
	last_keys(L, L2).

    last_keys([], []) :- !.		% Green cut for inverse use
    last_keys([L|Ls], [K-L|KLs]) :-
	last(K, L),
	last_keys(Ls, KLs).

It is usual when you know you will be using keysort/2 to design your
data structure so that it has the Key-Value form from the outset; when
that is not convenient, you temporarily convert the list to that form,
sort, and then convert back.

In this particular case, if you want to stick with 3-element lists,
you could write

    triple_sort(L0, L) :-
        triple_keys(L0, L1),		% forward use
        keysort(L1, L2),
        triple_keys(L, L2).		% inverse use

    triple_keys([], []) :- !.		% Green cut for inverse use
    triple_keys([L|Ls], [K-L|KLs]) :-
	L = [_,_,K],
	triple_keys(Ls, KLs).

I have tested these last two predicates on your example,
and they give the desired result.