我正在为 Prolog (SWI) 做作业,但不知道如何完成:
我有仿函数:
palindrome([]).
palindrome([_]).
palindrome([A|T]) :-
append(Middle,[A],T),
palindrome(Middle).
它告诉给定的列表是否是回文。
对于我的作业,我必须写一个仿函数
palindrome/2
没有 append/3
并带有差异列表。我知道差异列表是
[Y|X]-X
的一种形式,但我不明白如何使用它以及它如何替换附加仿函数。有人可以向我解释一下吗?
最佳答案
对于给定的长度为 n 的列表,您的解决方案需要一些 O(n2) 推理: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].
所以现在这是您使用差异列表的定义。
关于prolog - 将 Prolog 仿函数转换为具有差异列表的仿函数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9683776/