Робота процедури
Процедура розіб’є список [1,2,3] на списки [1] та [2,3]. Другий аргумент цілі задається структурою [ 2 | Pisl], щоб приєднати „2” до другого списку.
Зіставлення цілі з фактом виявляється неможливим по такій причині. Другий і третій аргумент факту однакові змінні. В цілі голова списку другого аргументу 2, голова списку третього аргументу 1. Отже, списки другого і третього аргументів не однакові.
Відбувається зіставлення цілі з головою правила. Вільна змінна Do зчіплюється з структурою [H | L1], де Н та L1 вільні. Наполовину визначена структура [ 2 | Pisl ] зчіплюється з вільною змінною L2. Список [1,2,3] з третього аргументу цілі зіставляється зі структурою. В результаті змінна Н конкретизується 1, а хвіст L3 конкретизується [2,3].
Нова ціль у тілі правила буде: pr (L1, [2 | Pisl], [2,3]).
Така ціль зіставляється з фактом, бо другий і третій аргументи цілі можуть бути однаковими. В результаті L1 конкретизується порожнім списком, а змінна Pisl конкретизується хвостом цього списку [3]. Див. Схему:
pr ( [] L L) факт
pr ( [] [2 [3]] [2,3]) ціль
Одержуємо: Do = [ 1 ]. Pisl = [3], [ 2 | Pisl ]= [ 2,3 ].
3) Процедура розділяє список на два підсписки, перебираючи всі можливі варіанти підсписків, елементи яких йдуть підряд.Для перебору, після використання одержаних підсписків, повинна стояти невірна умова.
Ціль: Перші два аргументи вільні змінні. Третій аргумент список.
Domains
List = integer*
Predicates
pr (list, list, list)
Clauses
pr ([ ], L, L),
pr ([Н | L1], L2, [Н | L3]): - pr (L1, L2, L3).
Goal pr (L1, L2, [1, 2, 3]), write(L1,L2), fail.
Ціль зіставляється з фактом. Змінна L1 конкретизується []. Список [1, 2, 3] з цілі конкретизує третій і другий аргументи L з факту і тому L2 з цілі теж конкретизується цим списком.
Список [1,2,3] розбився на списки[ ] та [1, 2, 3] .
Після виводу списків предикат fail включає механізм звороту і звільнює аргументи L1 і L2.
Виконується зіставлення цілі з головою правила. У результаті H=1, L3=[2, 3]. Ціль в тілі правила стає: pr(L1, L2, [2,3])
Ціль зіставляється з фактом. Змінна L1 конкретизується [ ],
L2=[2, 3]. Аргументи предиката в голові правила стають: перший аргумент [1], другий аргумент [2,3].
Список [1,2,3] розбився на списки[ 1] та [ 2, 3] .
Далі процес повторюється. Список [1,2,3] розбивається на:
[1,2] та [3], [1,2,3] та [ ].
Процедуру використовують для знаходження певних підсписків. Ознака одержання певних підсписків буде працювати як fail, якщо підсписки не підходять. Наприклад, замість fail можна записати L2=[H| T],H>2. Тоді знайдуться такі підсписки [1,2] та [3].
Процедура "Вилучити" – вилучає вказаний елемент із списку. Процедура має два варіанти.
Процедура "вилучити1" – вилучає перший вказаний елемент, що зустрівся.
Goal
vuluch1(2, [1,2,2], L).
Clauses
vuluch1(_,[], []):-!. (1)
vuluch1(Х,[X|L1],L1):-!. (2)
vuluch1(Х,[Н|L1],[Н|L2]):- vuluch1(Х,L1,L2). (3)
Гранична умова (1) досягається, якщо елемент не знайдено. Результат співпадає з вхідним списком.
У граничній умові (2) вилучається знайдений елемент. Залишок списку переноситься у новий список.
Правило (3) переносить голову списку у новий список, якщо вона не співпадає з елементом, що вилучається. Після цього продовжується пошук елементу.
Процедура "вилучити2"- вилучає всі елементи списку, які співпадають з вказаним.
Goal
vuluch1(2, [1,2,2], L).
vuluch2(_,[],[]):-!. (1)
vuluch2(Х,[Х|L1],L2):- vuluch2(Х,L1,L2). (2)
vuluch2(Х,[Н|L1],[Н|L2]):- vuluch2(Х,L1,L2). (3)
Процедура ''вилучити2' відрізняється від процедури “вилучити1”, тим, що після того, як вилучено вказаний елемент, продовжує пошук вказаного елемента у хвості списку.
7.7. СОРТУВАННЯ СПИСКІВ НА ПРОЛОЗІ
Сортування методом простої вставки
Нехай є список: [15, 11, 13, 12]. Треба відсортувати список в порядку зростання.
