Списки и их использование

Кроме шести основных объектов, Пролог поддерживает связанные объекты, называемые списками. Списки используются, когда заранее неизвестно, сколько будет элементов в списках и какая в них будет информация. Списком называется упорядоченный набор однотипных объектов, следующих друг за другом. Элементы, составляющие списки, связаны друг с другом. Поэтому с ними можно работать как с группой, т.е. со списком в целом, так и с отдельным элементом.
Над списками определены следующие операции.

Рассмотрим структуру, организацию и представления списков. Объектами списка могут быть целые, действительные числа, символы, символьные строки, структуры и списки. Файлы не могут быть элементами списка. Порядок расположения элементов определяет конкретный список и играет важную роль в процессе сопоставлений. Совокупность элементов списка помещают в квадратные скобки: [a, b, c, d, e, f]. Элементы отделяются друг от друга запятыми. Количество элементов в списке называется его длиной. Минимальным списком является (нулевой) пустой:[ ].Каждый список можно представить состоящим из двух частей: 1)головы- первый элемент списка и 2) хвоста-остальная часть списка.
Для выделения отдельного элемента в списке используется встроенная операция разделения списка на голову и хвост.
Х= [Н|T]
Head -голова
Tаil - хвост
Голова – отдельный элемент списка,
Хвост – это тоже список .

7.12.1. Использование списка
Для использования списка нужно описать предикат списка. Предикатам списка обычно присваивают имена, которые характеризуют либо тип элемента, либо сами данные. Введение списка отражается в трех разделах. Домен списка должен быть определен в разделе domains, работающий со списком предикат должен быть  в разделе predicates, сам список задается либо в фактах, либо в цели.
Отличительной особенностью списка является наличие знака * после имени домена элементов. Используем операцию разделения списка на голову и хвост для вывода на печать всех элементов списка.
Пример.
domains
number_list=integer
predicates
print_list(numbes_list) – предикат печатает список  
clauses 
print_list([  ]).
print_list([H|T]):-write(H), nl, print_list([T]).
goal
number_list=[1, 2, 3, 4, 5], print_list(number_list)  
Или просто:
Print_list([1, 2, 3, 4, 5, 6, 7])

7.12.2. Поиск элементов в списке
Введем предикат «Принадлежит» (member)

Принадлежит (X, L):– L=[H|T], Х=H 

или короче:
Принадлежит(X, [Y|_]):–X=Y
В первом случае X является элементом списка L, если X совпадает с головой списка L. Во втором случае X принадлежит списку, если он содержится в хвосте списка:

Принадлежит (X, L):–L= [Y|T], принадлежит (Х, Т)

При рекурсивном вызове предиката в конце концов реализуется один из двух случаев: либо мы найдем голову в каком-нибудь укороченном списке, либо исчерпаем все элементы и придем к пустому списку и остановимся, т.е. имеется два граничных случая.

Пролог рассматривает рекурсивное обращение предиката «Принадлежит» как попытку найти соответствие для некоторой новой его копии, что предотвращает путаницу переменных.

Имеется три различных варианта  использования предиката «Принадлежит»:
А) memder (X, [a, b, c]) – искать, является ли Х элементом a, b, c.
В) memder (b, X) – искать списки, в которых находятся элементы b.
С) memder (a, [a, b, c]) – проверить истину.

7.12.3. Создание нового списка путем слияния двух списков
Для создания нового списка путем слияния двух списков используется предикат add.
присоединить (A, B, C), C – результат, А, В – исходные списки.
1) Граничное условие-присоединение пустого списка к списку дает сам список
Присоединить ([  ], L, L)
2) Рекурсивное условие: присоединение списка В к концу списка А выполняется так: список В присоединяется к хвосту списка А, а затем спереди добавляется голова списка А.
Присоединить([X|L1], L2, [X, L3]):– присоединить(L1, L2, L3).
Опишем процесс создания объединенного.

Пример.
Присоединить([1, 2, 3], [4, 5], [  ]).
Сравнивает его с первым правилом – неудача.
Сравнивает его со вторым правилом
Х=1
Присоединить ([1|2, 3], [4, 5], [  ]):– присоединить ([2, 3], [4, 5], [  ])
X=2
Присоединить([2|3], [4, 5], [  ]):–присоединить([3], [4, 5], [  ])
головы списка помещаются в стек
Х=3
Присоединить([3| [  ]], [4, 5], [  ]):–присоединить([  ], [4, 5], [  ]
он сравнивается с первым предикатом
Присоединить([  ], [4, 5], [  ]):-присоединить([  ], [4, 5], [4, 5]).
Правило 1 удовлетворено и Turbo Prolog начинает сворачивать рекурсивные вызовы второго правила. Извлекаемые при этом из стека элементы помещаются в качестве головы к первому и третьему списку. Элементы извлекаются в обратном порядке, и значение извлеченного из стека элемента присваивается переменной N одновременно в [N|L1] и [N|L3]. Шаги данного процесса можно представить следующим образом:
присоединить ([ ], [4, 5], [4, 5]),
присоединить([3], [4, 5], [3, 4, 5]),
присоединить([2, 3], [4, 5], [2, 3, 4, 5]),
присоединить([1, 2, 3], [4, 5], [1, 2, 3, 4, 5]).
Присвоение идет рекурсивно до тех пор, пока стек не будет полностью исчерпан.
В английской транскрипции
Append([  ], Q, Q).
Append([X|Xs], Ys, {X|Zs]):–append(Xs, Ys, Zs).
В зависимости от вопроса будут совершаться разные операции, например:

Append([a, b, c], [d, e], Xs) приведет к списку Xs=[a, b, c, d, e]

Append(Xs, [c, d], [a, b, c, d]) дает разность Xs=[a, b].
Предикат member может быть выражен через предикат append в виде: Member(X, Ys):–append(As, [X|Xs], Ys). X является элементом списка Ys, если Ys может быть расщеплен на два списка, причем X является головой второго списка.

7.12.3. Разделение на два списка
Разделение на два списка используется тогда, когда для целей текущей обработки нужна лишь часть списка.
Разделить(M, L, L1, L2) – М – компаратор, – исходный список, L1, L2 – подсписки результата. В L1 помещаются все элементы исходного списка меньшие или равные компаратора, а в L2 – элементы исходного списка, большие компаратора.
Правило разделения списка гласит: очередной элемент извлекается из списка по методу выделения головы, а потом сравнивается с компаратором.
Граничное условие: разделить(_. [  ], [  ], [  ])

Пример.
Компаратор M=40, список   L= [30, 50, 20, 25, 65, 95]
H                T                          L1     L2
30     [50, 20, 25, 65, 95]                 [    ]    [    ]
50     [20, 25, 65, 95]                       [30]    [    ]
20     [25, 65, 95]                             [30]    [50]
[30, 20]     
Задания для самостоятельной работы.