Списки

Список — досить широко використовувана структура даних в області числового програмування. Список — це впорядкована послідовність елементів, яка може мати довільну довжину. Ознака впорядкований вказує на те, що порядок елементів в послідовності є важливим. Елементами списку можуть бути будь-які терми — константи, змінні, структури, які включають, звичайно, і інші списки.

Списки можуть бути представлені як спеціального виду дерево. Список — це будь-який порожній список, що не містить жодного елементу, або структура, що має дві компоненти: голову і хвіст списку. Кінець списку зазвичай представляють як хвіст, який є порожнім списком. Порожній список записують як [ ] — відкриваюча квадратна дужка, за якою йде закриваюча квадратна дужка. Голова і хвіст списку є компонентами функтора, що позначається точкою ‘.’. Так, список, що складається з одного елементу 'а', є.(а, [ ]), а його представлення у вигляді дерева має вигляд

Списки є впорядкованими послідовностями елементів, так що список а.b відрізняється від списку b.а. Деякі люблять записувати деревовидні діаграми списків у вигляді дерева, що «росте» зліва направо, гілки якого спрямовані вниз. Приведений вище список, представлений діаграмою у вигляді такої «виноградної лози», виглядає так: [а, VI, b, [X, Y]]

Приклад зіставити два задані списки, конкретизуючи змінні. [білий | Q], [P | кінь] à Р= білий Q= кінь.

Існує ще одна сфера застосування списків — це представлення рядків літер. Іноді виникає необхідність у використанні рядків літер для друку або вводу тексту. Якщо рядок літер поміщений в подвійні лапки, то цей рядок представляється як список кодів, що відповідають літерам рядка. Для кодування літер використовується код ASCII, Наприклад, рядок "system" перетвориться в Пролозі в наступний список: [115, 121, 115, 116, 101, 109].

 

17. Приналежність елементів списку.

Припустимо, що є деякий список, в якому X означає його голову, a Y — хвіст списку. Нагадаємо, що такий список ми можемо записати так: [X | Y]. Цей список міг би містити, марки автомобілів форд:

[fiesta,fusion,focus,tscont].

Тепер припустимо, що ми хочемо визначити, чи міститься деяка марка у вказаному списку. У Пролозі це можна зробити, визначивши, чи співпадає ця кличка з головою списку. Якщо співпадає, то наш список завершується успіхом. Якщо ні, то ми перевіряємо, чи є марка в хвості початкового списку. Це означає, що знову перевіряється голова, але вже хвоста списку. Потім перевіряється голова чергового хвоста списку. Якщо ми доходимо до кінця списку, який буде порожнім списком, то наш пошук завершується невдачею: вказаної марки в початковому списку немає.

Для того, щоб записати усе це на Пролозі, спочатку потрібно встановити, що між об'єктом і списком, в який цей об'єкт може входити, існує відношення. Це відношення, що називається відношенням приналежності.

Для запису цього відношення ми використовуватимемо предикат належить: цільове твердження належить(Х,Y) є істинним («виконується»), якщо терм, пов'язаний з X, є елементом списку, пов'язаного з Y. Є дві умови, які потрібно перевірити для визначення істинності предиката.

· Перша умова говорить, що X буде елементом списку Y, якщо X співпадає з головою списку Y. На Пролозі цей факт записується таким чином: належить(Х,[Х |_]).

Цей запис констатує, що X є елементом списку, який має X в якості голови. Ми використали анонімну змінну ‘_’ для позначення хвоста списку. Це зроблено тому, що ми ніяк не використовуємо хвіст списку в цьому окремому факті.

· Друге правило говорить про те, що X належить списку за умови, що він входить в хвіст цього списку, що позначається через Y. І немає кращого шляху, ніж використати той же самий предикат належить для того, щоб визначити, чи належить X хвосту списку! У цьому і полягає суть рекурсії. На Пролозі це виглядає так: належить(Х,[_ | Y]):— належить(Х,Y).

І констатує, що X є елементом списку, якщо X є елементом хвоста цього списку. Ми використали анонімну змінну ‘_’ оскільки нас не цікавить ім'я змінної, що означає голову списку. Два цих правила в сукупності визначають предикат для відношення приналежності.

Для предиката належить насправді є два типи граничних умов. Перша гранична умова для предиката належить розізнається першим твердженням, яке приведе до припинення пошуку в списку, якщо перший аргумент предиката належить співпадає з головою списку, що відповідає другому аргументу. Друга гранична умова зустрічається, коли другий аргумент предиката належить є порожнім списком.

Одна важлива проблема, на яку слід звертати увагу в рекурсивних визначеннях,— це лівобічна рекурсія. Вона виникає у разі, коли правило породжує під ціль, по суті еквівалентну початковій меті, яка стала причиною використання цього правила.

Для наведеного прикладу є простий спосіб усунення помилки — помістити факт перед правилом, а не після нього.

 

 

18. Приклад: перетворення речень.

Розглянемо програму на Пролозі, яка у відповідь на введену з терміналу пропозицію (англійською мовою) друкує іншу пропозицію, що представляє перетворене вхідне речення. Ця програма для «відповідей» програмістові могла б підтримувати наступний діалог:

Ви: you are a computer (Ви – ЕОМ)

Пролог: і am not a computer (Я – не ЕОМ)

Ви: do you speak french (Ви говорите французькою?)

Пролог: no і speak german (Ні, я говорю німецькою)

Для цього досить просто послідовно виконувати наступні дії:

1. Ввести речення, набране користувачем на терміналі.

2. Замінити кожне входження слова you на слово і.

3. Аналогічним чином замінити are на am not.

4. Замінити french на german.

5. Замінити do на no.

Програма на Пролозі, що перетворює одну пропозицію англійської мови в іншу,

може бути реалізована таким чином. Нам слід визначити предикат, що називається перетворити. Перетворити(Х, Y) означає, що пропозиція X може бути перетворена в пропозицію Y. Пропозиції X і Y зручно представляти у вигляді списків атомів, що означають слова, так що пропозиції можуть бути записані таким чином: [this, is, a, sentence] (ця деяка пропозиція).

Визначивши предикат перетворити, звертатися до Прологу з питаннями виду

?- перетворити([(do, you, know, french],X). (Чи знаєте ви французьку?)

Пролог

X=[no, i, know, german] (ні, я знаю німецький).

Оскільки аргументами предиката перетворити є списки, то якщо початковий список порожній, ми скажемо, що порожній список перетвориться в порожній список:

перетворити([], []).

Далі нам слід розібратися в тому, що основні дії предиката перетворити полягають в наступному:

1. Замінити голову вхідного списку відповідним словом і помістити це слово у вихідний список в якості голови.

2. Перетворити хвіст вхідного списку і зробити його хвостом вихідного списку.

3. Якщо ми досягли кінця вхідного списку, то до вихідного списку більше нічого додавати не потрібно, і ми можемо завершити вихідний список порожнім списком [].

Тепер слід сказати, що означає «замінити» одне слово на інше. Це може бути зроблено за наявності у базі цих фактів виду замінити(Х, Y), що означають, що слово X може бути замінене словом Y. У кінці бази даних слід помістити факт - «пастку», оскільки якщо слово не замінюється іншим словом, то його слід замінити самим собою. Роль такого факту-пастки виконує факт замінити(Х, Х), який означає, що слово X замінюється самим собою. Нижче приведена база даних, що забезпечує вказані вище заміни слів:

замінити(you, i).

замінити(are,[am, not]).

замінити(french, german).

замінити(do, no).

замінити(Х, Х). /* це факт-пастка */

Тепер можна перекласти приведений вище текст псевдо-Пролозі в справжню програму на Пролозі, пам'ятаючи, що запис [А|В] означає список, що має голову А і хвіст В. Ми отримуємо щось подібне наступному:

перетворити([],[]).

перетворити([Н|Т],[Х|Y]):-

замінити(Н, X), перетворити(Т, Y).

19. Приклад: впорядкування за абеткою.

Розглянемо предикат, який ми назвемо менше. Якщо предикат менше(X,Y) використовується як цільове твердження, то він істинний (тобто узгоджується з базою даних), якщо X і Y означають атоми і X за абеткою передує Y. Тоді, предикат менше(кавун, буквар) істинний, а менше(вітер, автомобіль) ні. Так само має бути неправдивий і предикат менше(картина, картина). Порівнюючи два слова, ми порівнюємо їх послідовно, буква за буквою і при порівнянні кожної букви визначаємо, яка з наступних умов має місце:

1. Досягнутий кінець першого слова, але не досягнутий кінець другого слова. Наприклад, у випадку менше(ліс, лісник)- предикат менше повинен вважатися істинним (тобто погодженим з базою даних).

2. Чергова літера в першому слові передує в алфавіті відповідній літері в другому слові. Наприклад, менше (слово, слон). Буква 'в' в слові слово передує в алфавіті букві 'н' в слові слон - предикат менше істинний.

3. Літера в першому слові співпадає з відповідною літерою в другому слові. Слід використати предикат менше для порівняння літер, що залишилися, в обох словах. Наприклад, якщо менше(стіл, сніг), то, оскільки обидва аргументи розпочинаються з букви 'с', необхідно взяти як наступну мету менше(тіл, ніг).

4. Одночасно досягнутий кінець першого і другого слів, як, наприклад, у випадку менше(яблуко, яблуко). Предикат меншим має бути неправдивим, оскільки обидва слова є однаковими.

5. Оброблені усі літери другого слова, але ще залишилися літери в першому слові, як, наприклад, у випадку менше(алфавітний, алфавіт). У такій ситуації предикат меншим має бути неправдивим.

Представлятимемо слова у вигляді списків літер (цілих чисел з деякого діапазону). Для цього потрібний спосіб перетворення атома в список літер. Цю функцію виконує вбудований предикат Прологу name(ім'я). Цільове твердження name(X,Y) узгоджується з базою даних, коли атом, що є значенням X, складається з літер, коди яких утворюють список, що є значенням Y (використовуються коди ASCII).

Першим твердженням у визначенні предиката менше є наступне правило:

менше(X,Y):- name(X, L), name(Y,M), менше_1(L,M).

Це правило спочатку перетворить слова в списки, використовуючи предикат name, і потім за допомогою предиката менше_1 (буде визначений нижче) порівнює списки на відповідність алфавіту. Визначення предиката менше_1 складається з тверджень, що реалізовують приведений вище набір умов. Перша умова є істинною, коли перший аргумент є порожній список, а другий аргумент — це довільний непорожній список:

менше_1([], [_|_]).

Друга умова записується таким чином:

менше_1([Х |_],[У|_]):- Х<Y.

Збираючи усі правила разом, отримаємо

менше(X,Y):- name(X,L), name(Y,M), менше_1(L,M).

менше_1([], [_|_]).

менше_1([Х|_], [Y|_]):- X<Y.

менше_1([Р|Q],[R|S]):- P=R, менше_1(Q,S).

 

20. Використання предиката приєднати і специфікація деталей.

Предикат приєднати, що опрацьовує списки, використовується для створення нового списку, що є результатом з'єднання двох інших списків. Наприклад, вірний наступний факт:

приєднати([a,b,c], [3,2,1], [a,b,c, 3,2,1]).

Предикат приєднати найчастіше використовується для створення нового списку в результаті конкатенації двох інших списків, як в наступному прикладі:

?- приєднати([alpha, beta],[gamma, delta],X).

X=[alpha, beta, gamma, delta]

Предикат приєднати має наступне визначення:

приєднати([], L, L).

приєднати([Х|L1],L2,[Х|L3]):- приєднати(L1, L2, L3).

Вихід на граничну умову відбувається, коли перший аргумент є порожнім списком. Будь-який список, приєднаний до порожнього списку, дає той же самий список. У усіх інших випадках виконуватиметься друге правило, сенс якого можна описати словами таким чином:

1. Перший елемент першого списку (X) завжди буде і першим елементом третього списку.

2. Хвіст третього аргументу (L3) завжди представлятиме результат приєднання другого аргументу (L2) до хвоста першого списку (L1).

3. Для приєднання одного списку до іншого, про що йшла мова в пункті 2, необхідно використати предикат приєднати.

4. Оскільки при кожному зверненні до правила віддаляється голова списку, що є першим аргументом, то поступово цей список буде вичерпаний і стане порожнім, так що станеться вихід на граничну умову.

Проте якщо ми хочемо зібрати деякий вузол, то необхідно застосувати цей процес до кожної складової частини вузла. Визначимо предикат частина(X,Y), де X — ім'я частини, а Y — список деталей, необхідних для її зборки.

Предикат список_частин бере список частин (з другого аргументу факту вузол, представленого вище) і застосовує предикат частина до кожної частини в списку. Після виклику самого себе, необхідного для обробки хвоста списку, предикат список_частин повинен склеїти отримані списки разом, використовуючи предикат приєднати:

список_частин([Р|Хвіст], Повний_список):- частина(Р, Частини_голови),

список_частин(Хвіст, Частини_хвоста),

приєднати(Частини_голови, Частини_хвоста, Повний_список).

 

21. Породження множинних рішень.

Наприклад, є наступні факти:

батько(марія, василь).

батько(іван, василь).