0

我有这个插入排序来在 Prolog 中按降序对列表进行排序，它可以工作：

insert(X,[],[X]).
insert(X, [Y|Tail], [X,Y|Tail]):- X > Y, !.
insert(X, [Y|Tail], [Y|NTail]):- insert(X, Tail, NTail).
ins_sort([], []).   
ins_sort([X|Tail], Sorted):- ins_sort(Tail, STail), insert(X, STail, Sorted).

我在 SWISH 上运行它，并试图通过以下跟踪了解它的功能：

 Call:ins_sort([1, 2, 3, 4, 5], _12162)
 Call:ins_sort([2, 3, 4, 5], _12358)
 Call:ins_sort([3, 4, 5], _12358)
 Call:ins_sort([4, 5], _12358)
 Call:ins_sort([5], _12358)
 Call:ins_sort([], _12358)
 Exit:ins_sort([], [])
 Call:insert(5, [], _12360)
 Exit:insert(5, [], [5])
 Exit:ins_sort([5], [5])
 Call:insert(4, [5], _12366)
 Call:4>5
 Fail:4>5
 Redo:insert(4, [5], _12370)
 Call:insert(4, [], _12282)
 Exit:insert(4, [], [4])
 Exit:insert(4, [5], [5, 4])
 Exit:ins_sort([4, 5], [5, 4])
 Call:insert(3, [5, 4], _12378)
 Call:3>5
 Fail:3>5
 Redo:insert(3, [5, 4], _12382)
 Call:insert(3, [4], _12294)
 Call:3>4
 Fail:3>4
 Redo:insert(3, [4], _12294)
 Call:insert(3, [], _12300)
 Exit:insert(3, [], [3])
 Exit:insert(3, [4], [4, 3])
 Exit:insert(3, [5, 4], [5, 4, 3])
 Exit:ins_sort([3, 4, 5], [5, 4, 3])
 Call:insert(2, [5, 4, 3], _12396)
 Call:2>5
 Fail:2>5
 Redo:insert(2, [5, 4, 3], _12400)
 Call:insert(2, [4, 3], _12312)
 Call:2>4
 Fail:2>4
 Redo:insert(2, [4, 3], _12312)
 Call:insert(2, [3], _12318)
 Call:2>3
 Fail:2>3
 Redo:insert(2, [3], _12318)
 Call:insert(2, [], _12324)
 Exit:insert(2, [], [2])
 Exit:insert(2, [3], [3, 2])
 Exit:insert(2, [4, 3], [4, 3, 2])
 Exit:insert(2, [5, 4, 3], [5, 4, 3, 2])
 Exit:ins_sort([2, 3, 4, 5], [5, 4, 3, 2])
 Call:insert(1, [5, 4, 3, 2], _12162)
 Call:1>5
 Fail:1>5
 Redo:insert(1, [5, 4, 3, 2], _12162)
 Call:insert(1, [4, 3, 2], _12336)
 Call:1>4
 Fail:1>4
 Redo:insert(1, [4, 3, 2], _12336)
 Call:insert(1, [3, 2], _12342)
 Call:1>3
 Fail:1>3
 Redo:insert(1, [3, 2], _12342)
 Call:insert(1, [2], _12348)
 Call:1>2
 Fail:1>2
 Redo:insert(1, [2], _12348)
 Call:insert(1, [], _12354)
 Exit:insert(1, [], [1])
 Exit:insert(1, [2], [2, 1])
 Exit:insert(1, [3, 2], [3, 2, 1])
 Exit:insert(1, [4, 3, 2], [4, 3, 2, 1])
 Exit:insert(1, [5, 4, 3, 2], [5, 4, 3, 2, 1])
 Exit:ins_sort([1, 2, 3, 4, 5], [5, 4, 3, 2, 1])

一旦我越过第一个“出口”，我就会迷路。我理解所有的递归调用，直到我们到达一个空列表，它会因为另一个事实而停止递归调用并开始返回，但是为什么在第 7 行的第一次退出之后，未定义的 STail 变成了一个空列表 []插入调用？

ins_sort([], []) 的退出是否将 STail 设置为空集 []，这是否意味着事实的最后一个参数是返回值或其他什么？

4

3 回答 3

2

痕迹太难了。重写通常要容易得多，尤其是使用像这里这样的确定性谓词。长变量名也太分散注意力。与其阅读和记忆，不如简单地看一下：

insert(X, [],    [X]).                                                                %1
insert(X, [Y|T], [X,Y|T] ):- X > Y, !.            % X was indeed greater than Y:      %2
                                                  %   accept the solution and stop;   %3
insert(X, [Y|T], [  Y|NT]):- insert(X, T, NT).    %   otherwise, insert into tail.    %4
                                                                                      %5
ins_sort( [],   []).              % rule {1}                                          %6
ins_sort( [X|T], S):-             % rule {2}                                          %7
   ins_sort( T,     ST),                                                              %8
   insert( X,       ST,                                                               %9
                 S).                                                                 %10

让我们用一个较短的列表来试试，

  ins_sort([1, 2, 3], S) ?                                                S.         %11
=           \                                                            /           %12
  {2:      [X1|T1]=[1,2,3] }                                            /            %13
      ins_sort(T1, ST1),                               insert(X1, ST1, S).           %14 
=               \                                                 /                  %15
      {2:      [X2|T2]=T1=[2,3] }                                /                   %16
          ins_sort(T2, ST2),                    insert(X2, ST2, ST1).                %17
=                   \                                      /                         %18
          {2:      [X3|T3]=T2=[3] }                       /                          %19
              ins_sort(T3, ST3),         insert(X3, ST3, ST2).                       %20
=                       \                          /                                 %21
              {1:      T3=[]                     ST3=[] }.                           %22

我们沿着 V 形轨迹从左上角向下到中间，结束递归直到我们到达基本情况，然后向上和向右，同时展开递归并在返回的路上构建结果基本情况，像往常一样。因此，我们从下往上开始建立，

  ST3 = [].                                                                          %22
  insert( {X3=3}, {ST3=[]}, ST2 ):- ST2 = [3].                                       %20
  insert( {X2=2}, {ST2=[3]}, ST1 ):- ST1 = [3,2].                                    %17
  insert( {X1=1}, {ST1=[3,2]}, S ):- S = [3,2,1].                                    %14

就是这样。

于 2017-11-02T19:02:03.060 回答
1

我认为这里的问题是您在理解递归期间变量发生的情况时遇到了一些困难。让我们看一个简化的案例：

count([], 0).
count([X|Xs], N) :- count(Xs, N0), succ(N0, N).

当我打电话时会发生什么count([a,b], N)：

count([a, b], N)
 +-> count([b], N)

进入后我们要做的第一件事count([a,b], N)是递归调用count/2. 当 Prolog 重新进入 count 时，我们突然有了一组新的 和X绑定Xs。在外部调用中，X=aand Xs=[b]，但在内部调用中，X=band Xs=[]。然后会有第三次内部调用，它以Xsvalue开头[]。这对应于该跟踪的前三行：

Call: (8) count([a, b], _8636) ? creep
Call: (9) count([b], _8866) ? creep
Call: (10) count([], _8866) ? creep

跟踪器在这里告诉您的是“我正在尝试使用这些值和变量输入这个谓词。” 请注意，变量实际上在第一次和第二次调用之间更改为 N。

现在，您会注意到[]无法匹配第二个子句，只能匹配第一个子句。第一个没有主体，但确实建立了绑定。因此，跟踪的下一行将反映：

Exit: (10) count([], 0) ? creep

看到旁边的数字了吗？这告诉你调用堆栈的深度。使用数字进行跟踪而不是直观地显示嵌套很方便，因为最终我们的调用堆栈会变得非常深！

现在我们有了变量的值，它将转到我们所在的子句中的下一个表达式：

Call: (10) succ(0, _8866) ? creep
Exit: (10) succ(0, 1) ? creep

嵌套级别上升了一级，但立即解决；这对于带有内置插件的课程来说是一样的succ/2。现在让我们看一下跟踪的其余部分：

Exit: (9) count([b], 1) ? creep
Call: (9) succ(1, _8636) ? creep
Exit: (9) succ(1, 2) ? creep
Exit: (8) count([a, b], 2) ? creep

所以现在我们有了递归调用的绑定，我们可以在父调用中进入下一步，依此类推，直到整个调用解决，我们得到 2。

让我们再看一遍，这次用嵌套而不是数字：

[trace]  ?- count([a,b],N).
  Call: (8) count([a, b], _8636) ? creep
    Call: (9) count([b], _8866) ? creep
      Call: (10) count([], _8866) ? creep
      Exit: (10) count([], 0) ? creep
      Call: (10) succ(0, _8866) ? creep
      Exit: (10) succ(0, 1) ? creep
    Exit: (9) count([b], 1) ? creep
    Call: (9) succ(1, _8636) ? creep
    Exit: (9) succ(1, 2) ? creep
  Exit: (8) count([a, b], 2) ? creep
N = 2.

这应该使您自己的跟踪中发生的事情更容易理解。

于 2017-11-02T15:38:14.783 回答
0

Prolog 与统一和模式匹配一​​起工作。您正在删除 Head 并再次使用 tail 调用谓词，tail 会不断删除 Head 并尝试在每次调用后查找匹配项，稍后您有一个空列表，因此 prolog 搜索您的文件以查找匹配项并且在这一点上它找到了一个匹配ins_sort([], []). 在第 6 次调用中，你有Call:ins_sort([], _12358)where _12358is a variable 并且这个变量将得到ns_sort([], []).一个事实的值。它只是意味着如果您在 ns_sort 中有一个空列表和一个变量，然后将该变量设置为也等于空列表，如果您有所有其他“术语”匹配，则变量将被实例化。

通过学习回溯可以很容易地理解Prolog，回溯是一种算法，因此prolog self是一种算法。

于 2017-11-02T06:42:45.973 回答