Списки в Prolog
У функціональних та логічних мовах списки використовуються дуже часто, вони дозволяють зберегти набір даних довільної довжини. У статті на багатьох прикладах показано обробку списків у мові Prolog. Основна частина прикладів написана на діалектах з динамічною типізацією (SWI/GNU/Arity Prolog), але з невеликими змінами добре працюватиме на строго-типізованих реалізаціях (Turbo/Visual Prolog).
Списки. Теорія
У загальному випадку список є абстрактним типом даних, що задає набір значень. У цій статті під списком розуміється "зв'язковий список", який є однією з можливих реалізацій абстрактних списків.
Зв'язковий список - структура даних, що складається з вузлів. Вузол містить дані та посилання (покажчик, зв'язку) на один або два сусідні вузли. Списки мови Prolog є однозв'язковими, тобто. кожен вузол містить лише одне посилання.
Працюючи з однозв'язковими списками необхідно виділяти перший вузол (званий головою списку), інші вузли (що становлять хвіст списку) можна отримати пересуваючись за покажчиками до останнього вузла. Хвіст списку є таким самим списком, як і вихідний, тому обробляється аналогічним чином (рекурсивно).
Списки у Prolog. Синтаксис
При використанні статично-типізованого діалекту необхідно оголосити тип списку (наприклад Turbo Prolog це робиться в розділі domains):
Наведений вище приклад показує рекурсивну природу списків - після відділення голови (першого елемента) залишається хвіст, який також є списком. Операція поділу на голову та хвіст може використовуватись для формування нового списку. У мові є позначення для порожнього списку, і воно постійновикористовується у рекурсивних функціях для фіксації закінчення обробки.
Рекурсивне опрацювання списків. Приклади
sum_list(List, Sum) - обчислення суми елементів списку
Сума елементів порожнього списку дорівнює нулю. Якщо список не порожній – розділимо його на перший елемент та хвіст. Обробимо рекурсивний хвіст, в результаті отримаємо суму елементів частини списку без урахування першого елемента. Додамо перший елемент, щоб отримати остаточний результат.
nth0(Index, List, Elem) - функція отримання елемента списку із заданим індексом. Індексація починається із нуля. Якщо потрібного елемента немає, функція завершується невдачею.
Функція завершує свою і успішно повертає перший елемент списку, якщо Index дорівнює нулю і від списку вдалося відокремити перший елемент. Функція завершується невдачею якщо Idex виявився меншим за нуль або залишився більше нуля при порожньому списку. Якщо ж список не порожній (від нього успішно відокремлюється перший елемент) і індекс більший за нуль — рекурсивно обробляється хвіст списку і зменшений на одиницю Index (адже список зменшився на один елемент).
member(Elem, List) — шукає значення у списку. Завершується успіхом, якщо елемент знайдений.
Якщо значення першого елемента списку збігається зі значенням елемента, що шукається — правило відразу завершується успіхом. В іншому випадку перший елемент відкидається і пошук продовжується у хвості. Як тільки поділ списку на голову та хвіст стане неможливим — правило завершиться невдачею.
Важливо, що предикат може повернути кілька рішень (предикат є недетермінованим — nondeterm), тому перше правило не містить відсікання. Така поведінка особливо важлива, якщо функція member використовується для перебору всіх елементів списку (достатньо передати замість Elemанонімну змінну).
min_list(List,MinElem) - обчислення найменшого елемента списку
Рішення очевидно, якщо список складається з одного елемента. Якщо елементів більше, то список поділяється на голову та хвіст. Рекурсивно обчислюється найменший елемент хвоста і порівнюється з першим елементом визначення результату всього списку.
Якщо на вхід буде подано порожній список, то поділ на голову та хвіст провалиться і правило завершиться невдачею.
reverse(List, ReverseList) — функція перевороту списку
Щоб перевернути список використовується метод накопичувального параметра, створюється допоміжна функція, яка крім двох списків приймає буфер. Спочатку буфер порожній, але в міру обробки, його початок додаються елементи з вихідного списку — тому перший доданий елемент виявиться останнім, а останній — першим. Як тільки всі елементи будуть оброблені - накопичені в буфері значення будуть переписані в список-результат.
Метод накопичувального параметра використовують досить часто, т.к. при його використанні рекурсивний виклик виявляється останньою операцією, яку виконує функція. Компілятори замінюють такий виклик на цикл, що дозволяє обробляти величезні списки і не боятися переповнення стека.
sublist(Sub, List) — завершується успіхом якщо всі елементи списку Sub зустрічаються в списку List у такому самому порядку.
Напишемо допоміжну функцію sub_start для перевірки випадку, коли список List починається зі списку Sub. Очевидно, що перевірка допоміжного правила дасть умову виходу з рекурсії у разі успішного завершення роботи. Якщо ж перевірка не увінчалася успіхом - відокремимо від List перший елемент, а решту спробуємо обробити рекурсивно.
Функціяsub_start завершується успіхом, якщо список Sub виявився порожнім, т.к. Порожній список за визначенням є частиною будь-якого списку.
delete(InputList, Elem, ResultList) — функція видалення всіх елементів із заданим значенням зі списку
Якщо на вхід подано порожній список, то результатом також повинен бути порожній список. Якщо перший елемент списку збігся з значенням, що видаляється - функція повинна повернути результат рекурсивної обробки хвоста, а в іншому випадку - додати до отриманого результату перший елемент.
append(List1, List2, List1AndList2) - функція об'єднання двох списків
Поступово вибираючи елементи першого списку зводимо ситуацію до того, що список стане порожнім - у цьому випадку результатом роботи функції повинен бути другий список. На рекурсивному підйомі додамо до результату отримані елементи першого списку.
Функція може виконувати як об'єднання списків, так і їх віднімання. Якщо заданий третій аргумент, але не заданий другий чи перший — вона спробує підібрати недостатні значення те щоб вийшов необхідний результат. Крім того, якщо не задані обидва перші аргументи — функція перебиратимете всі варіанти генерації третього списку з двох.
unique(List) - перевірка того, що жоден елемент списку не повторюється двічі
У списку немає елементів, що повторюються, якщо перший елемент списку не зустрічається в хвості, а також, у хвості немає елементів, що повторюються. Умовою виходу з рекурсії може бути порожнеча вихідного списку - в ньому гарантовано немає елементів, що повторюються.
rangConcat(List1, List2, List1AndList2) — об'єднання двох відсортованих списків так, щоб у результаті вийшов відсортований список.
Очевидно, що якщоодин зі списків порожній – результатом є інший список. На кожному кроці алгоритму обидва вхідні списки поділяються на голову та хвіст. Голови порівнюються та рекурсивно обробляються списки без найменшої голови, на рекурсивному підйомі вона додається до результату.
length(List, Length) - обчислює довжину списку
Використовуємо метод накопичувального параметра, щоб рекурсія функції була хвостовою, т.к. довжина списків на мові Prolog обчислюється дуже часто, тому ефективність функції є критичною.
Функція length викликає допоміжну, у своїй задає початкове значення довжини рівним нулю.
Допоміжна функція повертає накопичене в буфері значення як довжина, якщо на вхід подано порожній список. В іншому випадку від вихідного списку відокремлюється один елемент, обчислюється нове значення буфера. Хвіст списку та буфер передаються для рекурсивної обробки.