Prolog

Question

我想了很多，想不通。是否可以制作一个带有回溯的脚本以这种格式生成列表：

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

我制作了一个一次生成两个元素的程序，但我开始头疼，试图制作一个生成 "a" 的程序，然后是下一次 "b" 和下一次 "a" 等等。

这是一次两个元素的脚本：

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

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了解更多关于这种方便的形式主义的信息！

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]

这是Using Definite Clause Grammars in 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]

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

玩得开心:)

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

Prolog - Generate alternating symbols on backtrack: [a] ; [a,b]; [a,b,a]; [a,b,a,b]

list

dcg