мы рассматриваем два случая – пустой список и непустой список.
Непустой список следует рассматривать как структуру, состоящую из двух частей - головы и хвоста, при этом хвост тоже список, который либо пуст, либо имеет свою голову и хвост.
Одноэлементный список [a]- не то же самое, что элемент, который в него входит, так как [a] –на самом деле – это составная структура данных:
List
/ \
a []
Список в Прологе рассматривается как частный случай двоичного дерева.
При построении списков необходимо наличие константного символа, чтобы рекурсия не была бесконечной. Таким символом является символ [], обозначающий пустой список.
Требуется также функтор арности два [X|Y],где X и Y-компоненты терма, имеющие специальные названия: X – голова(car),а Y-хвост (cdr) списка.
Определение списка
list([]).
list([Head|Tail]):-
list(Tail).
Например, список [a,b,c] – это терм [H|T] при подстановке H=a и T=[b,c].
list([a,b,c])
|
list([b,c])
|
list([c])
|
list([])
Рис 6.2.Дерево вывода при проверке списка
Таблица 6.1. Примеры разделения списка на голову и хвост
|
|
список | голова | хвост |
[[1,2],[2,3,4],[]] | [1,2] | [[2,3,4],[]] |
[] | Не определен | Не определен |
[3] | [] |
Таблица 6.2.Примеры сопоставления двух списков:
Список 1 | Список 2 | Присвоение переменным |
[X,Y,Z] | [2,3,4] | X=2,Y=3,Z=4 |
[5] | [X|Y] | X=5,Y=[] |
[1,2,3,4] | [X,Y|Z] | X=1,Y=2,Z=[3,4] |
[1,2] | [3|X] | fail |
Использование списков отразится в программе на трех ее разделах:
1 domains
<описание домена списка>
2 predicates
<описание работающего со списком предиката>
3 clauses
<задание самого списка>
Операции над структурами данных типа список.
1 Принадлежность списку
2 Определение длины списка.
3 Вывод списка на печать
4 Модификация списка
5 Деление списка(X,L,L1,L2)
6 Удаление элемента из списка (X,L1,L2)
7 Объединение списков(L1,L2,L3)
8 Cортировка списков