list - 回文(作业)

Question

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

列表的第 i 个元素与列表的第 (n-i+1) 个元素相同，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 在 StackOverflow 上有自己的标签，dcg .

en.wikipedia.org拥有广泛的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].

Done. Let's run a few queries! First, the query the OP gave:

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

在德语中，“ Jade 米”被称为 "mais" .如果我们把 "siam" (“泰王国”的旧称)在前面，我们得到一个美味的回文:

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

At last, let's not forget about the most general query:

?- 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我们可以使用内置的 Prolog 谓词 listing/1查看 DCG 被“翻译”成的代码——在这个级别，内部使用了 difference-lists变得明显:

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

true.