2 
s(A,A).
s(A,D):- l(A,B),s(B,C),r(C,D).

l([a|A],A).

r([b|A],A).

prolog 中的上述代码检查列表的给定输入是否等于 a 和 b。

如

s([a,a,b,b],[]).
True.

这涉及递归和差异列表。任何人都可以解释底层递归如何一步一步地检查 a 和 b 是否相等。

4

2 回答 2

6

如果您在低层次上对它们进行推理，那么列表差异就不容易理解。

因此，我首先推荐一个更高级的视图：

总的来说，您的谓词s/2描述了一个list。我说“描述”，因为它不仅“检查”，而且如果我们愿意，它还会生成和完成这样的列表！

我们可以将每个目标读s/2作“然后是列表的一些元素”。

所以，暂时忘记论点，考虑谓词的抽象结构。我(-->)/2现在使用而不是(:-)/2明确我在谈论谓词的一个小变化，我只是忽略了参数：

s --> []。
s --> l, s, r。

我们可以用l/2and做同样的事情r/2：

l --> [a]。
r --> [b]。

这就是谓词在列表的抽象高级视图中描述的内容。在这种表示法中，我不需要与列表差异和论点搏斗。相反，我可以直接关注程序的本质。

很明显，您可以轻松地将此类高级代码转换为您发布的代码。事实上，如果您查阅这段代码，Prolog 会为您执行此翻译：它称为DCG 表示法。有关详细信息，请参阅。

所以，现在很清楚：s//0描述一个空列表，或者：

  • 由描述的列表l//0
  • 然后是一个由描述的列表s//0
  • 然后是由 描述的列表r//0。

由于l//0用单个元素描述了一个列表a，并且用一个元素r//0描述了一个列表b，很明显，在描述的列表中， s 和s 的s//0数量总是相同的。ab

我们phrase/2用来调用 DCG。例如：

?- 短语(s, Ls)。
LS = [] ;
LS = [a, b] ;
Ls = [a, a, b, b] ;
Ls = [a, a, a, b, b, b] 。

如果您开始明确地推理递归，您将不会取得太大进展，因为跟踪 Prolog 引擎执行的确切步骤并考虑所有可能性很快就会变得太难。我建议您关注谓词的含义，并尝试理解它们实际描述的内容。

编辑：如果您想明确地推理参数，代数类比可能会有所帮助：我们可以将每对参数视为将列表描述为两个列表之间的“差异”，一个列表差异，也类似于使用的微分 Δ结石。

例如，[X,Y,Z|Rs]和之间的“差异”Rs是[X,Y,Z]。因此，至少象征性地，我们可以这样写：

列出差异样本

让我们用 L、L 0、L 1和 L 2来表示由第二个子句中的这种差异所描述的列表：

列出差异

在代数上，我们可以将 L 视为其他列表的“总和”（串联）：

L 是总和

对于其他列表，我们有：

L0

L1

L2

所以，总的来说，我们有：

全部的

请注意，理解这一点不需要递归。相反，重要的是论点之间的关系。就个人而言，我也发现这样的推导不如反过来有用：我认为在编写此类代码时注意这种模式更为重要，因为这意味着您可以改用 DCG 表示法，并显着减少参数的数量被传递！

于 2018-12-02T09:09:19.223 回答
0 
s(  A, A).               % s(0).
s(  A,       D) :-       % s(n):-
  l(A, B),               %   before,
     s(B, C),            %   s(n-1),
  r(      C, D).         %   after.

l(  [a | A], 
         A ).
r(  [b | B], 
         B ).

一起定义

%% 1 
s(          [a , b | B1], B1):-
          l([a | A1],
                 A1 ),
              s( A1,      %s0%
                 A1 ),    %s0%
          r(    [b | B1],
                          B1 ).

和

%% 2 
s(      [a , a , b , b | B2], B2):-
      l([a | A2],
             A2 ),
          l([a | A1],              %s1%
                 A1 ),             %s1%
              s( A1,      %s0%     %s1%
                 A1 ),    %s0%     %s1%
          r(    [b | B1],          %s1%
                     B1 ),         %s1%
      r(            [b | B2],
                              B2 ).

和

%% 3 
s(  [a , a , a , b , b , b | B3], B3):-
  l([a | A3],
         A3 ),
      l([a | A2],                            %s2%
             A2 ),                           %s2%
          l([a | A1],              %s1%      %s2%
                 A1 ),             %s1%      %s2%
              s( A1,      %s0%     %s1%      %s2%
                 A1 ),    %s0%     %s1%      %s2%
          r(    [b | B1],          %s1%      %s2%
                     B1 ),         %s1%      %s2%
      r(            [b | B2],                %s2%
                         B2 ),               %s2%
  r(                    [b | B3],
                                  B3 ).

等等等等。

于 2018-12-02T12:24:36.470 回答