Domains. Treetype = tree(string, treetype, treetype);

treetype = tree(string, treetype, treetype);

empty()

Например, дерево

можно задать следующим образом:

tree(“1”,

tree(“2”,

tree(“4”, empty, empty),

tree(“5”, empty, empty)),

tree(“3”,

tree(“6”, empty, empty),

tree(“7”, empty, empty)))

Списки

Список является набором объектов одного и того же типа. Элементами списка могут быть любые термы – константы, переменные, структуры, которые включают и другие списки. Списковых структур достаточно для большинства вычислений. Списки широко используются для представления деревьев синтаксического разбора, грамматик, карт городов и т. д. Совокупность элементов списка заключается в квадратные скобки ([]), а друг от друга элементы списка отделяются запятыми. Пустой список записывается как [] – открывающая квадратная скобка, за которой следует закрывающая квадратная скобка. Список может быть представлен как специального вида дерево. Список – это либо пустой список, не содержащий ни одного элемента, либо структура, имеющая две компоненты: голову и хвост списка. Головой списка является первый его элемент. Хвост списка представляет список, состоящий из всех элементов исходного списка, за исключением первого его элемента. Конец списка обычно представляют как хвост, который является пустым списком.

Например:

[1, 2, 3]

1 – голова, [2, 3] – хвост списка

2 – голова, [3] – хвост списка

3 – голова, [] – хвост

списка

В языке Пролог введена специальная форма для представления списка с головой X и хвостом Y. Такой список записывается как [X|Y], где для разделения X и Y используется вертикальная черта. При конкретизации структуры подобного вида X сопоставляется с головой списка, а Y – с хвостом списка. В приведенном выше примере при сопоставлении списка
[1, 2, 3] со структурой [X|Y] переменная X примет значение 1, а переменная Y – [2, 3]. Представление списка в виде головы и хвоста было принято для удобной рекурсивной обработки элементов списка.

В языке Паскаль объявить тип list, описывающий список целых чисел можно следующим образом:

typelist = ^TElemList;

TElemList = record;

Inf: char;

Next: list;

end;

В языке Пролог списковый тип объявляется так: