差异列表（Prolog）（逻辑编程）

Question

我在用纸笔解决差异列表问题时遇到了问题，而不是在 SWI Prolog 的帮助下（这几天我正在准备我的逻辑编程考试）。

这里是问题：

q(X) :- p(X - []).
p([X|Y] - Y).
p([X|Y] - Z) :- p(Y - [X|Z]).

明确给出查询的所有基本术语 t 的集合 ?- q(t)。成功。陈述一个正式的以封闭形式定义集合（即不使用递归定义）。

答案是：

{[t1, . . . , tn−1, tn, tn−1, . . . , t1] | n > 0, ti is a ground term for all i ∈ {1, . . . , n}}

我使用了 [1,2,3,2,1]，它给了我正确的预期答案。

我不明白解决这个问题的步骤是什么？

Answer 1

让 t = [t1,t2,t3, ... , tn] 成为一个列表。

如果 p(t - []). 成功，

q(t). 就会成功。

如果 p([t2,t3,...,tn] - [t1]). 成功，则

p(t - []). 成功（第三条规则）。

如果p([t3,...,tn] - [t2,t1])成功，

p([t2,t3,...,tn] - [t1]).成功，以此类推

这实际上只会在某一时刻应用第二条规则时才会成功（否则我们最终会调用 p([] - _).，它不匹配任何可用的规则），也就是说，如果我们有 p([ti,ti+1,...,tn] - [ti+1,...,tn])..

第二个列表[ti+1,...,tn]实际上是[ti-1,ti-2,...,t2,t1]根据第三条规则中的构造方式。

因此 q(t). 成功当且仅当 ti-1 = ti+1, ti-2 = ti+2, ..., t2 = tn-1, t1 = tn，这意味着 t = [t1,t2,...,ti-1,ti,ti-1,...,t2,t1].

difference list (Prolog)(Logic Programming)