CODEWITHSUNDEEP
listsortinglambdaprolog
CyberShot
CyberShot

Reputation: 2335

Prolog sorting list using sort method

sort([ [30,100], [10,11] ], X).

gets

X = [[10,11],[30,100]]

How can I sort only by the first index of each sublist?

i.e

X = [[10,100], [30, 11]]

Thanks

Upvotes: 1

Views: 3975

Answers (3)

Cling
Cling

Reputation: 499

The below is my untested code.. there may be one/two cosmetic errors... The input list is split into two based on the head value on the list and the resulted two lists are recursively processed to finally result the sorted output.

sort(Input,Output):-sort(Input,[],Output).

sort([],SortedOut,SortedOut).
sort([[Index1,Index2]|Tail],SortedBig,Out):-
    split(Tail,[Index1,Index2],LessList,BigList),
    !,sort(BigList,SortedBig,NewSort),
    sort(LessList,[[Index1,Index2]|NewSort],Out).

split([],[_D],[],[]).
split([[Index1,Index2]|Rem],[Index21,Index22],[[Index1,Index1]|L1],L2):-
    Index1<Index21,
    !,split(Rem,[Index21,Index22],L1,L2).
split([[Index1,Index2]|Rem],[Index21,Index22],L1,[[Index1,Index1]|L2]):-
    !,split(Rem,[Index21,Index22],L1,L2).

Try this and let me know...

Upvotes: 0

m09
m09

Reputation: 7493

@chac(+1 btw): there's no need of lambda to one-line this (in swi at least!):

sortfirst(L, Res) :-
    maplist(selectchk, X, L, R),
    msort(X, XS),
    maplist(selectchk, XS, Res, R).

but lambda versions or your first version are less tricky and more readable I think!

Upvotes: 2

CapelliC
CapelliC

Reputation: 60004

The simpler way should be perusing the available builtins. Then take the first element from each sublist, sort them, and replace in the original:

sortfirst(L, S) :-
    maplist(get_first, L, A),
    msort(A, B),
    maplist(set_first, L, B, S).

get_first([E|_], E).
set_first([_|R], E, [E|R]).

edit: note that msort is required, to avoid losing duplicates.

test:

?- sortfirst([ [30,100], [10,11] ], X).
X = [[10, 100], [30, 11]].

get/set first are just needed to adjust the arguments from maplist: if we use lambda, we can write a true 'one liner' procedure:

:- [lambda].

sortfirst_lambda(L, S) :-
    maplist(\X^Y^(X = [E|_], Y = E), L, A),
    msort(A, B),
    maplist(\X^Y^Z^(X = [_|R], Y = E, Z = [E|R]), L, B, S).

Simple identities can simplify a little that expressions:

sortfirst_lambda(L, S) :-
    maplist(\X^Y^(X = [Y|_]), L, A),
    msort(A, B),
    maplist(\X^Y^Z^(X = [_|R], Z = [Y|R]), L, B, S).

edit: or still more simplified:

sortfirst_lambda(L, S) :-
    maplist(\[Y|_]^Y^true, L, A),
    msort(A, B),
    maplist(\[_|R]^Y^[Y|R]^true, L, B, S).

Here you can see that, as in the original get/set first, just the unification of arguments is needed.

Thus lambda it's syntactically convenient, but has its cost:

?- randomlists(100000, 3, -30,+30, L),
 time(sortfirst(L,A)),
 time(sortfirst_lambda(L,B)),
 assertion(A=B).

% 400,012 inferences, 0,482 CPU in 0,483 seconds (100% CPU, 830072 Lips)
% 1,700,012 inferences, 1,717 CPU in 1,721 seconds (100% CPU, 990302 Lips)
L = [[-8, -13, 11], [-13, -27, -29], [5, 10, -24], [-8, -7, -6], [3, -24, -9], [-13, -20, -24], [7, 27|...], [-5|...], [...|...]|...],
A = B, B = [[-30, -13, 11], [-30, -27, -29], [-30, 10, -24], [-30, -7, -6], [-30, -24, -9], [-30, -20, -24], [-30, 27|...], [-30|...], [...|...]|...].

here are the service predicates to build sized test data:

randomlist(Length, Low, High, List) :-
    findall(E, (between(1, Length, _),
            random(Low, High, E)), List).

randomlists(Length1, Length2, Low, High, ListOfLists) :-
    findall(E, (between(1, Length1, _),
            randomlist(Length2, Low, High, E)), ListOfLists).

Upvotes: 2

Related Questions