list - Posibles comportamientos de `predsort/3`

sorting prolog

Question

Este es un seguimiento de una respuesta a una pregunta sobre la clasificación de un argumento particular de un término, sin crear una nueva lista para un keysort (si entendí correctamente la pregunta original).

Digamos que queremos que predsort/3 comporte exactamente como sort/2 : si entiendo correctamente, esto significaría llamarlo así:

?- predsort(compare, List, Sorted).

Ahora diga que queríamos usar predsort/3 para clasificar como implementado por msort/2 (vea también esta pregunta ). Una forma de hacerlo sería definir un predicado de comparación Pred(-Delta, +A, +B) que no unifica Delta con = cuando los elementos son realmente iguales:

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

?- predsort(mcompare, List, Sorted).

Pregunta : ¿realmente eso simplemente ordena sin eliminar duplicados, como lo hace msort/2 ? Parece que debería.

Continuando: digamos que queríamos ordenar los términos con arity> n, en el orden estándar del enésimo argumento en el término. La forma limpia de hacerlo sería:

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

Si quisiéramos usar predsort/3 para lograr el mismo efecto, podríamos intentar usar un predicado de comparación de la siguiente manera:

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

Y para ordenar el segundo argumento:

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

Sin embargo, esto no es lo mismo que sort_argn/3 anterior que usa keysort/2 . Eliminará los duplicados y ordenará los términos compuestos de acuerdo con el orden estándar del término completo original si los segundos argumentos de dos términos son iguales:

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

Suponiendo que para cada par de A y B pasado al predicado de comparación Pred(Delta, A, B) , A aparece antes que B en la lista original. ¿Podemos definir una comparación?

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

En este punto, si y solo si dos elementos A y B siempre se pasan al predicado de comparación en el mismo orden en que estaban en la lista original, esto debería comportarse de manera idéntica a sort_argn/3 arriba:

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

Ahora, por supuesto, es importante que compare_argn_stable/4 unifique Delta con < cuando las dos "claves" son iguales. Además, el comportamiento depende de la implementación, y solo es idéntico al ejemplo predsort/3 iff predsort/3 mantiene el orden original de los elementos al pasarlos al predicado de comparación.

Pregunta: ¿Es eso correcto?

Pregunta: ¿Existe algún estándar que cubra este aspecto de predsort/3 ?

Answer 1

Dado que nadie ha respondido, y ya estoy bastante seguro de eso ahora:

Sí, podría usar predsort/3 para emular cualquiera de los otros géneros. La pregunta describe con algún detalle cómo.

Sin embargo : esta es una mala idea por varias razones.

• La "estabilidad" depende de la implementación de predsort/3 (ver la pregunta)
• El predsort/3 sí mismo no es parte de ningún estándar (por lo que puedo decir)
• Lo más probable es que su implementación de Prolog proporcione un msort/2 o keysort/2 que sea mucho más eficiente que predsort/3

Puede haber casos excepcionales en los que el tamaño de los elementos de la lista sea mucho mayor que la longitud de la lista que estamos ordenando, y este pequeño baile:

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

( ver aquí ) es en realidad más caro (más lento) que usar predsort(keycmp, List, Sorted) , con keycmp/3 definido por el usuario. Incluso entonces, el orden de los resultados con claves equivalentes depende no solo de la definición (usuario) de keycmp/3 , sino también de la implementación de predsort/3 .

En otras palabras, una clasificación "estable" con predsort/3 es una mala idea.