Списки
Списки - одна из наиболее часто употребляемых структур в Прологе. При записи список заключают в квадратные скобки, а элементы списка разделяют запятыми, например,
[слон, лошадь, обезьяна, собака]
Это список из четырех атомов - слон, лошадь, обезьяна, собака.
Элементами списка могут быть любые термы Пролога, т. е. атомы, числа, переменные и составные термы, что позволяет, в частности, составлять списки из списков. Пустой список записывается как [ ].
[слон, [ ], 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<1984, N1 is N+60, nm(N1,X).
Задание
Напишите процедуры на языке Пролог для решения следующих задач и приведите примеры использования этих процедур.
- Определите максимальный элемент списка чисел.
- Найдите второй по величине элемент списка.
- Сформируйте новый список из тех элементов данного списка, которые стоят на нечетных позициях. Например, из списка чисел [1, 2, 3, 4, 5, 6, 7] нужно получить следующий: [1, 3, 5, 7].
