2.11. Списки

Список – це структура даних, яка може зберігати довільну кількість однотипних елементів, наприклад:

[ ]

[1, 2, 3, 4, 5]

[tom, ann, john, bob]

Першим наведено порожній список. Непорожній список складається з двох елементів – голови і хвоста. Голова – перший елемент списку, інша частина списку – хвіст. Наприклад, в останньому списку tom – це голова, [ann, john, bob] – це хвіст списку. Список можна явно поділити на голову і хвіст за допомогою вертикальної риски:

[tom | [ann, john, bob]]

Насправді вертикальна риска має більш загальний зміст, нею можна виділити довільну кількість елементів: [tom, ann | [john, bob]], [tom, ann, john, bob] | [ ]].

Списки, як і всі структурні об’єкти в мові Пролог, – це дерева. Зокрема, третій список можна зобразити у вигляді дерева, показаного на рис. 9. Списки зручно використовувати, коли кількість компонентів у структурі змінна. Наприклад, якщо ми хочемо створити БД, у якій зберігаються прізвища викладачів і назви дисциплін, які вони викладають, її можна реалізувати таким чином:

domains

teacher = string

courses_list = string*

predicates

info(teacher, courses_list)

clauses

Info("Шевченко о.В.", ["Інформатика", "Чисельні методи"]).

Info("Нікольський а.С.", ["Комп’ютерна графіка"]).

Info("Рябчук м.В.", ["Фізика", "Хімія", "Астрономія"]).

goal

Info("Рябчук м.В.", X), write (X), nl.

Рис. 9. Зображення списку у вигляді дерева

Як видно, кількість дисциплін може варіюватися від нуля до довільної кількості. Списки описують за допомогою знака „*” (зірочка).

Основні операції зі списками такі:

• перевірка об’єкта на належність до списку;

• конкатенація (зчеплення) двох списків;

• додавання або вилучення об’єкта зі списку.

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

Приклади

Перевірку об’єкта на належність до списку реалізують на основі таких міркувань:

1. об’єкт є головою списку;

2. об’єкт належить списку, якщо об’єкт належить хвосту списку.

Ці речення мовою Пролог записують так:

member(X, [X | Tail]).

member(X, [Head | Tail]):-

member(X, Tail).

Конкатенацію (зчеплення) двох списків реалізують у вигляді предиката з трьома аргументами: перший і другий аргументи – два вхідні списки, третій аргумент – вихідний список. Нижчеподані фрази показують, як зчепити два списки:

1. якщо перший аргумент порожній, то другий і третій аргументи являють собою один і той же список;

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

Мовою Пролог ці фрази записують таким чином:

append([], List, List).

append([X|L1], List2, [X|L3]) :-

append(L1, List2, L3).

Додати об’єкт до списку можна без будь-якої процедури, просто записуючи його у вигляді голови списку: [X | List]. Якщо ж треба явно описати процедуру додавання об’єкта до списку, її можна записати у вигляді факту:

add(X, List, [X | List]).

Вилучення об’єкта зі списку можна описати як предикат, що має три аргументи: 1) сам об’єкт; 2) початковий список; 3) результуючий список. Відношення вилучення записують двома реченнями:

1. якщо Х– голова списку, то результатом вилучення буде хвіст цього списку;

2. якщо Х знаходиться у хвості списку, то його треба вилучити звідти.

Мовою Пролог зазначене вище можна переписати так:

remove(X, [X | Tail], Tail).

remove(X, [Y | Tail], [Y | Tail1]):-

remove(X, Tail, Tail1).

Пролог має і вбудований предикат для роботи зі списками – findall. За допомогою нього можна зібрати всі розв’язки цілі в один список. Загальна форма така:

findall(ArgumentName, PredicateCall, ValuesList)

ArgumentName визначає, який параметр у вказаному предикаті PredicateCall слід зібрати в список ValuesList.

PredicateCall вказує предикат, із якого будуть зібрані значення.

ValuesList – вихідний список значень, зібраних за допомогою бектрекінгу.

У поданій нижче програмі за допомогою предиката findall із БД збирають у список TownList1 назви всіх міст, а в список TownList2 – назви міст, до яких існує дорога з Києва:

domains

town = symbol

town_list=town*

facts

town(town).

predicates

nondeterm road(town,town)

clauses

town(kyiv).

town(lviv).

town(dnipro).

town(donetsk).

road(kyiv,lviv).

road(lviv,krakiv).

road(kyiv,dnipro).

road(dnipro,donetsk).

goal

findall(X, town(X), TownList1), write(TownList1), nl,

findall(X, road(kyiv,X), TownList2), write(TownList2), nl.

2.12. Ігри