我想出了用于测试列表中 a 和 b 是否相等的代码，但无法理解底层递归

Question

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

l([a|A],A).

r([b|A],A).

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

比如

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

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

Answer 1

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

因此，我先推荐一个更高层次的观点：

总而言之，您的谓词 s/2 描述了一个列表。我说 "describes"，因为它不仅 "checks"，而且生成和完成这样的列表，如果我们想要的话！

我们可以将 s/2 的每个目标读作 "and then some element(s) of the list"。

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

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

我们可以对 l/2 和 r/2 做同样的事情：

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

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

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

所以，现在很清楚了：s//0 描述的列表要么是空，要么是：

l//0
然后 s//0
然后 r//0描述的列表。

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

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

?- phrase(s, Ls).
Ls = [] ;
Ls = [a, b] ;
Ls = [a, a, b, b] ;
Ls = [a, a, a, b, b, b] .

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

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

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

让我们用 L、L₀、L₁ 和 L₂ 表示在第二个子句中由此类差异描述的列表：

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

对于其他列表，我们有：

所以，我们总共有：

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

Answer 2

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 ).

等等等等。

我想出了用于测试列表中 a 和 b 是否相等的代码，但无法理解底层递归

I figured out the code for testing equal a's and b's in a list but can't understand the underlying recursion

list

prolog

difference-lists