3.Использование списков в Прологе

Список – это упорядоченный набор объектов одного и того же типа. Элементами списка могут быть целые числа, действительные числа, символы, строки, символические имена и структуры. Порядок расположения элементов в списке играет важную роль: те же самые элементы списка, упорядоченные иным способом, представляют уже совсем другой список.

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

Непустой список можно рассматривать как список, состоящий из двух частей: головы – первого элемента списка; и хвоста – остальной части списка. Голова является элементом списка, хвост является списком. Голова списка – это неделимое значение, хвост представляет собой список, составленный из того, что осталось от исходного списка в результате «отделения головы». Этот новый список обычно можно делить и дальше. Если список состоит из одного элемента, то его можно разделить на голову, которой будет этот самый элемент, и хвост, являющийся пустым списком. Пустой список нельзя разделить на голову и хвост.

Операция деления списка на голову и хвост обозначается при помощи вертикальной черты (|):

[Head | Tail].

Head здесь является переменной для обозначения головы списка, переменная Tail обозначает хвост списка (для имен головы и хвоста списка пригодны любые допустимые Прологом имена). Данная операция также присоединяет элемент в начало списка, например, для того , чтобы присоединить X к списку S следует написать [X | S].

Отличительной особенностью описания списков является наличие звездочки (*) после имени домена элементов.

Пример 6: объявление списков, состоящих из элементов стандартных типов доменов или типа структуры.

domains

list1=integer*

list2=char*

list3=string*

list4=real*

list5=symbol*

personal_library = book (title, author, publisher, year)

list6= personal_library*

list7=list1*

list8=list5*

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

Пример 7: демонстрация разделения списков на голову и хвост.

Список	Голова	Хвост
[1, 2, 3, 4, 5]	1	[2, 3, 4, 5]
[6.9, 4.3]	6.9	[4.3]
[cat, dog, horse]	Cat	[dog, horse]
[‘S’, ‘K’, ‘Y’]	‘S’	[‘K’, ‘Y’]
[«PIG»]	«PIG»	[]
[]	Не определена	Не определен

4. Применение списков в программах

4.1 Поиск элемента в списке

Для применения списков в программах на Прологе необходимо описать домен списка в разделе domains, предикаты, работающие со списками необходимо описать в разделе predicates, задать сам список можно либо в разделе clauses либо в разделе goal.

Над списками можно реализовать различные операции: поиск элемента в списке, разделение списка на два списка, присоединение одного списка к другому, удаление элементов из списка, сортировку списка, создание списка из содержимого БД и так далее.

Поиск элемента в списке является очень распространенной операцией. Поиск представляет собой просмотр списка на предмет выявления соответствия между объектом поиска и элементом списка. Если такое соответствие найдено, то поиск заканчивается успехом, в противном случае поиск заканчивается неуспехом. Стратегия поиска при этом будет состоять в рекурсивном выделении головы списка и сравнении ее с объектом поиска.

Пример 8: поиск элемента в списке.

domains

list=integer*

predicates

member (integer, list)

clauses

member (Head, [Head | _ ]).

member (Head, [_ | Tail ]):- member (Head, Tail).

goal

member (3, [1, 4, 3, 2]).

Правило поиска может сравнить объект поиска и голову текущего списка, эта операция записана в виде факта предиката member. Этот вариант предполагает наличие соответствия между объектом поиска и головой списка. Отметим, что хвост списка в данном случае не важен, поэтому хвост списка присваивается анонимной переменной. Если объект поиска и голова списка различны, то в результате исполнения первого предложения будет неуспех, происходит возврат и поиск другого правила или факта, с которыми можно попытаться найти соответствие. Для этой цели служит второе предложение, которое выделяет из списка следующий по порядку элемент, то есть выделяет голову текущего хвоста, поэтому текущий хвост представляется как новый список, голову которого можно сравнить с объектом поиска. В случае исполнения второго предложения, голова текущего списка ставится в соответствие анонимной переменной, так как значение головы с писка в данном случае не играет никакой роли.

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

member (Head, [Head |_ ]):- !.

Отсечение отменяет действие механизма возврата, поэтому поиск альтернативных успешных решений реализован не будет.