Пролога разницы списка - сортировка слияние

Question

я должен написать предикат, который будет разбит один список в два список (по Halve):

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 предикат следует ожидать свой первый аргумент как обычный список (т.е. не разница-лист).

См. Также What does the "-" symbol mean in Prolog when dealing with lists?. '-' не нужен; вместо этого его две составляющие должны использоваться в качестве двух отдельных аргументов для предиката.

---

Таким образом, один из способов кодирования 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).