|
НАЗАД
На самом деле вертикальная черта имеет более общий смысл: мы можем перечислить любое количество элементов списка, затем поставить символ «|», а после этого - список остальных элементов. Так, только что рассмотренный пример можно представить следующими различными способами:
[а,b,с] = [а|[b,c]] = [а,b|[с]] = [а,b,с|[]]
Итак:
Список - это структура данных, которая либо дуста, либо состоит из двух частей: головы и хвоста. Хвост, в свою очередь, сам является списком.
Список рассматривается в Прологе как специальный частный случай двоичного дерева. Для повышения наглядности программ в Прологе предусматриваются специальные средства для списковой нотации, позволяющие представлять списки в виде
[ Элемент1, Элемент2, ... ]
или
[ Голова | Хвост ]
или
[ Элемент1, Элемеит2... | Остальные]
Унификация списков. Некоторые операции над списками
Списки представляют собой частный случай составных термов, и их унификация выполняется по общим правилам унификации составных термов. Списки успешно унифицируются, если они имеют одинаковую длину и соответствующие элементы этих списков попарно успешно сопоставимы.
Примеры унификации списков.
1) ? ¾ [a]=[].
No
Списки имеют разную длину, унификация невозможна, так как [a] является списком из одного элемента, а [] ¾ пустой список.
2) ? ¾ [L]=[a].
L=a
yes
Списки имеют одинаковую длину, переменная L и терм а успешно унифицируются, и переменная L конкретизируется значением а.
3) ? ¾ [L]=[a, b, с].
No
Списки имеют разную длину, переменная L обозначает один элемент списка, а другой операнд операции сопоставления является списком из трех элементов.
4) ? ¾ [a|L]=[a, b, с].
L=[b,c]
Yes
Унификация успешна, списки имеют одинаковые первые элементы, переменная L, обозначающая хвост первого списка, успешно сопоставляется и конкретизируется значением [b,c], списком, который является хвостом второго списка.
Списки можно применять для представления множеств, хотя и существует некоторое различие между этими понятиями: порядок элементов множества не существенен, в то время как для списка этот порядок имеет значение; кроме того, один и тот же объект может встретиться в списке несколько раз. Однако наиболее часто используемые операции над списками аналогичны операциям над множествами. Среди них:
- проверка, является ли некоторый объект элементом списка, что соответствует проверке объекта на принадлежность множеству;
- конкатенация (сцепление) двух списков, что соответствует объединению множеств;
- добавление нового объекта в список или удаление некоторого объекта из него.
|
