请解释Bubblesort Prolog计划中的剪辑？

Question

我目前正在通过Bratko Prolog的书工作,我正在研究泡沫分类计划.我似乎无法弄清楚为什么cut(!)是必要的.说削减不存在,Prolog会回溯,怎么可能找到错误的答案？因为如果我从中删除它,Prolog开始给我正确的答案,但随后也给出了其他不好的答案.

在我看来,交换怎么能返回一个非排序列表？如何将非排序列表击中目标bubblesort(Sorted, Sorted).

当然除非第一个名单也被改变了......不能理解它.

Prolog BubbleSort计划:

gt(X,Y) :- X > Y.

bubblesort(List, Sorted) :-
  swap(List, List1), !,           % A useful swap in List?
  bubblesort(List1, Sorted).
bubblesort(Sorted, Sorted).       % Otherwise list is already sorted

swap([X,Y|Rest], [Y,X|Rest]) :-   % Swap first two elements
  gt(X,Y).
swap([Z|Rest], [Z|Rest1]) :-      % Swap elements in tail
  swap(Rest, Rest1).

离开时,它给了我:

?- bubblesort([5,7,3,6,8,9,2,6], Sorted).

Sorted = [2, 3, 5, 6, 6, 7, 8, 9] ;

Sorted = [2, 3, 5, 6, 7, 6, 8, 9] ;

Sorted = [2, 3, 5, 6, 7, 8, 6, 9] ;

Sorted = [2, 3, 5, 6, 7, 8, 9, 6] ;

我认为不知怎的,我明白了,但我不确定.可能是在某个时刻,它回溯swap(List, List1)到第二个冒泡排序谓词并击中目标,这意味着Sorted的两个列表是相等的？

在英语中,这是否意味着冒泡排序需要继续进行交换,直到不再可能进行掉期,但是需要终止？或者这是否意味着每次成功完成交换,对成功进行回溯都没有用？

Answer 1

有几种可能性使目标swap(List, List1)失败.要么List是长度为0或1的列表; 或者它不包含两个紧接着的元素,其中第二个小于第一个元素.

切割的方式使其既可以切割,也可以swap/2替代切割bubblesort/2.

这是一个很好的例子,"深切"(深入切割swap/2)仍然可以很好地工作.但是,这种情况非常罕见.大多数时候,削减太多了.如果已经提出第二个论点,那么最大多数此类程序使用起来非常脆弱,更是如此.他们往往不坚定.

啊,我几乎错过了它:即使在这个程序中,我们也bubblesort(nonlist,L)取得了成功,或者bubblesort([1|nonlist],L)可能不是这样,并导致细微的编程错误.

还有另一个原因,为什么这个程序没有呈现理想的逻辑编程风格:bubblesort/2单独阅读的第二个规则是:一切都是一个排序列表 `.要理解这一点,我们必须同时阅读这两条规则并将其缩小到除了......之外的所有规则.

在英语中,这是否意味着冒泡排序需要继续进行交换,直到不再可能进行掉期,但是需要终止？或者这是否意味着每次成功完成交换,对成功进行回溯都没有用？

这是第一个适用于此的程序性意义.当然,回溯第二个条款的成功bubblesort/2将是一个错误.

另一个非常不直观的细节并不是特定于剪辑,除了数字之外,该程序还成功地表达了类似的表情bubblesort([1,1+1],L),这可能会导致细微的差异.