我想编写合并两个列表的合并函数,我可以通过编写两个(合并)谓词来实现,一个是元素 H1 =< H2,另一个是 H1 > H2,但是我想写 if-the-其他条件,但随后统一失败,我不知道该怎么做。这是我的代码:
merge([H1|T1],[H2|T2],List):-
(
H1 =< H2 ->
NewList = [H1|List],
merge(T1,[H2|T2],NewList)
;
NewList = [H2|List],
merge([H1|T1],T2,NewList)
).
merge([],L,L).
merge(L,[],L).
我知道问题出在哪里,如果我写两个合并谓词我可以避免它但我不知道如何在这里做,我被卡住了:(
模式匹配在这里失败:
最佳答案
您实际上非常接近。看看这条痕迹:
?- trace, merge([1,3,5,6], [2,4,7,8], X).
Call: (9) merge([1, 3, 5, 6], [2, 4, 7, 8], _6684) ? creep
Call: (10) 1=<2 ? creep
Exit: (10) 1=<2 ? creep
Call: (10) _7050=[1|_6684] ? creep
Exit: (10) [1|_6684]=[1|_6684] ? creep
Call: (10) merge([3, 5, 6], [2, 4, 7, 8], [1|_6684]) ? creep
Call: (11) 3=<2 ? creep
Fail: (11) 3=<2 ? creep
Redo: (10) merge([3, 5, 6], [2, 4, 7, 8], [1|_6684]) ? creep
Call: (11) _7062=[2, 1|_6684] ? creep
Exit: (11) [2, 1|_6684]=[2, 1|_6684] ? creep
Call: (11) merge([3, 5, 6], [4, 7, 8], [2, 1|_6684]) ? creep
Call: (12) 3=<4 ? creep
Exit: (12) 3=<4 ? creep
Call: (12) _7074=[3, 2, 1|_6684] ? creep
Exit: (12) [3, 2, 1|_6684]=[3, 2, 1|_6684] ? creep
Call: (12) merge([5, 6], [4, 7, 8], [3, 2, 1|_6684]) ? creep
Call: (13) 5=<4 ? creep
Fail: (13) 5=<4 ? creep
Redo: (12) merge([5, 6], [4, 7, 8], [3, 2, 1|_6684]) ? creep
Call: (13) _7086=[4, 3, 2, 1|_6684] ? creep
Exit: (13) [4, 3, 2, 1|_6684]=[4, 3, 2, 1|_6684] ? creep
Call: (13) merge([5, 6], [7, 8], [4, 3, 2, 1|_6684]) ? creep
Call: (14) 5=<7 ? creep
Exit: (14) 5=<7 ? creep
Call: (14) _7098=[5, 4, 3, 2, 1|_6684] ? creep
Exit: (14) [5, 4, 3, 2, 1|_6684]=[5, 4, 3, 2, 1|_6684] ? creep
Call: (14) merge([6], [7, 8], [5, 4, 3, 2, 1|_6684]) ? creep
Call: (15) 6=<7 ? creep
Exit: (15) 6=<7 ? creep
Call: (15) _7110=[6, 5, 4, 3, 2, 1|_6684] ? creep
Exit: (15) [6, 5, 4, 3, 2, 1|_6684]=[6, 5, 4, 3, 2, 1|_6684] ? creep
此时在递归的深度,你几乎有了解决方案。然后它开始出错:
Call: (15) merge([], [7, 8], [6, 5, 4, 3, 2, 1|_6684]) ? creep
Fail: (15) merge([], [7, 8], [6, 5, 4, 3, 2, 1|_6684]) ? creep
Redo: (14) merge([6], [7, 8], [5, 4, 3, 2, 1|_6684]) ? creep
Fail: (14) merge([6], [7, 8], [5, 4, 3, 2, 1|_6684]) ? creep
Redo: (13) merge([5, 6], [7, 8], [4, 3, 2, 1|_6684]) ? creep
Fail: (13) merge([5, 6], [7, 8], [4, 3, 2, 1|_6684]) ? creep
Redo: (12) merge([5, 6], [4, 7, 8], [3, 2, 1|_6684]) ? creep
Fail: (12) merge([5, 6], [4, 7, 8], [3, 2, 1|_6684]) ? creep
Redo: (11) merge([3, 5, 6], [4, 7, 8], [2, 1|_6684]) ? creep
Fail: (11) merge([3, 5, 6], [4, 7, 8], [2, 1|_6684]) ? creep
Redo: (10) merge([3, 5, 6], [2, 4, 7, 8], [1|_6684]) ? creep
Fail: (10) merge([3, 5, 6], [2, 4, 7, 8], [1|_6684]) ? creep
Redo: (9) merge([1, 3, 5, 6], [2, 4, 7, 8], _6684) ? creep
Fail: (9) merge([1, 3, 5, 6], [2, 4, 7, 8], _6684) ? creep
那么你的代码有什么问题?主要有两件事:您正在构建相反的结果(并不少见)并且您没有将其传回的好方法。安排一个结果变量当然是处理这些问题的一种方法,类似于 Luai 的想法:
merge(X,Y,Z) :- merge(X, Y, [], Z).
merge([H1|T1],[H2|T2],List,NewList):-
(
H1 =< H2 ->
merge(T1,[H2|T2],[H1|List],NewList)
;
merge([H1|T1],T2,[H2|List],NewList)
).
merge([],R,LRev,Res) :- reverse(LRev, L), append(L,R,Res).
merge(R,[],LRev,Res) :- reverse(LRev, L), append(L,R,Res).
或者您将不得不想出另一种方法来做到这一点,例如通过传递列表的尾部,如下所示:
merge2([H1|T1], [H2|T2], MT) :-
(H1 =< H2 ->
MT=[H1|MT2],
merge2(T1, [H2|T2], MT2)
;
MT=[H2|MT2],
merge2([H1|T1], T2, MT2)
).
merge2([], T2, T2).
merge2(T2, [], T2).
我个人赞成这种方法。
关于list - Prolog统一和优化,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47170736/