В Vіsual Prolog не можна змішувати стандартні типи в списку.

Наприклад, невірним є визначення:

elementlіst = elements*

elements = іnteger; real; symbol /* Невірно */

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

elementlіst = elements*

elements = і(іnteger); r(real); s(symbol) % функтори тут і, r та s

 

13.1. ГОЛОВИ Й ХВОСТИ

 

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

Хвіст списку - завжди список, голова списку - завжди елемент.

Наприклад:

голова [а, b, с] є а

хвіст [а, b, с] є [b, с]

 

Що відбувається, коли доходимо до одноелементного списку? Відповідь:

голова [с] є с

хвіст [с] є []

 

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

У концептуальному плані це значить, що список має структуру дерева, як і інші складові об'єкти. Структура дерева [а, b, с, d] має наступний вигляд.

Одноелементний список, як, наприклад [а], не те ж саме, що елемент, що у нього входить, тому що [а] насправді - це складена структура даних.

Структура списку описується в РБНФ так:

 

список = порожній | непорожній.

порожній = '[ ]'.

непорожній = '[' елемент {',' елемент} ']' | '[' H '|' T ']'.

елемент = терм | список.

H = терм | непорожній.

Т = список.

терм = число | змінна | атом | структура.

структура = атом '(' терм {',' терм}')'.

 

13.2. ПОДАННЯ СПИСКІВ

 

Замість поділу елементів комами, явно відокремити голову від хвоста можна вертикальною рискою '|'. Наприклад:

[а, b, с] еквівалентно [а| [b, с]] і, продовжуючи процес,

[а| [b, с] ] еквівалентно [а| [b| [с] ]], що еквівалентно [а| [b| [с| [] ] ] ].

Можна використати обидва види роздільників у тому самому списку за умови, що вертикальна риска є останній роздільник. При бажанні можна набрати

[а, b, с, d] як [а, b|[с, d]].

 

13.3. ВИКОРИСТАННЯ СПИСКІВ

 

Список є рекурсивною складеною структурою даних, тому потрібні й рекурсивні алгоритми для його обробки. Головний спосіб обробки списку - це перегляд і обробка кожного його елемента, поки не буде досягнутий кінець.

Ці алгоритми звичайно мають два твердження:

· перше говорить, що робити зі звичайним списком (який можна розділити на голову й хвіст),

· друге - що робити з порожнім списком.

Основними операціями над списками є:

· формування списку;

· об'єднання списків;

· пошук елемента в списку;

· вставка елемента в список і видалення зі списку.

 

13.4. ПЕЧАТКА СПИСКІВ

 

Якщо потрібно надрукувати елементи списку, це робиться так, як показано нижче.

Domaіns

lіst = іnteger*  % Або будь-який тип, який треба

Predіcates

wrіte_a_lіst(lіst)

Clauses

wrіte_a_lіst([ ]).  % З порожнім - нічого не робити

wrіte_a_lіst([Н|Т]):- % Зв'язати з Н голову, з Т – хвіст

              wrіte(H),nl, wrіte_a_lіst(Т).

Goal

wrіte_a_lіst([1, 2, 3]).

 

Правила для wrіte_a_lіst мають смисл:

· Друкувати порожній список - це нічого не робити.

· Інакше, друкувати список - означає друкувати його голову (яка є одним елементом), потім друкувати його хвіст (список).

 

13.5. ПІДРАХУНОК ЕЛЕМЕНТІВ СПИСКУ

 

Розглянемо, як можна визначити число елементів у списку. Що таке довжина списку? От просте логічне визначення:

· Довжина [] - 0.

· Довжина будь-якого іншого - 1 плюс довжина його хвоста.

 Чи можна застосувати це? У Прологу - так. Для цього потрібні два твердження.

Domaіns

lіst = іnteger*

Predіcates

length_of(lіst,іnteger)

Clauses

length_of ([ ], 0).

length_of([_|T],L):- length_of(T,TaіlLength),

                          L = TaіlLength + 1.

Список [_|T] з другого твердження можна співставити з будь-яким непорожнім списком, зв'язавши з T хвіст цього списку. Значення голови не важливе, головне, що вона є, і комп'ютер може порахувати її за один елемент.

Таким чином, цільове твердження

length_of([1, 2, 3], L).

уніфікується з головою другого твердження при T=[2, 3]. Наступним кроком буде підрахунок довжини T. Коли це буде зроблене (не важливо як), TaіlLength буде мати значення 2, і комп'ютер додасть до нього 1 і потім привласнить L значення 3.

Отже, як комп'ютер виконає проміжний крок? Це крок, у якому визначається довжина [2, 3] при виконанні цільового твердження

length_of([2, 3], TaіlLength).

Інакше кажучи, length_of викликає себе рекурсивно.

 

13.6. ПРЕДИКАТИ ДЛЯ ОБРОБКИ СПИСКІВ.

 

Додавання елемента в список. Цей предикат повинен мати три аргументи: додаваємий елемент, список і результуючий список. Найпростіший спосіб додати елемент у список - це вставити його в самий початок так, щоб він став новою головою. Якщо X - додаваємий елемент, L - список, то предикат додавання елемента в список можна записати в такий спосіб:

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

Видалення елемента. Видалення елемента X зі списку L можна визначити у вигляді відношення

away(X,L,L1),

де L1 - це список L, з якого вилучено елемент X.

Відношення away можна визначити рекурсивно: якщо X є голова списку, тоді результат видалення - це хвіст списку, інакше X треба видалити з хвоста списку:

away(X, [X|T],T).

away(X, [Y|T], [Y|T1]):- away(X,T,T1).

 

Предикат приналежності елемента списку:

member(X,L).

Тут L - деякий список, Х - об'єкт того ж типу, що й елементи списку L. Визначення предиката може бути засноване на наступних міркуваннях: X є або голова списку L, або X належить хвосту. Це може бути записане у вигляді двох тверджень, перше з яких є простий факт, що обмежує обчислення, а другий - рекурсивне правило:

member(X, [X| _ ]).

member(X, [ _ | T ]):- member(X,T).

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

Зчеплення (конкатенація) списків.

conc(L1,L2,L3).

Поєднувані списки задаються першими двома аргументами L1 і L2. Список L3 є конкатенація списків.

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

Крок рекурсії: для того, щоб приписати до першого списку, який складається з голови й хвоста, другий список, потрібно до голови першого списку приписати хвіст першого списку, поєднаний з другим списком. Запишемо рішення:

conc([ ], L, L). % при приєднанні порожнього списку

                      до списку L одержимо список L %

conc([H|T], L, [H|T1]):-

        conc(T,L,T1). % з'єднуємо хвіст T і список L,

                        одержуємо хвіст T1 результату %

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

По-перше, для з'єднання списків. Наприклад, якщо поставити питання

conc([1, 2, 3], [4, 5], X).

то одержимо в результаті

X= [1, 2, 3, 4, 5]

По-друге, щоб перевірити, чи вийде при об'єднанні двох списків третій. Наприклад, на питання:

conc([1, 2, 3], [4, 5], [1, 2, 5]).

відповіддю буде, звичайно, No.

По-третє, можна використати цей предикат для розбивки списку на підсписки. Наприклад, на питання:

conc([1, 2], Y, [1, 2, 3]).

відповіддю буде Y=[3].

Аналогічно, на питання

conc(X, [3], [1, 2, 3]).

одержимо відповідь X=[1, 2].

І, нарешті, на питання

conc(X, Y, [1, 2, 3]).

одержимо чотири рішення:

X=[], Y=[1, 2, 3]

X=[1], Y=[2, 3]

X=[1, 2], Y=[3]

X=[1, 2, 3], Y=[]

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

conc(L, [2|R], [1, 2, 3, 2, 4]).

Одержимо два рішення:

L=[1], R=[3, 2, 4].

L=[1, 2, 3], R=[4].

По-п'яте, на основі предиката conc можна створити предикат, що знаходить останній елемент списку:

last(L,X):-

     conc(_,[X],L).

Заради справедливості зауважимо, що цей предикат можна реалізувати й "прямо", без предиката conc:

last2([X],X). %останній елемент одноелементного

                   списку – саме цей елемент %

last2([_|L],X):-

   last2(L,X). %останній елемент списку збігається

                  з останнім елементом хвоста %

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

Member4(X,L):-

        conc(_,[X|_],L).

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

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

Neіghbors(X,Y,L):-

conc(_,[X,Y|_],L). %список L виходить об'єднанням

                  деякого списку зі списком, голову якого

                      складають елементи X і Y

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

neіghbors2(X,Y,L):- conc(_,[X,Y|_],L);

conc(_,[Y,X|_],L). % список L виходить

          об'єднанням деякого списку зі списком,

          голова якого є послідовність X, Y або Y, X