Пролог - Палиндром Функтор

Question

Я пытаюсь написать предикат palindrome/1 в Прологе, который является истинным, если и только если его входные данные списка состоят из палиндромного списка.

например:

?- palindrome([1,2,3,4,5,4,3,2,1]).

верно.

Есть идеи или решения?

Answer 1

Список палиндромов - это список, который читает то же самое в обратном направлении, поэтому вы можете повернуть список в обратном направлении, чтобы проверить, дает ли он тот же список:

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

Answer 2

Похоже, что все голосуют за реверс / 2 решение.Полагаю, вы, ребята, имеете в виду решение с обратным / 2, которое равно O (n) из данного списка.Что-то с аккумулятором:

 reverse(X,Y) :- reverse(X,[],Y).

 reverse([],X,X).
 reverse([X|Y],Z,T) :- reverse(Y,[X|Z],T).

Но есть и другие способы проверки на палиндром.Я придумал решение, которое использует DCG.Можно использовать следующие правила:

 palin --> [].
 palin --> [_].
 palin --> [Border], palin, [Border].

Какое решение лучше?Что ж, давайте сделаем небольшую статистику с помощью команды профиля системы Prolog.Вот результаты:

Так что, возможно, решение DCG часто быстрее в положительном случае («радар»), ему не нужно строить весь обратный список, нонепосредственно перемещается в середину, а затем проверяет остальное во время выхода из своей собственной рекурсии.Но недостатком решения DCG является то, что оно недетерминировано.Некоторые измерения времени покажут больше ...

Пока

PS: статистика портов выполняется с помощью нового подключаемого отладчика Jekejeke Prolog:
http://www.jekejeke.ch/idatab/doclet/prod/en/docs/10_dev/10_docu/02_reference/04_examples/02_count.html

Но другой прологсистемы имеют аналогичные средства.Для получения дополнительной информации см. Столбец «Code Profiler»:
http://en.wikipedia.org/wiki/Comparison_of_Prolog_implementations

Answer 3

Это звучит как домашнее задание, но я просто не могу с собой поделать:

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

Технически, функтор пролога ничего не "возвращает".

Answer 4

Вы можете использовать:

palindrome([]).
palindrome([_]).
palindrome([X|Xs]):-append(Xs1,[X],Xs), palindrome(Xs1).

Answer 5

Другой способ сделать это с помощью DCG:

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

Вы можете проверить палиндром следующим образом:

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

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