How to sort by letters *and* numbers in prolog?

Question

I have a list in Prolog like the following:

[(b,y,3),(p,z,1),(p,y,3),(b,y,2),(p,z,2),(p,x,3),...]

where the first element of the first tuple is in [b,p], the second is in [x,y,z], and the third is in [1,2,3,4,5,6,7].

How do I sort this list of tuples so that the above sample of list becomes:

[(b,y,2),(b,y,3),(p,x,3),(p,y,3),(p,z,1),(p,z,2),...]

that is, b comes before p, x before y and z and the numbers are sorted.

Answer 1

If you want to sort preserving duplicate entries in SICStus and many other Prologs use keysort/2:

msort(Keys, KeysS) :-
   keys_pairs(Keys, Pairs), % pairs_keys(Pairs, Keys)
   keysort(Pairs, PairsS),
   pairs_keys(PairsS, KeysS).

keys_pairs([], []).
keys_pairs([K|Ks], [K-_|Ps]) :-
   keys_pairs(Ks, Ps).

pairs_keys([], []).
pairs_keys([K-_|Ps],[K|Ks]) :-
   pairs_keys(Ps, Ks).

SICStus and many other Prologs need both keys_pairs/2 and pairs_keys/2 for an efficient mapping.