Clauses

Predіcates

Domaіns

Goal

Clauses

Predіcates

Domaіns

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

wrіte_a_lіst(lіst)

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

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

wrіte(H),nl,

wrіte_a_lіst(Т).

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

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

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

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

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

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

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

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

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

lіst = іnteger*

length_of(lіst,іnteger)

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 викликає себе рекурсивно.

12.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). /* з'єднуємо хвіст і список L, одержуємо

хвіст результату */

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

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

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 */