Mergersort 的序言实施不会停止

Question

我是一名新的 Prolog 开发人员，正在尝试获取合并排序 working.The 查询

mergesort([2,1],T).

将生产

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

所以虽然它似乎 "correctly" 对序列进行排序但它并没有停止

另一方面，如果我有这样的查询

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

我确定这是一个 hacky 解决方案，但它是 A 解决方案

mergesort(LIST,OLIST):-
    split(LIST,L1,L2),
    mergesort(L1,OLIST1),
    mergesort(L2,OLIST2),
    merge(OLIST1,OLIST2,OLIST),
    !.

Answer 2

^{（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 的效率非常低。))

Mergersort 的序言实施不会停止

Prolog Implementation of Mergersort won't halt

mergesort

prolog

infinite-loop

failure-slice