length-of([1,2,3],L1)

length-of([2,3],L2)

length-of([3],L3)

length-of([],0)

L3 = 0 + 1 = 1

L2 = L3+ 1 = 2

L1 = L2+ 1 = 3

Мал.8.1.Обчислення довжини списку.

8.2.3.Іще один варіант підрахунку довжини списку.

Як ви бачите, предикат length_of не є хвостовою рекурсією. Чи можливо створити рекурсивно-хвостовий предикат визначення довжини списку? Можливо, але для цього потрібно прикласти певні зусилля.

Проблема з length_ of заключається в тому, що ми не можемо обчислити довжину списку, пока не підрахуємо довжину хвоста. Та все ж така можливість мається. Використаємо предикат з трьома аргументами.

- Перший є список, котрий ЕОМ буде читати при кожному виклику, поки він не стане пустим.

- Другий є вільним аргументом, який в кінці роботи буде визначати результат.

- Третій є лічильником, котрий починається з 0 і збільшується з кожним викликом. В кінці лічильник можна уніфікувати з незв'язаним результатом.

Наступна програма реалізує наш підхід.

domains

list = integer*

predicates

length_of(list, integer, integer)

clauses

/* * * * * * * * * * * * * * * * * * * * * * *

* Якщо список пустий, тоді уніфікувати другий *

* результуючий аргумент предикату з третім *

* аргументом - лічильником *

* * * * * * * * * * * * * * * * * * * * * * */

length_of([], Result, Result).

/* * * * * * * * * * * * * * * * * * * * * * * * * * *

* В іншому випадку, додати 1 до лічильника і рекурсивно *

* зв`язати результат цього кроку з результатом в майбутньому. *

* * * * * * * * * * * * * * * * * * * * * * * * * * */

length_of([_|T], Result, Counter):- NewCounter=Counter + 1,

length_of(T, Result, NewCounter).

Запит до цієї програми повинен також мати вмонтований предикат друку. Наприклад:

goal : length_of([1,2,3], L, 0), /* починає з значенням Counter = 0 */

write(L), nl.

Остання версія програми length_of більш складна і менш логічна.

8.2.4.Модифікація списку.

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

Обчислення, які повинна виконувати програма, можна описати наступним чином:

1.Зв'язати голову і хвіст початкового списку відповідно з Head і Tail.

2.Зв'язати голову і хвіст результату з Head1 і Tail1

(Head1 і Tail1 ще не мають значень).

3.Додаючи 1 до Head, отримаємо Head1.

4.Рекурсивно додайте 1 до всіх элементів Tail, отримаєте Tail1.

Наступна програма реалізує запропонований алгоритм.

domains

list = integer*

predicates

add1(list, list)

clauses

add1([], []).

add1([Head|Tail], [Head1|Tail1]) :-

Head1= Head+1,

add1(Tail,Tail1).

Розглянемо ще одну програму модифікації списку. Вона сканує вхідний список і переписує його без від'ємних чисел.

domains

list = integer*

predicates

discard_negatives(list, list)

clauses

discard_negatives([], []).

discard_negatives([H|T], ProcessedTail) :-

/* якщо Н є від`ємним, тоді пропустити його */

H < 0, !,

discard_negatives(T, ProcessedTail).

discard_negatives([H|T], [H|ProcessedTail]) :-

discard_negatives(T, ProcessedTail).

Наступний предикат копіює елементи списку, повторюючи їх два рази.

doubletail([],[]).

dou bletail([H|T],[H|H| doubletail ]) : -

doubletail(T, doubletail ).

8.2.5.Належність елемента списку.

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

member(name, namelist)

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

domains

namelist = name*

name = symbol

predicates

is_a_member_of(name, namelist)

clauses

is_a_member_of(Name,[Name|_]).

is_a_member_of(Name,[_|Tail]):- is_a_member_of(Name,Tail).

8.3.Використання одного й того ж предикату для вирішення різних задач.

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

append(List1,List2,List3)

де List3 є результуючим списком. Використаємо наступний рекурсивний алгоритм.

Якщо перший список пустий, тоді результуючий список буде рівний другому списку (append([],List2,List2)). Інакше, головою третього списку становиться голова першого списку, а хвостом - залишок першого списку і другий список.

Прийдемо до програми:

domains

integerlist = integer*

predicates

append(integerlist, integerlist, integerlist)

clauses

append([], List, List).

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

append(L1, List2, L3).

Якщо ми задамо ціль

goal: append([1,2],[3,4]), тоді отримаємо список [1,2,3,4].

З іншого боку, розглядаючи предикат append з декларативної точки зору, ми визначили відношення між трьома списками. Таке відношення буде вірним і у випадку, коли буде відомий тільки третій список. Наприклад,

goal: append(L1,L2,[1,2,4] дасть результат

L1 = [], L2 = [1,2,[1,2,4]

l1 = [1], l2 = [2,4]

. . .

Також ви можете використати предикат append, щоб визначити який із списків можна додати до списку [3,4], щоб отримати список [1,2,3,4]. Наприклад, задавши

goal: append[L1,[3,4],[1,2,3,4] матимемо L1 =[1,2]

Предикат append визначає відношення між множинами на вході і виході. Тому відношення може використовуватись різними способами. Задаючи таке відношення, ви можете запитати:

Який вихід відповідає даному входу? або ж

Який вхід відповідає даному виходу?

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

Але не всі предикати Прологу