Prolog实施Mergersort不会停止

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 = []

因为这个程序循环,你的原始程序也循环.因此,可见部分的某处必定存在错误.递归规则mergesort/2适用于空列表真的有意义吗？

((除此之外,分裂是非常低效的.))