Возможное поведение `predsort/3`

Question

Это продолжение ответа на вопрос о сортировке определенного аргумента термина без создания нового списка для keysort (если я правильно понял исходный вопрос).

Скажи, что мы хотели predsort/3 вести себя так же, как sort/2Если я правильно понимаю, это будет означать, называя это как:

?- predsort(compare, List, Sorted).

Теперь скажите, что мы хотели использовать predsort/3 сортировать как реализовано msort/2 (см. также этот вопрос). Один из способов сделать это - определить предикат сравнения. Pred(-Delta, +A, +B) это не объединяет Delta с = когда элементы на самом деле равны:

mcompare(Delta, A, B) :-
    compare(Delta0, A, B),
    (   Delta0 == (=)
    ->  Delta = (<)
    ;   Delta = Delta0
    ).

?- predsort(mcompare, List, Sorted).

Вопрос: действительно ли это просто сортировка без удаления дубликатов, как msort/2 делает? Кажется, так и должно быть.

Двигаясь дальше: скажем, мы хотели отсортировать термины с arity> n в стандартном порядке n-го аргумента в термине. Чистый способ сделать это будет:

sort_argn(N, List, Sorted) :-
    map_list_to_pairs(arg(N), List, Pairs),
    keysort(Pairs, Sorted_pairs),
    pairs_values(Sorted_pairs, Sorted).

Если бы мы хотели использовать predsort/3 чтобы достичь того же эффекта, мы можем попытаться использовать предикат сравнения следующим образом:

compare_argn(N, Delta, A, B) :-
    arg(N, A, AN),
    arg(N, B, BN),
    compare(Delta, AN-A, BN-B).

И отсортировать по второму аргументу:

?- predsort(compare_argn(2), List, Sorted).

Однако это не то же самое, что sort_argn/3 выше, что использует keysort/2, Он удалит дубликаты и упорядочит составные термины в соответствии со стандартным порядком исходного полного члена, если вторые аргументы двух терминов окажутся равными:

?- predsort(compare_argn(2), [f(b,2), f(a,1), f(a,1), f(a,2)], Sorted).
Sorted = [f(a, 1), f(a, 2), f(b, 2)].

?- sort_argn(2, [f(b,2), f(a,1), f(a,1), f(a,2)], Sorted).
Sorted = [f(a, 1), f(a, 1), f(b, 2), f(a, 2)].

Делая предположение, что для каждой пары A а также B передано в предикат сравнения Pred(Delta, A, B), A приходит раньше B в первоначальном списке. Можем ли мы определить сравнение:

compare_argn_stable(N, Delta, A, B) :-
    arg(N, A, AN),
    arg(N, B, BN),
    compare(Delta0, AN, BN),
    (   Delta0 == (=)
    ->  Delta = (<)
    ;   Delta = Delta0
    ).

На данный момент, если и только если любые два элемента A а также B всегда передаются предикату сравнения в том же порядке, в котором они были в исходном списке, это должно вести себя идентично sort_argn/3 выше:

?- predsort(compare_argn_stable(N), List, Sorted).

Теперь, конечно, важно, чтобы compare_argn_stable/4 унифицирует Delta с < когда два "ключа" равны. Кроме того, поведение зависит от реализации и только идентично keysort пример если predsort/3 сохраняет исходный порядок элементов при передаче их в предикат сравнения.

Вопрос Это правильно?

Вопрос: Существует ли какой-либо стандарт, охватывающий этот аспект? predsort/3?

Answer 1

Так как никто не ответил, и так как я совершенно уверен в этом сейчас:

Да, вы могли бы использовать predsort/3 подражать любому из других сортов. Вопрос описывает в некоторых деталях, как.

Однако: это плохая идея по нескольким причинам.

• "Стабильность" зависит от реализации predsort/3 (см. вопрос)
• predsort/3 сам по себе не является частью какого-либо стандарта (насколько я могу судить)
• Скорее всего, ваша реализация Prolog обеспечивает msort/2 или же keysort/2 это гораздо эффективнее, чем predsort/3

Могут быть редкие случаи, когда размер элементов списка намного больше, чем длина списка, который мы сортируем, и этот маленький танец:

list_to_keyval_pairs(List, Pairs), % defined by the user as necessary
keysort(Pairs, Sorted_pairs),
pairs_values(Sorted_pairs, Sorted)

( см. здесь) на самом деле дороже (медленнее), чем использование predsort(keycmp, List, Sorted), с keycmp/3 определяется пользователем. Даже тогда порядок результатов с эквивалентными ключами зависит не только от (пользовательского) определения keycmp/3, но и о реализации predsort/3,

Другими словами, "стабильный" вид с predsort/3 плохая идея