回文（作业）

Question

我尝试使用列表编写 Prolog 程序。但是，我必须使用 差异列表 并且输出应该是：

列表的第i^th个元素与列表的第(n-i+1)^th个元素和n相同是列表的长度。例如，[a,X,c,b,Y] 应该给出 X = b 和 Y = a。我在其他问题中找不到类似的回文示例。

到目前为止我已经实现了：

% length of the list 
len([], 0).
len([H|T], B) :-
   len(T, NT),
   B is NT + 1.

% return the ith element of the list 
match([H|_], 0, H) :-
   !.
match([_|T], N, H) :-
   N > 0,
   N1 is N-1,
   match(T, N1, H).

但是，我无法完成。请帮助我！

Answer 1

使用定句语法！

DCG 是 Prolog 的主要功能，它使差异列表的使用变得简单——使您能够毫不费力地编写简洁的和高效代码！

想了解更多？只需按照以下要点：

DCG 在 Whosebug 上有自己的标签，dcg。
en.wikipedia.org has an extensive article on DCG.
要快速入门，请阅读 DCG primer by Markus Triska!

事不宜迟，让我们进入代码：

palindrome --> [].
palindrome --> [_].
palindrome --> [X], palindrome, [X].

% Alternatively, we could also use the following more compact definition:
palindrome --> [] | [_] | [X], palindrome, [X].

完成。让我们运行问几个问题！首先，OP 给出的查询：

?- phrase(palindrome, [a,X,c,b,Y]).
   X = b, Y = a
;  false.

在德语中，"corn"前面叫做"mais". If we put "siam"（"the Kingdom of Thailand"的旧称），我们得到一个delicious回文：

?- set_prolog_flag(double_quotes, chars).
true.

?- phrase(palindrome, "siammais").
   true
;  false.

?- phrase(palindrome, "siamais").       % or kick one middle 'm' character
   true                                 % ... for an odd-length palindrome
;  false.

最后，我们不要忘记最一般的查询：

?- phrase(palindrome, Xs).
   Xs = []
;  Xs = [_A]
;  Xs = [_A,_A]
;  Xs = [_A,_B,_A]
;  Xs = [_A,_B,_B,_A]
;  Xs = [_A,_B,_C,_B,_A]
...

在prolog-toplevel we can use the built-in Prolog predicate listing/1 to peek at the code the DCG was "translated" to—at this level the internal use of difference-lists上变得明显：

?- listing(palindrome//0).
palindrome(A, A).
palindrome([_|A], A).
palindrome([C|A], D) :-
    palindrome(A, B),
    B = [C|D].

true.

回文（作业）

Palindrome (homework)

list

prolog

palindrome

dcg

difference-lists