Список – это рекурсивный составной объект, поэтому

мы рассматриваем два случая – пустой список и непустой список.

Непустой список следует рассматривать как структуру, состоящую из двух частей - головы и хвоста, при этом хвост тоже список, который либо пуст, либо имеет свою голову и хвост.

Одноэлементный список [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ортировка списков