list - 我找出了测试列表中 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

如果您在较低层次上进行推理，则列表中的差异并不容易理解。

因此，我首先推荐一个更高层次的 View :

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

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

因此，暂时忘记参数并考虑谓词的抽象结构。我现在使用 (-->)/2 而不是 (:-)/2 来明确我正在谈论谓词的一个小变体，我只是忽略参数:

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

我们可以对 l/2 和 r/2 执行相同的操作:

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

这就是谓词在列表的抽象、高级 View 中所描述的内容。在这种表示法中，我不需要费力地处理列表差异和争论。相反，我可以直接关注程序的本质。

很明显，您可以轻松地将此类高级代码转换为您发布的代码。事实上，如果您查阅以下代码，Prolog 会为您执行此转换:它称为DCG 表示法。请参阅dcg了解更多信息。

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

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

因为l//0描述了具有单个元素a的列表，而r//0描述了具有单个元素的列表b，很明显，在s//0描述的列表中，a和的数量总是相同的bs。

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

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

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

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

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

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

从代数角度来说，我们可以将 L 视为其他列表的“总和”(串联):

对于其他列表，我们有:

因此，我们总共有:

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