Пролог сортировка списка с использованием метода сортировки

Question

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

получает

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

Как сортировать только по первому индексу каждого подсписка?

1007 * т.е. *

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

Спасибо

Answer 1

Более простой способ - просматривать доступные встроенные функции. Затем возьмите первый элемент из каждого подсписка, отсортируйте их и замените в оригинале:

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 : обратите внимание, что требуется msort, чтобы избежать потери дубликатов.

тест:

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

get / set first просто необходимы для настройки аргументов из maplist: если мы используем lambda , мы можем написать настоящую процедуру 'one liner':

:- [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).

Простые тождества могут немного упростить выражения:

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 : или еще более упрощенно:

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

Здесь вы можете видеть, что, как и в оригинальном get / set, необходимо просто объединение аргументов.

Таким образом, лямбда синтаксически удобна, но имеет свою стоимость:

?- 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|...], [...|...]|...].

Вот предикаты службы для построения тестовых данных с размером:

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).

Answer 2

@ chac (+1 между прочим): нет необходимости в лямбде, чтобы в одну строку это (по крайней мере, на swi!):

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

но лямбда-версии или ваша первая версия менее хитры и более читабельны, я думаю!

Answer 3

Ниже приведен мой непроверенный код ... могут быть одна / две косметические ошибки ... Список ввода разбивается на два на основе значения заголовка в списке, и полученные два списка рекурсивно обрабатываются, чтобы в итоге получить отсортированный выход.

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).

Попробуйте и дайте мне знать ...