Prolog 合并排序的实现不会停止

Question

我是一名新的 Prolog 开发人员，正在尝试让合并排序工作。查询

mergesort([2,1],T).

将生产

T=[1,2];
T=[1,2];
T=[1,2];
...

因此，尽管它似乎“正确”地对序列进行了排序，但它并没有停止

另一方面，如果我有一个查询，例如

mergesort([2,1],[2,1])

它进入无限循环。我想知道为什么会这样？

append([H|T],LISTB,[H|LISTC]):-
    append(T,LISTB,LISTC).

split(LIST,L1,L2):-
    length(LIST,LENGTH),
    M is div(LENGTH,2),
    append(L1,L2,LIST),
    length(L1,L1LENGTH),
    (L1LENGTH =:= M).

merge(A,[],A).
merge([],B,B).
merge([A|TA],[B|TB],[A|MERGED]) :-
    A =< B,
    merge(TA,[B|TB],MERGED).
merge([A|TA],[B|TB],[B|MERGED]) :-
    B < A,
    merge([A|TA],TB,MERGED).

mergesort([],[]).
mergesort([X],[X]).
mergesort(LIST,OLIST):-
    split(LIST,L1,L2),
    mergesort(L1,OLIST1),
    mergesort(L2,OLIST2),
    merge(OLIST1,OLIST2,OLIST).

Answer 1

^{(缺少append([]，L，L)。)}

首先，减少输入的大小! [2,1] 遇到的问题已经可以通过 [2] 甚至 [] 观察到!

?- mergesort([],T).
   T = []
;  T = []
;  T = []
;  T = []
;  ... .

所以问题似乎是程序没有终止。或者也许在十个答案后就停止了？有一种方法可以更好地测试这一点:

?- mergesort([], T), false.   loops.

如果我愿意，我将在您的程序中添加更多目标，以便生成的程序仍然循环:

append([], L, L).append([H|T],LISTB,[H|LISTC]):- false,    append(T,LISTB,LISTC).split(LIST,L1,L2):- LIST = [],    length(LIST,LENGTH),    M is div(LENGTH,2),    append(L1,L2,LIST),    length(L1,L1LENGTH),    (L1LENGTH =:= M).mergesort([],[]) :- false.mergesort([X],[X]) :- false.mergesort(LIST,OLIST):- LIST = [],    split(LIST,L1,L2), L1 = [], L2 = [],    mergesort(L1,OLIST1), false,    mergesort(L2,OLIST2),    merge(OLIST1,OLIST2,OLIST).

我添加了目标 false 和 L = [] 它们都会终止，因此将要么改进终止，要么保持原样。该程序的结果片段称为 failure-slice .

因为这个程序循环，你原来的程序也会循环。因此，可见部分一定有错误。 mergesort/2 的递归规则应用于空列表真的有意义吗？

((除此之外， split 的效率相当低。))