Рекурсивный предикат Пролог для реверса / палиндрома

Question

1. Могу ли я получить рекурсивный предикат Prolog, имеющий два аргумента, называемый обратным, который возвращает инверсию списка:

   Пример запроса и ожидаемый результат:

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

2. Рекурсивный предикат Пролога с двумя аргументами, называемый palindrome, который возвращает истину, если данный список является палиндромом.

   Пример запроса с ожидаемым результатом:

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

Answer 1

Не существует эффективного способа определения 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). 

Answer 2

Объявление 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 3

Просто для любопытства здесь приведена рекурсивная реализация reverse / 2, которая не использует вспомогательные предикаты и все же переворачивает список.Вы можете считать это обманом, поскольку он использует reverse / 2, используя списки и структуру - / 2 в качестве аргументов.

reverse([], []):-!.
reverse([], R-R).
reverse(R-[], R):-!.
reverse(R-NR, R-NR).
reverse([Head|Tail], Reversed):-
  reverse(Tail, R-[Head|NR]),
  reverse(R-NR, Reversed).

Answer 4

conca([],L,L).
conca([X|L1],L2,[X|L3]):- conca(L1,L2,L3).
rev([],[]).
rev([X|Y],N):- rev(Y,N1),conca(N1,[X],N).
palindrome([X|Y]):- rev([X|Y],N),equal([X|Y],N).
equal([X],[X]).
equal([X|Y],[X|Z]):- equal(Y,Z).