Recursive Prolog predykatu do tyłu/palindromu

Question

1. mogę dostać rekurencyjną Prolog orzecznik posiadający dwa argumenty, zwanej odwróconej, która zwraca odwrotność listy:

   zapytanie Sample i oczekiwany wynik:

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

2. Rekurencyjny predykat Prologu z dwoma argumentami o nazwie palindrome, który zwraca wartość true, jeśli podana lista jest palindromem. Zapytanie

   próbki z oczekiwanego rezultatu:

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

Answer 1

Ad 1: To jest niemożliwe do zdefiniowania reverse/2 jako ( bezpośrednio edycji thx do @repeat tail) rekurencyjnego orzecznika - jeśli nie zezwalają orzeczenie pomocnicze.

Ad 2:

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

Ale najprostszym sposobem jest zdefiniowanie takich predykatów z DCGs:

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

Nie jest skutecznym sposobem definiowania reverse/2 z jednym rekurencyjnej definicji bez korzystania jakiś pomocniczy predykat. Jeśli jednak mimo wszystko jest dozwolone, to proste rozwiązanie, które nie opiera się na żadnych wbudowanych ins jak append/3 (i powinny być stosowane do większości implementacji Prolog) byłoby użyć listy akumulatora, co następuje:

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 jest orzecznikiem odwrócenie, które po prostu „delegatów” (lub, okłady) wersja akumulator opartych o nazwie rev-acc/2, który rekursywnie dodaje elementy z listy wejściowej do akumulatora w odwrotnej kolejności.

Running to:

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

i rzeczywiście jak @false zwracał już uwagę (+1),

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

Answer 3

Tylko dla ciekawości tu idzie rekurencyjną implementację odwrotnej/2, który nie użyj pomocniczych predykatów i nadal odwraca listę. Możesz uważać to za oszustwo, ponieważ używa odwrotnego/2 list i struktury -/2 jako argumentów.

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