Prolog的差異列表 - 歸併

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謂語應該期待它的第一個參數作爲一個正常的列表（即不差列表）。請參閱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).