Сортировать список по второму атому в функторе

Question

У меня есть этот список в прологе:

List = [functor(a,1),functor(n,7),functor(l,9),functor(k,0)]

и я хочу отсортировать его по номеру в функторе вместо буквы. Я имею в виду, если я делаю sort(L,L1)я получу

L1 = [functor(a,1),functor(k,0),functor(l,9),functor(n,7)]

но я хочу, чтобы это было похоже

L1 = [functor(k,0),functor(a,1),functor(n,7),functor(l,9)]

есть ли способ сделать это (а не просто воссоздать его и поставить номер первым)

Answer 1

Чтобы "воссоздать" список (вид):

?- List = [functor(a,1),functor(n,7),functor(l,9),functor(k,0)],
    map_list_to_pairs(arg(2), List, Pairs),
    keysort(Pairs, Sorted_pairs),
    pairs_values(Sorted_pairs, Sorted).
Pairs = [1-functor(a, 1), 7-functor(n, 7), 9-functor(l, 9), 0-functor(k, 0)],
Sorted = [functor(k, 0), functor(a, 1), functor(n, 7), functor(l, 9)].

Смотрите здесь. Это, вероятно, самый "идиоматический" способ сделать это, учитывая, что ваша реализация имеет library(pairs), Если этого не произойдет, то используемые здесь предикаты почти тривиальны: см. Исходный код библиотеки.

Если вы используете predsortсм. вопрос, связанный также в комментарии. Вы можете определить предикат помощника, например:

compare_2(Order, A, B) :-
    arg(2, A, A2),
    arg(2, B, B2),
    compare(Order, A2-A, B2-B).

(исправление @false)

Это будет сортировать по второму аргументу первым, а если они равны, по всему члену.

?- List = [f(a,1),f(n,0),f(l,9),f(k,0)],
predsort(compare_2, List, Sorted).
List = [f(a, 1), f(n, 0), f(l, 9), f(k, 0)],
Sorted = [f(k, 0), f(n, 0), f(a, 1), f(l, 9)].

Другими словами, это не "стабильный вид". Так что на самом деле, лучше использовать keysort подход.

Обратите внимание, что эта версия compare_2 будет по-прежнему удалять все, кроме первого появления идентичных терминов, потому что это то, что predsort делает:

?- List = [f(a,1),f(n,0),f(l,9),f(n,0)],
predsort(compare_2, List, Sorted).
List = [f(a, 1), f(n, 0), f(l, 9), f(n, 0)],
Sorted = [f(n, 0), f(a, 1), f(l, 9)].

Вы можете "обмануть" его, определив, что два элемента, которые эквивалентны (но не равны), уже отсортированы:

compare_2_stable(Order, A, B) :-
    arg(2, A, A2),
    arg(2, B, B2),
    compare(Order0, A2, B2),
    (   Order0 == (=)
    ->  Order = (<)
    ;   Order = Order0
    ).

?- List = [f(a,1),f(n,0),f(l,9),f(k,0)],
predsort(compare_2_stable, List, Sorted).
List = [f(a, 1), f(n, 0), f(l, 9), f(k, 0)],
Sorted = [f(n, 0), f(k, 0), f(a, 1), f(l, 9)].

?- List = [f(a,1),f(n,0),f(l,9),f(n,0)],
predsort(compare_2_stable, List, Sorted).
List = [f(a, 1), f(n, 0), f(l, 9), f(n, 0)],
Sorted = [f(n, 0), f(n, 0), f(a, 1), f(l, 9)].

Обратите внимание, что я точно не знаю, сохранит ли это исходный порядок эквивалентных элементов (элементов с "равными" вторыми членами). Это делает это в данный момент, для этого примера. Это будет иметь место только в том случае, если predsort сохраняет элементы в их первоначальном порядке, когда передает их в предикат сравнения, и это может зависеть от реализации (??).

РЕДАКТИРОВАТЬ: посмотрев на исходный код predsort/3 в SWI-Prolog, да, в SWI-Prolog, при текущей реализации последнее решение даст точно такое же решение, как и при использовании keysort/2, Тем не менее, вы должны предпочесть keysort/2 если у вас нет практической причины не делать этого, и вы готовы пожертвовать переносимостью.