如何从两个已排序的列表中生成一个已排序的列表

Question

在 Prolog 中，我必须找出一种方法，将两个已排序的列表合并为一个排序的列表。换句话说：我必须比较两个列表中的头并将最小的添加到新列表中。我想我已经走了很远，但不知怎的，它就是行不通，我不明白为什么不行。顺便说一句，我没有收到任何错误。它只是回馈false。

所以，我希望有人能告诉我我做错了什么。

sort([],L,L).
sort(L,[],L).
sort([Head1|Tail1],[Head2|Tail2],L) :- 
    Head1 < Head2 -> append([Head1],L,L2), sort(Tail1,[Head2|Tail2],L2) ; 
    Head1 > Head2 -> append([Head2],L,L2), sort([Head1|Tail1],Tail2,L2) ; 
    Head1 == Head2 -> append([Head1],L,L2), append([Head2],L2,L3), 
                                            sort(Tail1,Tail2,L3).

Answer 1

你应该稍微简化你的代码：

sort([],L,L).
sort(L,[],L).
sort([Head1|Tail1], [Head2|Tail2], L) :- 
    Head1 < Head2 -> L = [Head1|R], sort(Tail1,[Head2|Tail2],R) ;
    Head1 > Head2 -> L = [Head2|R], sort([Head1|Tail1],Tail2,R) ;
    L = [Head1,Head2|R], sort(Tail1,Tail2,R).

测试：

?- sort([1,2,4,5,18],[1,3,5,10],R).
R = [1, 2, 3, 4, 5, 10, 18] .

命名这样的谓词排序确实具有误导性，合并会更好......

编辑 L = [Head1,Head2|R]而不是L = [Head1|R]Head1=Head2 （之前的测试失败）偏离了 sort/2 Prolog 语义，即删除了重复项。