反向/回文的递归Prolog谓词

Question

1. 我是否可以获得具有两个参数的递归Prolog谓词,称为reverse,它返回列表的反转:

   示例查询和预期结果:

   ?- reverse([a,b,c], L).
   L = [c,b,a].
   

2. 两个参数的递归Prolog谓词,palindrome如果给定列表是回文,则返回true.

   具有预期结果的示例查询:

   ?- palindrome([a,b,c]).
   false.
   
   ?- palindrome([b,a,c,a,b]).
   true.
   

Answer 1

广告1:除非您允许辅助谓词,否则无法定义reverse/2为(直接编辑thx到@repeat:tail)递归谓词.

广告2:

palindrome(X) :- reverse(X,X).

但最简单的方法是使用DCG定义这样的谓词:

iseq([]) --> [].
iseq([E|Es]) --> iseq(Es), [E].

reverse(Xs, Ys) :-
   phrase(iseq(Xs), Ys).

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

palindrome --> [].
palindrome --> [E].
palindrome --> [E], palindrome, [E].

Answer 2

在reverse/2没有使用某些辅助谓词的情况下,没有一种有效的方法来定义单个递归定义.但是,如果允许这样做,那么一个不依赖于任何内置函数的简单解决方案append/3(并且应该适用于大多数Prolog实现)将使用累加器列表,如下所示:

rev([],[]).
rev([X|Xs], R) :-
    rev_acc(Xs, [X], R).

rev_acc([], R, R).
rev_acc([X|Xs], Acc, R) :-
    rev_acc(Xs, [X|Acc], R).

rev/2是反转谓词,它简单地"委托"(或包装)基于累加器的版本rev-acc/2,该版本以递减的顺序将输入列表的元素添加到累加器中.

运行这个:

?- rev([1,3,2,x,4],L).
L = [4, x, 2, 3, 1].

事实上@false已经指出(+1),

palindrome(X) :- rev(X,X).