我想出了在列表中测试等于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).

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

如

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

这涉及递归和差异列表.任何人都可以解释底层递归检查如何与b的步骤相等.

Answer 1

如果您在较低级别对其进行推理,则列表差异并不容易理解.

因此,我首先推荐一个更高级别的视图:

总而言之,您的谓词s/2描述了一个列表.我说"描述",因为它不仅"检查",而且如果我们想要也生成并完成这样的列表!

我们可以将每个目标读s/2作" 然后列表中的一些元素".

所以,暂时忘掉这些论点并考虑谓词的抽象结构.我(-->)/2现在使用而不是(:-)/2明确表示我正在讨论谓词的一个小变体,我只是忽略了这些参数:

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

我们可以做同样的l/2和r/2:

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

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

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

所以,现在很清楚:s//0描述一个空的列表,或者:

由于l//0描述了具有单个元素的列表a,并r//0描述了具有单个元素的列表b,因此很明显,在s//0描述的列表中,始终存在相同数量的as和bs.

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

?- phrase(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 ₀,L ₁和L ₂表示由第二个条款中的这些差异描述的列表:

在代数上,我们可以将L视为其他列表的" 总和 "(连接):

对于其他列表,我们有:

所以,总的来说,我们有:

请注意,理解这一点不需要递归.相反,重要的是争论之间的关系.就个人而言,我也发现这样的推导没有比反向更有用:我认为在编写这样的代码时注意这种模式更为重要,因为这意味着你可以使用DCG符号,并显着减少参数的数量.传遍了!