Пролог как вывести список

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

Список в Prolog’е заключается в квадратные скобки и элементы списка разделяются запятыми. Список, который не содержит ни одного элемента, называется пустым списком.

список, элементами которого являются целые числа

список, элементами которого являются символы

список, элементами которого являются строки

Для работы со списками с Prolog’е не существует отдельного домена, для того, чтобы работать со списком, необходимо объявить списочный домен следующим образом:

listdomain — это произвольно выбранное имя нестандартного списочного домена, elementdomain — имя домена, которому принадлежит элемент списка, звездочка * как раз и обозначает, что выполнено объявление списка, состоящего из элементов домена element. При работе со списками нельзя включать в список элементы, принадлежащие разным доменам. В таком случае нужно воспользоваться составным доменом.

Примеры объявления списочных доменов:

Обратите внимание, что при объявлении составного домена были использованы функторы, так как объявление вида mixdomain=integer; symbol; string привело бы к ошибке.

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

Голова списка — первый элемент списка;
Хвост списка — все последующие элементы, являющиеся, в свою очередь списком.

Примеры голов и хвостов списков:

В Prolog’е используется специальный символ для разделения списка на голову и хвост — вертикальная черта |.

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

Примеры сопоставления и унификации в списках:

Так как список является рекурсивной структурой данных, то для работы со списками используется рекурсия. Основной метод обработки списков заключается в следующем: отделить от списка голову, выполнить с ней какие-либо действия и перейти к работе с хвостом списка, являющимся в свою очередь списком. Далее у хвоста списка отделить голову и так далее до тех пор, пока список не останется пустым. В этом случае обработку списка необходимо прекратить. Следовательно, предикаты для работы со списками должны иметь по крайней мере два предложения: для пустого списка и для непустого списка.

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

Результат работы программы:

Еще один пример работы со списком — подсчет числа элементов списка или, другими словами, определение длины списка. Для того, чтобы определить длину списка, вновь нужно рассмотреть два случая: для пустого и непустого списков. Если список пуст, то его длина равна 0, если же список не пуст, то определить его длину можно следующим образом: разделить список на голову и хвост, подсчитать длину хвоста списка и увеличить это длину хвоста на единицу (то есть учесть отделенную предварительно голову списка.)

Результат работы программы:

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

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

Результат работы программы:

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

Результат работы программы:

Еще один пример, который будет рассмотрен, это решение задачи соединения двух списков. Итак, каким образом можно объединить два списка? Предположим, имеется два двухэлементных списка: [1, 2] и [3, 4]. Объединение нужно начать с последовательного отделения голов первого списка до тех пор, пока первый список не станет пустым. Как только первый список станет пустым, его легко можно будет объединить со вторым, непустым, никоим образом к этому моменту не изменившимся списком. В результате, естественно, будет получен список, полностью совпадающий со вторым. Все, что осталось сделать, это добавить головы, отделенные от первого списка, ко второму списку. Вот как это выглядит в пошаговом описании:

отделяется голова от первого списка — [1, 2] -> [1 | [2]] (голова — 1, хвост — [2])
продолжается выполнение отделение головы, только теперь от полученного хвоста — [ 2] -> [2 | [ ]] (голова — 2, хвост — [ ])
когда первый список разобран до пустого, можно приступить к его объединению со вторым, непустым списком, объединяются пустой хвост [ ] и непустой второй список [3, 4] — получается тоже непустой список — [3, 4], теперь можно приступать к формированию объединенного списка, так как основа для списка-результата заложена, это его будущий хвост — [3, 4]
к хвосту списка-результата [3, 4] добавляется последняя отделенная от первого списка голова 2, что дает следующий список — [2, 3, 4]
все, что осталось сделать, это добавить к списку [2, 3, 4], который получился на предыдущем шаге, голову 1, которая была отделена самой первой и получается объединенный список [1, 2, 3, 4]

Теперь текст программы:

Результат работы программы:

Последний пример, который будет рассмотрен, это сортировка списка методом «пузырька».

Сначала текст программы:

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

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

Источник

Списки в Прологе

В императивных языках, как правило, основной структурой данных являются массивы. В Прологе – это списки.

Список – последовательность элементов одного типа. Задается перечислением элементов через запятую в квадратных скобках. Например, [джек, джон, фред] или [3,1,8,0,34,9] или [‘a’, ‘b’, ‘c’, ‘d’].

Запись [] обозначает пустой список, т.е. не содержащий элементов.

Элементы списка могут иметь любой тип (числа, строки, символы). В частности, элементами списка могут быть сами списки.

Чтобы использовать список, надо сначала описать его тип. Новые типы данных, которые вводит пользователь, описываются в разделе Domains (аналогичен разделу Type в Паскале и помещается вначале программы).

Например (звездочка обозначает список),

intlist = integer* % новый тип – список из целых чисел

symlist = symbol* % новый тип – список из строк

Любой список, кроме пустого, можно разбить на «голову» – первый элемент этого списка, и «хвост» – все его остальные элементы. Хвост списка – всегда список, а голова – всегда элемент.

Например, голова списка [3, 1, 8, 0, 34, 9] – число 3, а хвост – список [1, 8, 0, 34, 9] . Голова списка [3] – число 3, а хвост – пустой список [] .

Если достаточное число раз отделить первый элемент списка, то получим пустой список. Операция «|» как раз позволяет разделить список на хвост и голову или, наоборот, приписать элемент (элементы) к началу списка.

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

1. Выведите список из целых чисел

Предикат имеет один аргумент – список, который необходимо вывести.

Источник

Главная

ПРОЕКТ «ЧЕЛОВЕК. ЗЕМЛЯ. ВСЕЛЕННАЯ»

Инструменты пользователя

Инструменты сайта

Боковая панель

Содержание

Списки

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

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

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

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

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

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

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

Атрибуты списка

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

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

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

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

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

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

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

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

В списке [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]

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

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

Графическое представление списков

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примеры

Метода разделения списка на голову и хвост

Задание цели в виде 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 обозначает хвост списка. Для имен головы и хвоста списка пригодны любые допустимые Прологом имена.

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

Примеры

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

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

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

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

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

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

Примеры

Деление списков

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

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

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

Предположим, что вначале значением переменной Мiddle является число 40, переменной L присвоен список [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].

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

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

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

Примеры

Присоединение (слияние) списков

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

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

Примеры

Сортировка списков

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

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

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

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

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

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

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

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

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

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

Примеры

Компоновка данных в список

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

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

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

Примеры

Заключение

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

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

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

Источник