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

Пролог позволяет выполнять со списком целый ряд операций:

• доступ к объектам списка;
• проверка на принадлежность к списку;
• разделение списка на два;
• слияние двух списков;
• сортировку элементов списка в порядке возрастания или убывания.

Списки бывают полезны при создании баз знаний (баз данных), экспертных систем, словарей.

Список является набором объектов одного и того же доменного типа. Объектами списка могут быть:

• целые числа;
• действительные числа;
• символы;
• символьные строки;
• структуры.

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

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

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

[1,2,3,6,9,3,4]
[3.2,4.6,1.1,2.64,100.2]
["YESTERDAY","TODAY","TOMORROW"]

Объекты списка называются элементами списка. Список может содержать произвольное число элементов, единственным ограничением является лишь объем оперативной памяти.

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

В Прологе список [«JOHN WALKER»,3.50,45.50] некорректен ввиду того, что составлен из элементов разных типов. Списки структур являются исключением из правила.

Количество элементов в списке называется его длиной. Длина списка [«MADONNA»,«AND»,«CHILD»] равна 3. Длина списка [4.50,3.50,6.25,2.9,100.15] равна 5. Список может содержать всего один элемент и даже не содержать элементов вовсе:

[«summer»]
[]

Список, не содержащий элементов, называется пустым или нулевым списком.

Непустой список можно рассматривать как состоящий из двух частей:

1. первый элемент списка - его голова;
2. остальная часть списка - хвост.

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

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

В списке [4.50,3.50,6.25,2.9,100.15] например, головой является значение 4.50, а хвостом - список [3.50,6.25,2.9,100.15] Этот список в свою очередь имеет и голову, и хвост. Голова - это значение 3.50, хвост - список [6.25,2.9,100.15]

Таблица. Головы и хвосты различных списков

Графическое представление списков является полезным наглядным вспомогательным средством при проектировании доменных структур и задании данных для программ на Прологе. Его также используют при документировании прикладных программ и системного матобеспечения.

Первый способ графического представления списков - это изображение списка при помощи линейного графа. Рассмотрим следующее утверждение:

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

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

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

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

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

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

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

Для того чтобы использовать в программе список, необходимо описать предикат списка. Примеры таких предикатов:

num([1,2,3,6,9,3,4])
realnum([3.2,4.6,1.1,2.64,100.2])
time(["YESTERDAY","TODAY","TOMORROW"])

В этих выражениях num, realnum и time все представляют предикаты списков. Предикатам списков обычно присваиваются имена, которые характеризуют либо тип элемента (num), либо сами данные (time).

Введение списков в программу с необходимостью отражается на трех ее разделах. Домен списка должен быть описан в разделе domains, а работающий со списком предикат - в разделе predicates. Нужно ввести (задать) сам список: либо в разделе clauses, либо в разделе goal.

Каждый элемент приведенного ниже списка обозначает одну из птиц.

birds([«sparrow», «robin», «mockingbird», «thunderbird», «bald eagle»]).

Если этот список необходимо использовать в программе, то следует описать домен элементов списка; ему логично присвоить имя подобное name_birds (названия птиц). Список может содержать много элементов, может содержать один элемент, а может не содержать ни одного.

Отличительной особенностью описания списка является наличие звездочки (*) после имени домена элементов. Так запись bird_name * указывает на то, что это домен списка, элементами которого являются bird_name, т. е. запись bird_name * следует понимать как список, состоящий из элементов домена bird_name.

Описание в разделе domains, следовательно, может выглядеть либо как:

bird_list = bird_name *
bird_name = symbol

либо как

bird_list = symbol *

Домен bird_list является доменом списка элементов типа symbol (списка птиц).

В разделе описания предикатов predicates требуется присутствия имени предиката, а за ним заключенного в круглые скобки имени домена.

birds(bird_list)

Как видим, описание предиката списка ни в чем не отличается от описания обычного предиката.

Сам список присутствует в разделе утверждений clauses:

birds(["sparrow","robin","mockingbird","thunderbird", "bald eagle"]).

• Программа "Списки" - демонстрация работы со списками: вывод содержимого списка, вывод отдельных элементов списка.

Задание цели в виде birds(All) обеспечит присваивание переменной All всего списка в целом. Цель birds([_,_,_,B,_]) позволит извлечь из списка лишь один элемент. В этом случае, однако, требуется точное знание числа элементов списка, являющегося объектом предиката birds. Если задать цель в виде birds([B1,B2,B3]), то цель не будет удовлетворена ввиду несоответствия между количеством элементов в списке и количеством элементов в целевом утверждении.

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

Например в списке [4,-9,5,3] головой является элемент 4, а хвостом - список [-9,5,3]. Головой нового списка будет уже число -9, хвостом - список [5,3]. Этот список также имеет голову (5) и хвост ([3]). Наконец, список [3] состоит из головы - числа 3 и хвоста, являющегося пустым списком.

Неоднократное разделение списка на голову и хвост играет важную роль в программировании на Прологе.

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

[Head|Tail].

Head здесь является переменной для обозначения головы списка, переменная Tail обозначает хвост списка. Для имен головы и хвоста списка пригодны любые допустимые Прологом имена.

Рекурсивные правила для работы со списками просты, но вместе с тем и очень важны, ввиду их применимости в большинстве программ.

• Программа "Голова-хвост списка" - демонстрация метода разделения списка на голову и хвост.

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

Для сопоставления объекта поиска с элементами просматриваемого списка необходим предикат, объектами которого и являются эти объект поиска и список:

find_it(3 ,[1,2,3,4,5]).

Первый из объектов утверждения, 3, есть объект поиска. Второй - это список [1,2,3,4,5].

Для выделения элемента из списка и сравнения его с объектом поиска можно применить метод разделения списка на голову и хвост. Стратегия поиска при этом будет состоять в рекурсивном выделении головы списка и сравнении ее с элементом поиска.

Так же как в программе «Голова-хвост списка», при рекурсии хвостом каждый раз становится новый список, голова которого присваивается переменной, сравниваемой с объектом поиска.

• Программа Программа "Поиск элемента в списке" - демонстрация метода поиска элемента в списке методом деления списка на голову и хвост.

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

При делении списков используется предикат split, аргументами которого являются элемент данных и три списка:

split(Middle,L,L1,L2).

• элемент Мiddle - компаратор
• L - исходный список
• L1 и L2 - подсписки, получающиеся в результате деления списка L.

Если элемент исходного списка меньше или равен Middle, то он помещается в список L1; если больше, то в список L2.

Предположим, что вначале значением переменной Мiddle является число 40, переменной L присвоен список [30,50,20, 25,65,95], а переменные L1 и L2 не инициализированы.

split(40,[30,50,20,25,65,95],L1,L2).

Правило для разделения списка должно быть написано таким образом, чтобы элементы исходного списка, меньшие либо равные 40, помещались в список L1, а большие 40 - в список L2.

Правило устроено следующим образом: очередной элемент извлекается из списка при помощи метода разделения списка на голову и хвост, а потом сравнивается с компаратором Middle.

Если значение этого элемента меньше или равно значению компаратора, то элемент помещается в список L1, в противном случае - в список L2.

В результате применения правила к списку [30,50,20,25,65,95] значениями списков L1 и L2 станут соответственно [30,20,25] и [50,65,95].

Само правило для разделения списка записывается в Прологе следующим образом:

split(Middle,[Head|Tail],[Head|L1],L2) :- Head <= Middle, split(Middle,Tail,L1,L2). 
split(Middle,[Head|Tail],L1,[Head|L2]) :- split(Middle,Tail,L1,L2), Head > Middle.
split(_,[],[],[]).

Метод деления списка на голову и хвост используется в данном правиле как для разделения исходного списка, так и для формирования выходных списков.

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

• Программа Программа "Деление списка" - демонстрация деления списка на два списка методом деления списка на голову и хвост.

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

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

• Программа Программа «Присоединение списков» - демонстрация присоединения одного списка к другому.

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

Существует много способов сортировки списков. Рассмотрим, например, список целых чисел:

[51,23,84,17,11]

Элементы этого списка не расположены в каком-то определенном порядке в обычном понимании этого слова. Тот же самый список, но уже отсортированный в порядке возрастания элементов, выглядит так:

[11,17,23,51,84]

Сортирующее правило Пролога принимает на вход неотсортированный список, и выдает отсортированный на выходе.

Входной список называется исходным, выходной - целевым.

Три метода обычно применяются для сортировки списков:

• метод перестановки
• метод выборки
• метод вставки.

Сортировку можно произвести любым из трех названных методов или их комбинацией.

Метод перестановки заключается в перестановке элементов списка до тех пор, пока они не выстроятся в нужном порядке.

Метод выборки включает в себя многократную выборку и перемещение элементов списка.

Метод вставки осуществляется при помощи неоднократной вставки элементов в список до тех пор, пока он не будет упорядочен. Этот метод особенно удобен для реализации на Прологе.

• Программа Программа "Сортировка списка - метод вставки" - демонстрация сортировки списка при помощи вставок для целочисленных списков.

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

Требуемый список представляется означенной переменной, являющейся одним из объектов предиката. Предописание встроенного предиката findall выглядит следующим образом:

findall(Variable_name,Predicate_expression,List_name).

Variable_name обозначает здесь объект входного предиката Predicate_expression,а List_name является именем переменной выходного списка. Переменная должна относиться к домену списков, объявленному в разделе domains.

• Программа Программа «Компоновка данных» - демонстрация компоновки данных в список с целью вычисления среднего значения с помощью предиката findall.

Рекомендуем не пропускать предлагаемые упражнения, которые призваны углубить понимание основных структур и техники программирования. Упражнения помогают также научиться модифицировать демонстрационные программы с целью приспособить их к своим нуждам.

Чтение главы является обязательным, если вы собираетесь использовать списки в ваших программах, так как представленные здесь методы находят самое широкое применение при разработке программ на Прологе.

Эти методы можно применять даже в том случае, если вы не понимаете до конца механизм их работы, хотя, конечно, понимание сделает Вам честь как программисту.

!!Рекомендуем: Семейная Энциклопедия Здоровья ⇒ Что должен знать современный человек? ⇒ Самоанализ. Работа над собой ⇒ Оглавление ⇒ Главная сайта