反向/回文的递归 Prolog 谓词 [英] Recursive Prolog predicate for reverse / palindrome

问题描述

1. 我能否得到一个递归 Prolog 谓词，它有两个参数，称为 reverse，它返回列表的倒数:

   示例查询和预期结果:

   <上一页>?- 反向([a，b，c]，L).L = [c,b,a].

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

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

   <上一页>?- 回文([a,b,c]).错误的.?- 回文([b,a,c,a,b]).真的.

解决方案

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

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)，

回文(X):- rev(X，X).

1. Can I get a recursive Prolog predicate having two arguments, called reverse, which returns the inverse of a list:

   Sample query and expected result:

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

2. A recursive Prolog predicate of two arguments called palindrome which returns true if the given list is palindrome.

   Sample query with expected result:

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

解决方案

There isn't an efficient way to define reverse/2 with a single recursive definition without using some auxiliary predicate. However, if this is nevertheless permitted, a simple solution which doesn't rely on any built-ins like append/3 (and should be applicable for most Prolog implementations) would be to use an accumulator list, as follows:

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 is the reversal predicate which simply 'delegates' to (or, wraps) the accumulator-based version called rev-acc/2, which recursively adds elements of the input list into an accumulator in reverse order.

Running this:

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

And indeed as @false has already pointed out (+1),

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

这篇关于反向/回文的递归 Prolog 谓词的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！