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

Встроенные предикаты для работы со списками

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

  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) порождает отсортированный (упорядоченный) список решений, в котором повторяющиеся решения объединены в один элемент. Упорядочение происхлдит по алфавиту, или по отношению ‘

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

    Список, содержащий числа 1, 2 и 3, записывается так:[1, 2, 3]

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

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

    Объявление списков

    Чтобы объявить домен для списка целых, надо использовать декларацию домена, такую как:

    Символ (*) означает "список чего-либо"; таким образом, integer* означает "список целых".

    Элементы списка могут быть любыми, включая другие списки. Однако все его эле­менты должны принадлежать одному домену. Декларация домена для элементов должна быть следующего вида:

    Здесь elements имеют единый тип (например: integer, real или symbol) или явля­ются набором отличных друг от друга элементов, отмеченных разными функторами.

    Работа со списками

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

    [а, b, с] эквивалентно [а | [b, с]] и. продолжая процесс,

    [а | [b, с] ] эквивалентно [а | [b] [с] ] ], что эквивалентно [а | [b | [с | [ ] ] ] ]

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

    Печать списков

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

    Преобразование списков

    Принадлежность к списку

    Предположим, что у вас есть список имен John, Leonard, Eric и Franc, и вы хотите проверить, имеется ли заданное имя в этом списке. Другими словами, вам нужно выяснить отношение "принадлежность" между двумя аргумен­тами — именем и списком имен. Это выражается предикатом

    member(name,namelist) . % "name" принадлежит "namelist"

    Не нашли то, что искали? Воспользуйтесь поиском:

    Лучшие изречения: Студент — человек, постоянно откладывающий неизбежность. 10805 — | 7380 — или читать все.

    91.146.8.87 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

    Отключите adBlock!
    и обновите страницу (F5)

    очень нужно

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    Еще один пример, который будет рассмотрен, это решение задачи соединения двух списков. Итак, каким образом можно объединить два списка? Предположим, имеется два двухэлементных списка: [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]

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

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

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

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

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

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

    Эффективная работа со списками