Список различий Пролога - mergesort

Question

Я должен написать предикат, который разделит один список на два списка (пополам):

halve(X-Y, X-Z, Z-Y) :- halve_pom(X-Y, X-Y, Z), !.

halve_pom(Z-Y, Y-Y, Z).

halve_pom([_|A]-Y, [_,_|B]-Y, Z) :- halve_pom(A-Y, B-Y, Z).

Это было легко, но теперь я должен написать алгоритм, который будет выполнять сортировку слиянием - я понятия не имею. Этот алгоритм должен использовать списки различий.

Пожалуйста помоги.

Answer 1

Нет, это было не просто, так как, к сожалению, это не работает. halve([1,2,3]-[],A,B) не работает; halve_pom([1,2,3]-[],A,B) тоже не работает. Кроме того, неясно, какую из схем расщепления вы предпочитаете, [1,2,3,4,5,6,7] -> ([1,3,5,7] , [2,4,6]) или же -> ([1,2,3,4] , [5,6,7]),

Если твой halve предикат сработал, все, что вам нужно сделать, это определить merge, что бы объединить две половины списка, по порядку. Затем,

mergesort(A,S):- halve(A,B-[],C-[]), mergesort(B,SB), mergesort(C,SC),
  merge(SB,SC,S-[]).

Обратите внимание, что вы, вероятно, назвали бы это с обычным списком Aто есть halve Предикат должен ожидать свой первый аргумент как обычный список (т.е. не список различий).

См. Также Что означает символ "-" в Прологе при работе со списками?, '-' не нужно; вместо этого его две составляющие должны использоваться как два отдельных аргумента для предиката.

---

Итак, один из способов кодирования halve является

halve([A,B|C],[A|X]-ZX,[B|Y]-ZY):- halve(C,X-ZX,Y-ZY). 
halve([A],[A|X]-X,Y-Y). 
halve([],X-X,Y-Y).

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

merge(SB,SC,S-Z):- SB=[A|B], SC=[C|D], A=<C, S=[A|T], merge(B,SC,T-Z).
merge(SB,SC,S-Z):- SB=[A|B], SC=[C|D], A>C,  ... ,    ... .
merge(SB,SC,S-Z):- SB=[A|B], SC=[],          ... ,    ... .
merge(SB,SC,S-Z):- SB=[], SC=[C|D],          S=[C|T], ... .
merge([],[],Z-Z).