Понятие структуры. Списки, последовательность. Операции над списками

Структуры – объекты, которые состоят из нескольких компонент, которые, в свою очередь, могут быть структурами. Например дата (день, месяц, год). Для того, чтобы определить компоненты, требуется выбрать функтор – дата. Все структуры можно изображать в виде деревьев, где корень – функтор, а ветви – аргументы).  

Списки – последовательность, составленная из произвольного числа элементов, которые разделяются запятыми и заключаются в квадратные скобки. [а,б,в.г], [1,2,3], [“Петров”, “Иванов”]. Объектом в списке может быть всё, что угодно, включая список. Однако все элементы списка должны относиться к одной и той же области определения, и в программе должны присутствовать объявления области определения объектов следующего типа:

DOMAINS

тип_списка = тип_объектов* (в списке м.б. 0 и > элементов)

тип_объектов = ….  

Для списка возможны 2 случая:

1. пустой список – список заканчивается как атом []
2. непустой список – список рассматривается как структура, состоящая из 2 частей: головы (первый элемент) и хвоста, которые соединяются межу собой |

Операции над списками:

1. принадлежность к списку: принадлежит (X,L). Х – голова L, X – хвост L. Это можно записать в виде двух предложений, первое из которых есть простой факт, а второе – правило.

Принадлежит (X,[X|_]).

Принадлежит (X,[_|Xvost]):-принадлежит (X,Xvost).

2. Конкатенация (сцепление) – для сцепления списков определим отношение конкат (L1, L2,L3). Если L1 – пуст, то L2 и  L3 один и тот же список. Если L1 не пуст, то он имеет голову и хвост [X|L1].

konkat([],L,L).

konkat([X|L1],L2,[X|L3]):-konkat(L1,L2,L3).

При помощи данной программы можно разбивать списки. Например в цели задать konkat(L1,L2,[а, б, в).

3. Добавление элемента – самое простое – вставить в голову. dob(X,L,[X|L]).
4. Удаление элемента. Удалить (X, L, L1). Если Х – голова, то результат удаления – хвост. Если Х в хвосте, то удаляем оттуда.

del(X,[X|Xvost],Xvost).

del(X,[Y|Xvost],[Y|Xvost1]):-del(X,Xvost,Xvost1).

5. Подсписок – S является подсписком L, если L – можно разбить на 2 списка L1 и L2, и L2 тоже можно разбить на 2 списка – S и L3.

podspisok(S,L):- konkat(L1,L2,L), konkat(S,L3,L2).

6. Перестановки – определим отношение перестановка с двумя аргументами (2 списка, один из которых является перестановкой другого). Если 1 список пуст, то и 2 пуст. Если 1 список непуст, то он имеет вид  [X|L] и перестановку такого списка можно построить так: вначале получить список L1 – перестановку L, а затем внести Х в произвольную позицию L1. Следовательно, удаляем X из первого списка, переставляем оставшийся список и добавляем X в начало нового списка.

perest([], []).

perest(L,[X|P]):-del(X,L,L1),perest(L1,P).