Пролог работа со списками

Пролог работа со списками

На этом шаге мы рассмотрим работу со списками.

В Прологе есть способ явно отделить голову от хвоста. Вместо разделения элементов запятыми, это можно сделать вертикальной чертой "|". Например: и, продолжая процесс, Можно использовать оба вида разделителей в одном и том же списке при условии, что вертикальная черта есть последний разделитель. При желании можно набрать [а,b,с,d] как [a,b| [c,d]]. В таблице 1 вы найдете другие примеры.

Таблица 1. Головы и хвосты списков

Список Голова Хвост
[‘a’,’b’,’с’] ‘a’ [‘b’,’с’]
[‘a’] ‘a’ [] % пустой список
[ ] Не определена Не определен
[[1,2,3], [2,3,4],[ ]] [1,2,3] [[2,3,4],[ ]]

В таблице 2 приведены несколько примеров на присвоение в списках.

Таблица 2. Присвоение в списках

Список 1 Список 2 Присвоение переменным
[X,Y,Z] [эгберт, ест,мороженое] Х=эгберг, У=ест, Z=мороженое
[7] [X | Y] Х=7,Y=[ ]
[1,2,3,4] [X, Y | Z] X=1, Y = 2, Z = [3,4]
[1,2] [3|X] fail % неудача

На следующем шаге мы начнем рассматривать использование списков.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Читайте также:  Delphi excel вставить строку

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

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

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

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

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

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

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

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

Читайте также:  Настройка почтовых серверов в outlook

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

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

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

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

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

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

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

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

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

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

  1. Предикат append(List1, List2, List12) является успешным, если выполняет конкатенацию списков List1 и List2 в список List12 (Успешен, если заданы списки соответствующие преобразованию).
  2. Предикат member(Element, List) успешен, если Element есть в списке List. А также может использоваться для организации перебора.
  3. Встроенный предикат reverse(List1, List2) порождает список List2 из элементов списка List1 , переставленных в обратном порядке. Успешен, если заданы списки соответствующие преобразованию.
  4. delete(List1, Element, List2) порождает список List2 из элементов списка List1 за исключением всех элементов Element . Успешен, если заданы списки соответствующие преобразованию.
  5. select(Element, List1, List2) Удаляет одно вхождение элемента и порождает дочерний список. Может использоваться для перебора вариантов. Успешен, если заданы списки соответствующие преобразованию.
  6. permutation(List1, List2) Успешен, если List2 есть перестановка списка List1 . Предикат может использоваться для генерации перестановок.
  7. prefix(Prefix, List) Успешен, если Prefix — начало списка List . Если Prefix — переменная, то генерируется набор префиксов (списков), включая "пустой список" и весь исходный список "целиком".
  8. Аналогично, работает suffix(Suffix, List) (только работает с "концом" списка — суффиксом).
  9. sublist(List1, List2) — успешен, если List2 есть суб-список List1 . Если дать неконкретизированную переменную, сгенерирует набор подсписков.
  10. last(List,Element) — успешен, если заданный элемент последний в списке. Если дать непроинициализированную переменную — извлечет последний элемент:
  11. length(List, Length) — успешен, если Length — длинна списка. Если дать не конкретезированную переменную, предикат вернет длинну списка.
  12. nth(N, List, Element) — работа с N — элементом списка. Успешен если он Element, если его дать не конкретизированной переменной — вернет заданный элемент списка:
  13. min_list(List, Min) успешен если Min наименьшее число в List .
    max_list(List, Max) успешен если Max наибольшее число в List .
    sum_list(List, Sum) успешен если Sum сумма всех элементов в List .

Если дать не конкретизированную переменную — поиск искомой величины!

Читайте также:  Зачем нужен рендеринг видео
  • sort(List1, List2) успешен, если List2 есть отсортированный по возрастанию список List1 , причем дублирующиеся элементы объединяются в один! Если Вам не требуется объединение элементов — используйте sort0(List1, List2) :
  • keysort(List1, List2) succeeds if List2 is the sorted list of List1 according to the keys. The list List1 consists of items of the form Key-Value. These items are sorted according to the value of Key yielding the List2. Duplicate keys are not merged. This predicate is stable, i.e. if K-A occurs before K-B in the input, then K-A will occur before K-B in the output.
  • bagof, setof и findall

    Однако, есть возможность, собрать все решения в список. Встроенные предикаты bagof (набор) и setof (множество) обеспечивают такую возможность. Вместо них иногда используют findall (найти все).

    Например, у нас есть набор следующих фактов:

    setof(X,p,C) порождает отсортированный (упорядоченный) список решений, в котором повторяющиеся решения объединены в один элемент. Упорядочение происхлдит по алфавиту, или по отношению ‘

    Ссылка на основную публикацию
    Программы похожие на муви мейкер
    Если Windows Movie Maker вам не подходит, есть несколько альтернатив, которые больше подходят вашим специфическим требованиям. Для вдохновленных кинопроизводителей важно...
    Приложение расплачиваться телефоном в магазине андроид
    Многие из Вас наверняка не раз видели, как некоторые люди оплачивают свои покупки в магазине или проезд в общественном транспорте,...
    Приложение гид по москве
    Время долгих прогулок настало! Очень надеемся, что в этом году Москва предстанет перед своими жителями и гостями в полной красоте,...
    Продажа авто гражданину белоруссии
    Авторы статьи: Коллектив компании AMB MOTORS www.ambmotors.ru +7(495) 724-10-44 В последнее время в Москве автомобили с пробегом все чаще стали...
    Adblock detector