Списки.
Списки – один из типов структур данных, широко используемых в нечисловом программировании. Списки рассматриваются в Прологе как специальный частный случай двоичного дерева. В Прологе существует два способа изображения списков:
пустой список – это атом, изображается [] ;
непустой список – рассматривается как структура, состоящая из двух частей:
первый элемент – голова (ею может быть любой прологовский объект, например, переменная или структура);
остальная часть списка называется хвостом, им может быть только список.
Голова соединяется с хвостом при помощи специального функтора « . »
. (Голова, Хвост)
Хвост может быть пустым, либо иметь свои собственные голову и хвост:
.( мяч, .(кукла, .(машинка, [] ) ) )
Э
тому
списку соответствует следующая
древовидная структура:
Во внутреннем представлении списки всегда выглядят как деревья. Однако, в Прологе используются специальные средства для списковой нотации, позволяющие представлять списки в более лаконичном виде:
[Элемент1, Элемент2,…].
Примеры: а) [мяч, кукла, машинка]
б) Увлечения1=[теннис, музыка],
Увлечения2=[еда, пиво],
Список= [миша,Увлечения1,коля, Увлечения2].
Список= [миша, [теннис, музыка] ,коля, [еда, пиво]].
На практике бывает удобно трактовать хвост списка как самостоятельный объект. Тогда используется следующая списковая нотация:
[Голова | Хвост].
Например. L=[a,b,c], тогда можно написать Хвост=[b,c] L=[a | Хвост]
или [Элемент1, Элемент2,…| Остальные],
т.е. « | » имеет более общий смысл: можно перечислить любое количество элементов списка, затем поставить | и перечислить остальные элементы.
Пример: [a,b,c]= [a | [b,c]] =[a,b | [c]] =[a,b,c | []].
Списки можно применять для представления множеств, хотя эти понятия различаются тем, что для списка существенным является порядок элементов, а для множества – нет; в списке один и тот же элемент может встречаться несколько раз. Операции над списками аналогичны операциям над множествами (проверка принадлежности объекта списку, конкатенация двух списков, добавление объекта в список или удаление его из списка).
Рассмотрим работу со списками на примере конкатенации двух списков.
domains
spis=symbol*
predicates
konkat(spis,spis,spis)
clauses
/*Исходный вид: когда 1-й список пуст, то результат конкатенации – это второй список*/
konkat([],S,S).
/*Рекурсивное правило*/
konkat([X|S1],S2,[X|S3]):-konkat(S1,S2,S3).
Эта программа обладает большой гибкостью и ее можно использовать в различных целях.
Запрос ?- konkat ([а, в] , [с, d] ,S).
позволяет получить список, являющийся результатом конкатенации: S=[а, в, с, d].
Разбиение заданного списка на две части всеми возможными способами:
?- konkat (S1 ,S2, [а, в, с]).
Получим:
S1=[], S2=[a,b,c]; S1=[a], S2=[b,c]; S1=[a, b], S2=[c]; S1=[a, b, c], S2=[];
Поиск в списке комбинации элементов, отвечающей некоторому условию, заданному в виде шаблона или образца:
а) найти все элементы, предшествующие заданному элементу списка, и следующие за ним:
?- konkat ( До , [c | После], [а, в, с, d, e]).
До=[a, b], После=[d, e]
б) элемент списка, предшествующий данному, и элемент, следующий за данным элементом:
?- konkat ( _ , [До, c, После | _], [а, в, с, d, e]).
До= b, После= d
в) удаление хвоста списка, начиная с заданной цепочки элементов:
?- konkat ( Список , [c, с, с | _ ], [а, в, с, с, с, d, e]).
Список=[a, в]
г) используя конкатенацию, можно задать отношение принадлежности элемента списку:
принадлежит (X, S):- konkat ( _ , [X | _ ], S).
То есть X принадлежит S, если список S можно разбить на два списка таким образом, чтобы элемент X являлся головой второго из них.