Программирование на языке пролог

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

Аналогично список, состоящий из атомов a, bи с, мог бы быть записан как .(а,.(b,.(с,[]))), что изображается следующим образом:

Иногда функтор точка ('.') определяется как оператор, так что допустимо для Пролога два последних списка записать как а.[]и а.(b.(с.[]))). Второй список можно было бы записать просто как а.b.с.[], так как функтор точка – правоассоциативный оператор. Списки являются упорядоченными последовательностями элементов, так что список а.bотличается от списка b.а.

Некоторые любят записывать древовидные диаграммы списков в виде дерева, «растущего» слева направо, ветви которого направлены вниз. Приведенный выше список, представленный диаграммой в виде такой «виноградной лозы» выглядит так:

В этой диаграмме компонента функтора '.', соответствующая голове списка, «свисает» вниз, а компонента, соответствующая хвосту списка, «растет» вправо. Конец списка четко выделен тем, что последняя компонента – хвост списка – является пустым списком. Главное преимущество использования диаграммы для представления списка заключается в том, что она может быть записана справа налево на листе бумаги.

«Виноградная» диаграмма может оказаться удобной для записи списков на бумаге, когда нам необходимо видеть структуру списка, но в программах на Прологе для записи списков такие диаграммы не используются. Так как запись сложных списков с помощью функтора '.' часто оказывается неудобной, то в Прологе предусмотрена другая синтаксическая форма, которая может быть использована для записи списков в программе. Это так называемая скобочная форма записи списка.Она представляет собой заключенную в квадратные скобки последовательность элементов списка, разделенных запятыми. Например, упоминавшиеся выше списки могут быть записаны в скобочной форме в виде [а]и [а, b, с]. Списки могут содержать другие списки или переменные. Например, в Прологе допустимы следующие списки:

[]

[конкретный, человек, [любит, ловить, рыбу]]

[а, V1, b, [X, Y]]

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

Чтобы продемонстрировать структуру списков, содержащих в качестве элементов другие списки, приведем «виноградную» диаграмму для последнего из рассмотренных списков:

Из приведенной диаграммы ясно видно, что каждый ее горизонтальный уровень является списком, состоящим из некоторого числа элементов. Верхний уровень на приведенной диаграмме представляет список, содержащий четыре элемента, один из которых сам является списком. Второй уровень, содержащий два элемента, представляет четвертый элемент списка верхнего уровня. Работа со списками основана на расщеплении их наголовуи хвостсписка. Голова списка – это первый аргумент функтора '.', который используется для конструирования списка. Хвост списка – это второй аргумент функтора '.'. В случае когда для записи списка используется скобочная форма записи, головой списка является первый его элемент. Хвост списка представляет список,состоящий из всех элементов исходного списка, за исключением первого его элемента. Следующие примеры демонстрируют расщепление списков на голову и хвост:

Список	Голова	Хвост
[а, b, с]	а	[b, с]
[а,]	а	[]
[]
[[эта, кошка], сидела]	[эта, кошка]	[сидела]
[эта, [кошка, сидела]]	эта	[кошка, сидела]]
[эта, [кошка, села], на пол]	эта	[кошка, села], на пол]
[X+Y, х + y]	X + Y	[x + y]

Заметим, что пустой список не имеет ни головы, ни хвоста. В последнем примере оператор ± используется как функтор для структур +(Х, Y)и +(х,у).

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

p([1, 2, 3]).

p([эта, кошка, сидела, [на, этой, подстилке]]).

?- p([X|Y]).

X = 1 Y=[2,3]

;

X=эта Y=[кошка, сидела, [на, этой, подстилке]]

?- p([_,_,_,[_|X]]).

X=[этой, подстилке]

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

1-8910111213141516171819202122-83

© 2024 xBook

Почта для связи: [e-mail]

Список 1	Список 2	Конкретизация
[X, Y, Z]	[джону,нравится,рыба]	X=джону Y= нравится Z = рыба
[кошка]	[X| Y]	X= кошка
[X, Y | Z]	[мэри,нравится,вино]	X = мэри Y = нравится Z = [вино]
[[этот, Y]|Z]	[[X, заяц], [находится, здесь]]	X = этот Y = заяц Z = [[находится_ здесь]]
[X, Y|Z, W]	(синтаксически некорректная конструкция списка)