Списки, портал знань, портал знань, Дистанційне навчання

Додати до моєї бази знань

Списки - одна з найбільш часто вживаних структур в Пролозі. При записи список укладають у квадратні дужки, а елементи списку поділяють запитом, наприклад,
[Слон, кінь, мавпа, собака]
Це список з чотирьох атомів - слон, кінь, мавпа, собака.
Елементами списку можуть бути будь-які терми Прологу, т. Е. Атоми, числа, змінні і складові терми, що дозволяє, зокрема, складати списки зі списків. Порожній список записується як [].
Ось приклад списку з трохи більш складною структурою:
[Слон, [], X, предок (Х, тому), [a, b, c], f (22)]
Перший елемент непорожньої списку називається головою, а інша частина списку носить назву хвіст. У списку, що складається тільки з одного елемента головою є цей єдиний елемент, а хвостом - порожній список. Позначення [H | T] використовується для подання списку з головою H і хвостом T. Якщо символ | поміщений перед останнім термо списку, то це означає, що цей останній терм визначає інший список. Повний список вийде, якщо поєднати цей подсписок з послідовністю елементів, розташованих до риси.
У наступному прикладі 1 - голова списку, а [2, 3, 4, 5] - хвіст. Пролог покаже це за допомогою зіставлення списку чисел зі зразком, що складається з голови і хвоста.
?- [1, 2, 3, 4, 5] = [Head | Tail].
Head = 1
Tail = [2, 3, 4, 5]
Yes
Тут Head і Tail - тільки імена змінних. Ми могли б використовувати X і Y або якісь інші імена змінних з тим же успіхом. Зауважимо, що хвіст списку завжди є списком. Голова, в свою чергу, є елемент списку, що вірно і для всіх інших елементів, розташованих до вертикальної риси. Це дозволяє отримати, скажімо, другий елемент списку.
приклад
Використовуємо анонімні змінні для голови і списку, що стоїть після риси, якщо нам потрібен тільки другий елемент списку:
?- [Слон, кінь, осел, собака] = [_, X | _].
X = кінь
Yes
Розглянемо кілька процедур обробки списків. Зверніть увагу, що всі вони використовують рекурсію, в якій термінальне (базове) правило визначено для порожнього списку.
приклад
Напишемо предикат для обчислення суми всіх елементів списку чисел.
сумма_спіска ([], 0).
сумма_спіска ([H | T], S): - number (H), сумма_спіска (T, S1),
S is S1 + H.
приклад
Предикат місце / 3 успішний, якщо третій аргумент є список, отриманий вставкою першого аргументу в довільне місце списку, що є другим аргументом.
місце (E, L, [E | L]).
місце (E, [H | L], [H | Y]): - місце (E, L, Y).
Подивимося на результати деяких запитів, що використовують цей предикат.
?- місце (1, [2,3], X).
X = [1, 2, 3];
X = [2, 1, 3];
X = [2, 3, 1];
No
?- місце (1, L, [2,1,3]).
L = [2, 3];
No
?- місце (X, [2,3], [2,1,3]).
X = 1;
No
приклад
Предикат перестановка / 2 видає списки, отримані перестановкою елементів свого першого аргументу.
перестановка ([], []).
перестановка ([H | L], Z): - перестановка (L, Y), місце (H, Y, Z).
Приклад використання:
?- перестановка ([a, b, c], X).
X = [a, b, c];
X = [b, a, c];
X = [b, c, a];
X = [a, c, b];
X = [c, a, b];
X = [c, b, a];
No
І, нарешті, наведемо правило для друку всіх можливих перестановок списку:
все_перестановкі (L): - перестановка (L, R), write (R), nl, fail.
Перша подцель предиката обчислює чергову перестановку, друкує її та переходить до останньої підцілі - fail. Ця подцель завжди неуспішна, що змушує Пролог повернутися до початку правила і продовжити пошук рішення. Робота процедури завершиться, коли все перестановки будуть вичерпані:
?- все_перестановкі ([ 'маркіза', 'ваші прекрасні очі',
| 'Обіцяють мені смерть від любові']).
[Маркіза, ваші прекрасні очі, обіцяють мені смерть від любові]
[Ваші прекрасні очі, маркіза, обіцяють мені смерть від любові]
[Ваші прекрасні очі, обіцяють мені смерть від любові, маркіза]
[Маркіза, обіцяють мені смерть від любові, ваші прекрасні очі]
[Обіцяють мені смерть від любові, маркіза, ваші прекрасні очі]
[Обіцяють мені смерть від любові, ваші прекрасні очі, маркіза]
No
приклад
У давньояпонському календарі був прийнятий 60-річний цикл, що складається з п'яти 12-річних підциклів. Підцикли позначалися назвами квітів: зелений, червоний, жовтий, білий і чорний. Усередині кожного подцикла року носили назви тварин: пацюк, корова, тигр, заєць, дракон, змія, кінь, вівця, мавпа, курка, собака і свиня. Наприклад, 1984 рік - рік початку чергового циклу - називався Роком Зеленої Щура.
Складемо програму, яка за заданим номером року нашої ери n друкує його назва в давньояпонському календарі. Розглянемо два випадки:
(1) значення n не менше, аніж 1984;
(2) значення n - будь-яке натуральне число.
Скористаємося вбудованим предикатом nth0 (індекс, список, елемент), який буде успішним, якщо елемент знаходиться на місці з номером індекс, рахуючи від 0. Для випадку (1) використовуємо предикат nam, для випадку (2) предикат - nm.
color (N, X): - N1 is ((N-1984) mod 60) // 12,
nth0 (N1, [ 'зелений',
'Червоний', 'жовтий',
'білий чорний'],
X).
animal (N, X): - N1 is (N-1984) mod 12,
nth0 (N1,
[ 'Щур', 'корова', 'тигр',
'Заєць', 'дракон', 'змія',
'Кінь', 'вівця', 'мавпа',
'Курка', 'собака', 'свиня'],
X).
nam (N, [X, Y]): - number (N), color (N, X), animal (N, Y).
nm (N, X): - N> 1983, nam (N, X).
nm (N, X): - N

Сторінки, блізькі за змістом