Convertir foncteur Prolog à Functor avec une différence liste

Question

Je travaille sur mes devoirs pour Prolog (SWI) mais ne peut pas comprendre comment obtenir ce fait:

Je foncteur:

palindrome([]). 
palindrome([_]). 
palindrome([A|T]) :- 
     append(Middle,[A],T), 
     palindrome(Middle). 

qui indique si une liste donnée est un palindrome.

Pour mes devoirs je dois écrire un foncteur palindrome/2 sans append/3 et avec des listes de différence.

Je sais qu'une liste de différence est une forme de [Y|X]-X, mais je ne comprends pas comment l'utiliser et comment cela peut remplacer le foncteur append.

Quelqu'un peut-il m'expliquer cela?

Answer 1

Pour une liste donnée de longueur n, votre solution a besoin de quelques O ( n) inférences: n (en fait n/2) pour palindrome/1 et i pour chaque append/3 qui cherche et compare simplement la fin. La manière la plus simple de reformuler votre définition utilise des grammaires (DCG) qui constituent un moyen pratique d'utiliser des listes de différences. Notez que chaque règle de grammaire correspond à une clause de votre programme.

palindrome --> 
    []. 
palindrome --> 
    [_]. 
palindrome --> 
    [A], 
    palindrome, 
    [A]. 

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

Pour plus de commodité, voici la même grammaire écrite plus compacte:

palindrome --> [] | [_] | [A], palindrome, [A]. 

Maintenant, comment ces règles de grammaire mises en œuvre? Le plus simple est de regarder la définition réelle avec listing(palindrome).

?- listing(palindrome). 
palindrome(A, A). 
palindrome([_|A], A). 
palindrome([C|A], D) :- 
    palindrome(A, B), 
    B=[C|D]. 

Donc c'est maintenant votre définition en utilisant des listes de différences.

Answer 2

Écrivez-le vous-même. Vous avez

palindrome([]).   % palindrome(Z-Z). 
palindrome([_]).   % palindrome([_|Z]-Z). 
palindrome([A|T]) :-  % palindrome([A|T]-Z):- 
    append(Middle,[A],T), % append(Middle-Z2,[A|Z3]-Z3,T-Z), 
    palindrome(Middle).  % palindrome(Middle-Z2). 

Append pour les listes cultés est append(A-B,B-C,A-C), de sorte que l'appel append nous donne Z2=[A|Z3], Z3=Z, Middle=T, et ainsi (écrire les deux moitiés d'une dif-liste comme deux arguments pour le prédicat),

palindrome(Z,Z). 
palindrome([_|Z],Z). 
palindrome([A|T],Z) :- 
    palindrome(T, [A|Z]). 

maintenant, vous pouvez l'exécuter

10 ?- palindrome(X,[]). 

X = [] ; 
X = [_G340] ; 
X = [_G340, _G340] ; 
X = [_G340, _G346, _G340] ; 
X = [_G340, _G346, _G346, _G340] ; 
.... 

11 ?- X=[a,b,c|_],palindrome(X,[z]). 

X = [a, b, c, b, a, z] ; 
X = [a, b, c, c, b, a, z] ; 
X = [a, b, c, _G460, c, b, a, z] ; 
X = [a, b, c, _G460, _G460, c, b, a, z] ; 
.... 

16 ?- palindrome([1,2,2,1,0],Z). 

Z = [1, 2, 2, 1, 0] ; 
Z = [2, 2, 1, 0] ; 
Z = [0] ; 
No 

Bien sûr, les règles DCG fournir une interface confortable à la différence des listes.