如何将两个已排序的列表合并成一个排序列表

Question

在Prolog中，我需要找出一种方法将两个已排序的列表合并成一个排序的列表。换句话说，从两个列表中比较其头部元素，将最小的添加到新列表中。我认为我已经做得很好了，但不知道为什么它就是无法正常工作。BTW，我没有收到任何错误提示，只是返回了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).

- user1666419

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

将这样的谓词命名为“sort”实在是误导人，使用“merge”会更好一些...

在 sort/2 Prolog 语法中，删除重复项，因此应该将 L = [Head1,Head2|R] 替换为 L = [Head1|R]，其中 Head1=Head2（未通过前面的测试）。

- CapelliC

---

对于 [], []，成功两次。 - false

Answer 2

在SWI Prolog中，有一个内置谓词merge/3可以实现这个功能。因此，你不应该将你的谓词称为“sort”，它不是“sort”，而是“merge”。

接下来，让我们阅读你的定义。

merge([H1|T1], [H2|T2], L) :-

意思是，合并这两个列表会产生合并后的列表L。到目前为止，一切顺利。

    H1 < H2 -> append([H1],L,L2), merge(T1,[H2|T2],L2) 

意思是，如果 H1 < H2，则在答案列表 L 前缀添加 H1 可以得到 L2，这是合并的结果...等等，这有意义吗？

Prolog 不是 Basic。我们写的不是用于“执行”操作的“命令”_{（好吧，它们是，但是通过迂回的方式）}。如果我们想说 H1 是 L 的头元素，我们就这么说：

               L = [H1|L2],        merge(T1,[H2|T2],L2) 
        %% or: append([H1],L2,L), 

等等，现在这就有意义了。 :)

- Will Ness

---

好的，谢谢。但我必须为自己创建一些东西。这是一个任务。 - user1666419

@Haile他们不是，但我们仍然可以提供指导...例如，在这里，OP问了他们做错了什么，所以我认为我已经回答了这个问题-而没有透露全部代码。现在，如果OP要求完整的代码，而我没有提供，也许我的答案就会被认为是不完整的答案，一些大佬主管（我的意思是，“管理员”）会将其评为负分，并扣除我的声望...我不知道。幸运的是，这里的问题不是这样的。 - Will Ness

@WillNess 当然。我读错了他的评论，以为他在询问你引用的merge/3谓词的代码。 - Haile

@Haile 不要介意。 :) 顺便说一下， listing(merge) 给了我那段代码。 :) 它没有使用 <。 - Will Ness

Answer 3

根据您问题中的代码，您正在合并已排序的数字列表。 如果这些数字都是整数，并且您的Prolog系统提供clpfd，请考虑使用此处提供的代码。为什么呢？

• 该实现保留逻辑纯度。
• 代码单调，使其具有弹性和灵活性：即使在非基础数据的情况下工作，始终可以获得逻辑上正确的答案。
• 主要谓词sorted1_sorted2_merged/3表现得像一个真实的关系。
• 与内置的sort/2不同，此代码保留所有重复项（完全相同的多重性）。
• 关于要合并的列表中的相等项，它的行为是合理的： 输入#1中与输入#2中某些项目相等的项目位于合并结果中的那些项目之前。
• 该实现在不留下无用的选择点方面效率高，例如sorted1_sorted2_merged([1,3,5],[2,4,5,6],Zs)。

没有更多的话...这就是代码:

:- use_module(library(clpfd)).

sorted1_sorted2_merged([]    ,Ys,Ys).
sorted1_sorted2_merged([X|Xs],Ys,Zs) :-
   sorted2_hd1_tl1_merged(Ys,X,Xs,Zs).

hd1_tl1_hd2_tl2_merged(X,Xs,Y,Ys,Zs) :-
   zcompare(Op,X,Y),
   op_hd1_tl1_hd2_tl2_merged(Op,X,Xs,Y,Ys,Zs).

sorted1_hd2_tl2_merged([]    ,Y,Ys,[Y|Ys]).
sorted1_hd2_tl2_merged([X|Xs],Y,Ys,Zs) :- 
   hd1_tl1_hd2_tl2_merged(X,Xs,Y,Ys,Zs).

sorted2_hd1_tl1_merged([]    ,X,Xs,[X|Xs]).
sorted2_hd1_tl1_merged([Y|Ys],X,Xs,Zs) :-
   hd1_tl1_hd2_tl2_merged(X,Xs,Y,Ys,Zs).

op_hd1_tl1_hd2_tl2_merged(<,X,Xs,Y,Ys,[X|Zs]) :-
   sorted1_hd2_tl2_merged(Xs,Y,Ys,Zs).
op_hd1_tl1_hd2_tl2_merged(=,X,Xs,Y,Ys,[X|Zs]) :- 
   sorted1_hd2_tl2_merged(Xs,Y,Ys,Zs).
op_hd1_tl1_hd2_tl2_merged(>,X,Xs,Y,Ys,[Y|Zs]) :- 
   sorted1_hd2_tl2_merged(Ys,X,Xs,Zs).

转化为中文：

接下来是一些查询！首先：

?- sorted1_sorted2_merged([1,3,4,6],[2,4,5,5,7],Xs).
Xs = [1,2,3,4,4,5,5,6,7].         % succeeds deterministically

它在“其他方向”中也能工作吗？

?- sorted1_sorted2_merged([1,3,4,6],Ys,[1,2,3,4,4,5,5,6,7]).
Ys = [2,4,5,5,7] ;                % succeeds, but leaves behind choicepoint
false.

?- sorted1_sorted2_merged(Xs,[2,4,5,5,7],[1,2,3,4,4,5,5,6,7]).
Xs = [1,3,4,6] ;                  % succeeds, but leaves behind choicepoint
false.

最后，一个相当普遍的用途：

?- sorted1_sorted2_merged(Xs,Ys,[0,1,2,3]).
Xs = [       ], Ys = [0,1,2,3] ;
Xs = [0,1,2,3], Ys = [       ] ;
Xs = [0      ], Ys = [  1,2,3] ;
Xs = [0,1    ], Ys = [    2,3] ;
Xs = [0,1,2  ], Ys = [      3] ;
Xs = [0,1,  3], Ys = [      2] ;
Xs = [0,  2,3], Ys = [      1] ;
Xs = [0,    3], Ys = [  1,2  ] ;
Xs = [0,  2  ], Ys = [  1,  3] ;
Xs = [  1,2,3], Ys = [0      ] ;
Xs = [    2,3], Ys = [0,1    ] ;
Xs = [      3], Ys = [0,1,2  ] ;
Xs = [    2  ], Ys = [0,1,  3] ;
Xs = [  1    ], Ys = [0,  2,3] ;
Xs = [  1,2  ], Ys = [0,    3] ;
Xs = [  1,  3], Ys = [0,  2  ] ;
false.

- repeat