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

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

4 голосов
/ 13 марта 2012

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

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

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

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

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

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

Может кто-нибудь объяснить мне это?

Ответы [ 2 ]

6 голосов
/ 13 марта 2012

Для заданного списка длины n вашему решению требуются некоторые O ( n 2 ): n (на самом деле n / 2 ) для palindrome / 1 и i для каждого 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].

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

2 голосов
/ 17 марта 2012

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

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 для 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 предоставляют удобный интерфейс для списков различий.

...