→ Пошук по сайту       Увійти / Зареєструватися
Знання Пролог

Списки

Списки - одна из наиболее часто употребляемых структур в Прологе. При записи список заключают в квадратные скобки, а элементы списка разделяют запятыми, например,
[слон, лошадь, обезьяна, собака]
Это список из четырех атомов - слон, лошадь, обезьяна, собака.
Элементами списка могут быть любые термы Пролога, т. е. атомы, числа, переменные и составные термы, что позволяет, в частности, составлять списки из списков. Пустой список записывается как [ ].
Вот пример списка с несколько более сложной структурой:
[слон, [ ], 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).

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