Конвертировать функтор Пролог в функтор с разностными списками

Question

Я работаю над домашней работой для Пролога (SWI), но не могу понять, как это сделать:

У меня есть функтор:

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

который сообщает, является ли данный список палиндромом.

Для моей домашней работы я должен написать функтор palindrome/2 без append/3 и со списками различий.

Я знаю, что список различий является формой [Y|X]-X, но я не понимаю, как использовать это и как это может заменить функтор добавления.

Может кто-нибудь, пожалуйста, объясните мне это?

Answer 1

Для заданного списка длины n вашему решению требуются некоторые выводы O (n²): n (фактически n / 2) для palindrome/1 и я для каждого append/3 который просто ищет и сравнивает конец.

Самый простой способ переформулировать ваше определение - использовать грамматики (DCG), которые являются удобным способом использования списков различий. Обратите внимание, что каждому правилу грамматики соответствует предложение в вашей программе.

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

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

Для удобства вот та же грамматика, написанная более компактно:

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

Теперь, как реализованы эти грамматические правила? Самый простой способ - посмотреть на фактическое определение с помощью listing(palindrome),

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

Так что теперь это ваше определение с использованием списков различий.

Answer 2

Просто запишите это сами. У тебя есть

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

Добавить для dif-списков append(A-B,B-C,A-C)так что вызов append дает нам Z2=[A|Z3], Z3=Z, Middle=Tи так (записав две половины dif-списка в качестве двух аргументов для предиката),

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

Теперь вы можете запустить его

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

Конечно, правила DCG предоставляют удобный интерфейс для списков различий.