Prolog - 在回溯时生成交替符号: [a] ; [a,b]; [a,b,a]; [a,b,a,b]

Question

我思考了很久，但仍然搞不清楚。 是否有可能编写一个脚本，使用回溯算法生成这种格式的列表：

[a]
[a,b]
[a,b,a]
[a,b,a,b]
...

我已经制作了一个每次生成两个元素的脚本，但是当我尝试制作一个能够交替生成"a"、"b"的脚本时，我的头开始疼了。

以下是每次生成两个元素的脚本：

ab([a]).
ab([b,a|T]):-ab([a|T]).
ab([a,b|T]):-ab([b|T]).

- Dimitur Epitropov

Answer 1

在描述列表时，始终考虑使用DCG符号。

这使得聚焦您想要描述的本质变得非常方便，而不需要那么多额外的变量和参数。

例如，请考虑：

abs --> [a]， abs_rest。
abs_rest --> []。
abs_rest --> [b]，([] | abs)。

示例查询和答案：

？- phrase(abs, ABs)。
ABs = [a];
ABs = [a，b]；
ABs = [a，b，a]；
ABs = [a，b，a，b]；
ABs = [a，b，a，b，a]；
ABs = [a，b，a，b，a，b]。

有关此方便形式的更多信息，请参见dcg！

- mat

---

这很有趣，以前没有遇到过，而且在我的大学课程中肯定没有学过，这是宝贵的信息！无论如何，我正在训练我的递归技能并制作生成脚本，我不确定 DCG 是否会被接受在我的考试中，所以我仍在传统方式下寻找解决方案 :) - Dimitur Epitropov

如果你所说的“传统方式”是指“不太易读的方式”，那么只需使用以下查询来获取对应于DCG的纯Prolog代码：?- listing(abs//0), listing(abs_rest//0). 你可以将其输出结果交给你的教师，知道有一个更好的解决方案，但你可能不被允许使用，因为为什么要使用适当的形式化语言，当有一种更复杂的表达方式呢？ - mat

“传统”这个词并不适合描述我所需要的东西。 我正试图仅使用列表的“头”、“尾”和“递归”特性来解决它。代码如下： ab([a]). ab([b,a|T]):-ab([a|T]). ab([a,b|T]):-ab([b|T]). - Dimitur Epitropov

正如我所说：加载上面的DCG，然后使用listing/1使您的Prolog系统输出您也可以使用的低级代码。在内部，您的系统将DCG编译为普通的Prolog，并且您可以使用listing/1检查生成的代码（如果您的系统提供它）。 - mat

谢谢Mat！看来我昨天已经有点累了，没有第一时间注意到，现在一切都清楚了 :) - Dimitur Epitropov

Answer 2

我同意@mat的观点，对于这种类型的问题，应尽可能使用dcg。

以下是另一组规则。

abs --> [a].
abs --> [a,b].
abs --> [a,b], abs.

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

有趣的是，这些规则始于这个变体。

abs2 --> [].
abs2 --> [a].
abs2 --> [a,b], abs2.

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

这是在SWI-Prolog中使用确定性子句语法的练习之一。

如果您不想使用DCG，那么我同意@mat的建议，建议您使用listing/1来查看标准Prolog语法中的DCG。

listing(abs).

abs([a|A], A).
abs([a, b|A], A).
abs([a, b|A], B) :-
        abs(A, B).

listing(abs2).  

abs2(A, A).
abs2([a|A], A).
abs2([a, b|A], B) :-
        abs2(A, B).

作为普通的 Prolog 规则，它们可以被用作这样：

abs(X,[]).
X = [a] ;
X = [a, b] ;
X = [a, b, a] ;
X = [a, b, a, b] ;
X = [a, b, a, b, a] ;
X = [a, b, a, b, a, b] ;
X = [a, b, a, b, a, b, a]

abs2(X,[]).
X = [] ;
X = [a] ;
X = [a, b] ;
X = [a, b, a] ;
X = [a, b, a, b] ;
X = [a, b, a, b, a] ;
X = [a, b, a, b, a, b] 

- Guy Coder

---

您链接的文本使用了过时的术语，请使用维护更好的文档。 - mat

@mat 我理解你指的是，“在SWI-Prolog中使用确定性语法规则”。我添加了链接来展示还有其他类似的问题，这基本上就是添加链接的原因。 - Guy Coder

谢谢伙计，感谢进一步解释，非常感激！ - Dimitur Epitropov

Answer 3

你写的谓词太笼统了：

?- ab([b,a]).
true

原因是以下规则。

ab([b,a|T]) :-
  ab([a|T]).

有人可能会说，您描述的是中间结果，这并不能解决您实际问题。要解决这个问题，您可以说明一个ab序列以a开头，其余部分必须是ba序列，其中ba序列再次根据ab序列进行定义：

ab([a]).
ab([a|Xs]) :-
    ba(Xs).

ba([b]).
ba([b|Xs]) :-
    ab(Xs).

或者，你可以把abs看作一个状态机，当最后一个元素是b时产生a，反之亦然。如果我们引入一个额外的参数来追踪历史记录，我们就得到了：

abs(a,[a]).
abs(b,[b]).
abs(a,[a|Xs]) :-
    abs(b,Xs).
abs(b,[b|Xs]) :-
    abs(a,Xs).

现在我们定义一个ab序列，其最后一个元素是a。

ab(Xs) :-
    abs(a,Xs).

玩得开心 :)

- lambda.xy.x