'predsort/3`의 가능한 행동

Question

keysort에 대한 새 목록을 만들지 않고이 용어의 특정 인수를 정렬하는 것에 대한 질문으로 answer의 후속 조치입니다 (원래 질문을 올바르게 이해 한 경우).

이

?- predsort(compare, List, Sorted). 

이제 우리는 msort/2에 의해 구현으로 정렬 predsort/3를 사용하고 싶다고 말한다 (참조 : 내가 제대로 이해한다면,이로 호출 의미 :

우리가 정확하게 작동하도록 sort/2로 predsort/3를 원 말 이 question).

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

?- predsort(mcompare, List, Sorted). 

질문 : 그것을 할 수있는 한 가지 방법은 요소가 실제로 동일한 경우 =와 Delta를 통합하지 않는 비교 조건 Pred(-Delta, +A, +B)을 정의하는 것입니다 정말 단순히 종류의 msort/2으로, 중복을 제거하지 않고 않는다는 것을 수행 ? 그것은해야하는 것처럼 보인다.

계속 진행 : 용어의 n 번째 인수의 표준 순서에 따라 arity> 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 같은는 012,394을 사용. 그것은 중복을 제거하고, 두 용어의 두 번째 인수가 동일하게 일어날 경우 원래 만삭의 표준 순서에 따라 복합 용어를 주문한다 :

?- 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 앞에옵니다. 우리가 비교를 정의 할 수 있습니다 : 그들은 원래 목록에 있던으로하고 경우에만 두 요소 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 
    ). 

, 를이해야 위의 sort_argn/3에 동일하게 작동 : 두 개의 "키"가 동일한 경우 compare_argn_stable/4가 <와 Delta을 통합하는 것이

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

것은 지금의 과정이 중요하다. 또한 동작은 구현에 따라 다르며 predsort/3 요소를 비교 술어로 전달할 때 요소의 원래 순서를 유지하는 경우에만 keysort 예제와 동일합니다.

질문 맞습니까?

질문predsort/3의이 측면을 다루는 표준이 있습니까?

Answer 1

아무도 대답하지 않았다 때문에

, 이후 지금은 그것에 대해 매우 확신 :

예, 당신은 다른 종류의를 에뮬레이션 predsort/3를 사용할 수 있습니다. 이 질문은 어떻게 자세하게 설명합니다.

: 이것은 여러 가지 이유로 좋지 않습니다.

• 은 "안정성"(질문 참조)
• predsort/3 자체가 (지금까지 내가 말할 수있는) 표준의 일부가 아닌
• 확률은 predsort/3의 구현에 프롤로그를 따라 구현은 제공 훨씬 더 효율적 predsort/3보다 있다는 msort/2 또는 keysort/2

리스트의 요소의 크기가 렌보다 훨씬 더 큰 드문 경우가있을 수 있습니다 우리가 정렬 된 목록의 GTH, 그리고이 작은 춤 :

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

(see here가) 실제로 사용자에 의해 정의 keycmp/3으로, predsort(keycmp, List, Sorted)를 사용하는 것보다 더 비싼 (느린)입니다. 그런 경우에도 동일한 키를 사용하는 결과의 순서는 keycmp/3의 (사용자) 정의뿐만 아니라 predsort/3의 구현에 따라 달라집니다.

즉, predsort/3의 "안정적인"정렬은 좋지 않은 아이디어입니다.