Палиндром (домашнее задание)

Question

Я пытался написать программу Prolog, используя списки. Тем не менее, я должен использовать списки различий и вывод должен быть:

I-^й элемент списка совпадает с (n-i+1)^-ым элементом списка, а n - это длина списка. Например, [a,X,c,b,Y] должен дать X = b а также Y = a, Я не смог найти подобный пример палиндрома в других вопросах.

До сих пор я реализовал:

% length of the list 
len([], 0).
len([H|T], B) :-
   len(T, NT),
   B is NT + 1.

% return the ith element of the list 
match([H|_], 0, H) :-
   !.
match([_|T], N, H) :-
   N > 0,
   N1 is N-1,
   match(T, N1, H).

Однако я не смог завершить. Пожалуйста, помогите мне!

Answer 1

Используйте определенные грамматики предложения!

DCG, основная функция Prolog, упрощает использование списков различий, позволяя вам писать краткий и эффективный код без особых усилий!

Хотите узнать больше? Просто следуйте точкам:

• DCG имеет свой собственный тег на Stackru, dcg.

• https://en.wikipedia.org/ имеет обширную статью о DCG.

• Для краткого ознакомления прочитайте учебник по DCG Маркуса Триски!

Без дальнейших церемоний, давайте перейдем к коду:

палиндром -> [].
палиндром -> [_].
палиндром -> [X], палиндром, [X].

В качестве альтернативы, мы могли бы также использовать следующее более компактное определение:
палиндром -> [] | [_] | [X], палиндром, [X].

Готово. Давайте запустим несколько запросов! Сначала запрос ОП дал:

?- phrase(palindrome, [a,X,c,b,Y]).
   X = b, Y = a
;  false.

На немецком языке "кукуруза" называется "маис". Если мы поставим перед собой "сиам" (старое название "Королевство Таиланд"), мы получим восхитительный палиндром:

? - set_prolog_flag (двойные кавычки, символы).
правда.?- фраза (палиндром, "siamm ais").
   правда; ложный.?- фраза (палиндром, "siam ais"). % или ударить один средний символ "м"
   правда% ... для палиндрома нечетной длины; ложный.

Наконец, давайте не будем забывать о самом общем запросе:

?- phrase(palindrome, Xs).
   Xs = []
;  Xs = [_A]
;  Xs = [_A,_A]
;  Xs = [_A,_B,_A]
;  Xs = [_A,_B,_B,_A]
;  Xs = [_A,_B,_C,_B,_A]
...

---

На уровне пролога мы можем использовать встроенный предикат Пролог listing/1 Чтобы взглянуть на код, в который была переведена DCG - на этом уровне становится очевидным внутреннее использование списков различий:

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

true.