ВНУТРЕННЕЕ ПРЕДСТАВЛЕНИЕ СПИСКОВ

Рассмотрим следующее утверждение:

number([66,84,12,32]).

Объектом предиката number является четырехэлементный список. Голова этого списка есть число 66, хвост — список [84,12,32]. Нумерация списка начинается с головы и заканчивается на его последнем элементе, числе 32.

Внутренним Турбо-Прологовским представлением этого списка является бинарное дерево (рис 6.1).

рис. 6.1

Функтор списка, number, является корнем этого дерева. От корня отходят две ветви. Левая заканчивается листом со значением 66. Правая ветвь кончается узлом, из которого расходятся еще две ветви. Левая кончается значением 84, правая опять разветвляется на две ветви. На левой из них располагается лист со значением 12, правая ветвится еще раз. Левая из этих ветвей ведет к листу со значением 32, правая заканчивается пустым списком.

Очередность, в которой элементы связаны друг с другом, начинается с корня дерева. Лист самой левой ветви дает первый элемент списка. Затем очередность при посредстве узла правой ветви переходит на следующую левую ветвь, на ее листе находится второй элемент списка, 84. Аналогично нумеруются и все остальные элементы вплоть до последнего, 32. Так как больше неупорядоченных элементов не остается, то дерево оканчивается ветвью с пустым списком.

Изображение в виде бинарного дерева бывает особенно полезным для нагядной интерпретации процесса возврата в виде направленного перебора ветвей дерева.

Упражнение 6.1.

1. Различаются ли с точки зрения Турбо-Пролога два таких списка:

[63,29,24,27,86]

[63,24,29,27,86]

2. Можно ли назвать корректным следующий список:

student([”МГМА”,"Смирнов",”2204”,1995])