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