Найпростіші процедури роботи зі списками

 

У порграмі 4.1 мета year (All) забезпечувала присвоєння змінній All усього списку в цілому. Навпаки, мета year (_,Х,_,_) дозволяла витягнути зі списку усього лише один елемент. Однак, у цьому випадку було потрібне точне знання числа елементів у списку. Якщо задати мету у вигляді year ([ Х,Y ]), то вона не буде досягнута, через невідповідність кількості елементів у списку і цільовому твердженні.

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

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

/* програма 4.5 */

domains

list_season=season*

season=string

predicates

year (list_season)

print_list (list_season)

goal

year (L), print_list (L).

clauses

year ([ “зима”, “весна”, “літо”, “осінь” ]).

print_list ([]).

print_list ([ Х|Y ]) :- write (X), nl, print_list (Y).

Процедура print_list () включає два правила. Перше – це факт, що визначає граничну умову рекурсивної процедури, тобто кінець виводу елементів списку, якщо він порожній.

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

print_list ([]) :- L= [ Х|Y ], write (X), nl, print_list (Y).

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

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

Однак, мета програми обмежує можливі дії з модифікації даних у базі: додавання, пошукову, виключення і т.д.

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

Приклад такого підходу реалізований у програмі 4.6, з використанням предиката show_worker.

/* програма 4.6 */

domains

number,salary=integer

name=string

member=worker (name,salary)

list_worker=member*

predicates

office (number,list_worker)

print_list (list_worker)

show_workеr

clauses

show_worker:- write (“Введіть номер відділу -> “), readint (Otd), office (Otd,L), print_list (L), readchar (_).

office (101, [ worker (“Кардаш”,500), worker (“Петренко”,300), worker (“Маслов”,200)]).

office (211,worker (“Денега”, 400)]).

print_list ([]).

print_list ([ X | Y ]) :- write (X) ,nl, print_list (Y).

 

Процедури обробки списків

 

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

Належність до списку. Представимо відношення належності у вигляді member (R, L), де R – терм, a L – список. Ціль member (R, L) істинна, якщо терм R зустрічається в L. Задача перевірки входження терму в список формулюється у вигляді:

Гранична умова: Терм R знаходиться в списку, якщо R є голова списку L.

Рекурсивна умова: Терм R знаходиться в списку, якщо R належить хвостові L.

Один з варіантів Пролог-процедури можна представити в наступному виді:

member (R,L) :-L= [ H|Т ], H=R.

member (R,L) :- L= [ H|Т ], member (R,T).

Ціль L= [ H|Т ] у тілі обох правил служить для того, щоб розділити список L на голову і хвіст. Можна поліпшити процедуру, якщо врахувати той факт, що Пролог спочатку зіставляє з метою заголовок правила, а потім намагається погодити його тіло. Тоді поліпшений варіант цієї ж процедури може бути записаний у виді:

member (R, [ R |_ ]).

member (R, [ _ | Т ]) :- member (R, Т).

Використання анонімних змінних (_) викликане тим, що при застосуванні першого правила нас не цікавить хвіст списку, а при застосуванні другого – голова списку.

Як приклад розглянемо роботу процедури при виконанні мети:

member (d, [ a,b,d,c ]).

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

Змінна Т одержує значення [ b,d,c ], і породжується нова мета: member (d, [ b,d,c ]). Тому що перше правило не уніфікується з метою, відбувається повторне зіставлення другого правила і виділення нового хвоста списку.

Поточною метою стає member (d, [ d,c ]). Використання першого правила приводить до того, що елемент, який перевіряється, d зіставляється з головою списку. [ d,c ]. Перше правило стає істинним, тобто ціль досягнута.

Якщо вихідна мета member (d, [ a,b,c,e ]), то процес зіставлення з другим правилом буде рекурсивно повторюватися дотих пір, поки не буде досягнута мета member (d, []). Жодне з правил не уніфікується з цією метою і, тому вихідна мета виявляється помилковою.

З’єднання двох списків. Для з’єднання двох списків визначимо відношення append (L1, L2, L3), де L1 – вихідний список, L2 – список, що приєднується (додається), a L3 – список, одержуваний при їхньому з’єднанні. Задача з’єднання списків формулюється в такий спосіб:

Гранична умова: Приєднання списку L2 до [] дає той же список L2.

Рекурсивна умова: Список L2 приєднується до хвоста L1, а потім попереду додається голова L1.

Тоді безпосередньо з постановки задачі можна написати процедуру виду:

аppend ([], L2, L2).

append (L1, L2, L3) :- L1= [ H|Т ], append (T, L2, X), L3= [ H|X ]

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

append ([], L2, L2).

append ([ Н|L1 ], L2, [ Н|L3 ]) :- append (L1, L2, L3).

На запит append ([ a,b,c ], [ d,e ], L) буде отримана відповідь L= [ a,b,c,d,e ], а на запит append ([ a,b ], [ c ], [ a,c,d ]) відповіддю буде “ні”.

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

Goal: append (X, [ “квітень”|Y ], [ “січень”, “лютий”, “березень”, “квітень”, “травень”, “червень” ])

X= [ “січень”, “лютий”, “березень”, “квітень” ]

Y= [ “травень”, “червень” ]

Видалення елементу. Для видалення елемента Х зі списку L введемо відношення delete (X, L, L1), де L1 – скорочений список. Задача буде сформульована у виді:

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

Рекурсивна умова: Якщо Х знаходиться в хвості списку, тоді його варто видалити з хвоста списку.

delete (X, [ X | Т ], Т).

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

Одержання n- го терма зі списку. Задача доступу до заданого номером елементу списку формулюється наступним чином:

Гранична умова: Перший терм у списку [ H| ] є Н.

Рекурсивну умову: N -й терм у списку [ H| ] є (N -1)-шим термом у списку Т.

term_in_list ([ Н | _ ] ,1,Н).

term_in_list ([ _ |Т ], N, X) :- M=N-1, term_in_list (T, M, X).

Визначення довжини списку. Задача формулюється в такий спосіб:

Гранична умова: Довжина порожнього списку дорівнює нулеві.

Рекурсивна умова: Довжина списку [ H| ] на одиницю більше довжини списку Т.

list_len ([] ,0).

list_len ([ _|T ] ,Len) :- list_len (T,Len1), Len = Len1+1.

У предикаті list_len другий аргумент набуває значення рівне довжині списку. Якщо другий аргумент є зв'язаною змінною, то йде перевірка на її збіг з довжиною списку.