4

我正在为 Prolog (SWI) 做作业，但不知道如何完成这项工作：

我有函子：

palindrome([]).
palindrome([_]).
palindrome([A|T]) :-
      append(Middle,[A],T),
      palindrome(Middle).

它告诉给定列表是否是回文。

对于我的作业，我必须编写一个palindrome/2没有append/3和有差异列表的函子。

我知道差异列表是 的一种形式[Y|X]-X，但我不明白如何使用它以及它如何替换附加函子。

有人可以向我解释一下吗？

4

2 回答 2

6

对于长度为n的给定列表，您的解决方案需要一些 O( n 2 ) 推论：n（实际上是n/2）代表palindrome/1 和i代表每个append/3简单地搜索和比较结尾。

重新制定定义的最直接方法是使用语法 (DCG)，这是使用差异列表的便捷方式。请注意，每个语法规则都对应于程序中的一个子句。

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

palindrome(T) :-
   phrase(palindrome,T).

为方便起见，下面是写得更简洁的相同语法：

palindrome --> [] | [_] | [A], palindrome, [A].

现在，这些语法规则是如何实现的？最简单的方法是使用 . 查看实际定义listing(palindrome)。

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

所以现在这是您使用差异列表的定义。

于 2012-03-13T13:08:09.027 回答
2

自己写下来就好了。你有

palindrome([]).           % palindrome(Z-Z).
palindrome([_]).          % palindrome([_|Z]-Z).
palindrome([A|T]) :-      % palindrome([A|T]-Z):-
  append(Middle,[A],T),   %   append(Middle-Z2,[A|Z3]-Z3,T-Z),
  palindrome(Middle).     %   palindrome(Middle-Z2).

附加为 diff-lists 是append(A-B,B-C,A-C)，所以 append 调用给了我们Z2=[A|Z3], Z3=Z, Middle=T，所以（写出一个 diff-list 的两半作为谓词的两个参数），

palindrome(Z,Z).
palindrome([_|Z],Z).
palindrome([A|T],Z) :-
  palindrome(T, [A|Z]).

现在你可以运行它了

10 ?- palindrome(X,[]).

X = [] ;
X = [_G340] ;
X = [_G340, _G340] ;
X = [_G340, _G346, _G340] ;
X = [_G340, _G346, _G346, _G340] ;
....

11 ?- X=[a,b,c|_],palindrome(X,[z]).

X = [a, b, c, b, a, z] ;
X = [a, b, c, c, b, a, z] ;
X = [a, b, c, _G460, c, b, a, z] ;
X = [a, b, c, _G460, _G460, c, b, a, z] ;
....

16 ?- palindrome([1,2,2,1,0],Z).

Z = [1, 2, 2, 1, 0] ;
Z = [2, 2, 1, 0] ;
Z = [0] ;
No

当然，DCG 规则为差异列表提供了一个舒适的界面。

于 2012-03-17T12:20:34.180 回答