Представление списков. Список - это простая структура данных, широко используемая в нечисловом программировании

Список - это простая структура данных, широко используемая в нечисловом программировании. Список - это последовательность, составленная из произвольного числа элементов, например энн, теннис, том, лыжи. На Прологе это записывается так:

[ энн, теннис, том, лыжи ]

Каким образом можно представить список в виде стандартного прологовского объекта? Мы должны рассмотреть два случая: пустой список и не пустой список. В первом случае список записывается как атом [ ]. Во втором случае список следует рассматривать как структуру состоящую из двух частей:

(1) первый элемент, называемый головой списка;

(2) остальная часть списка, называемая хвостом.

Например, для списка

[ энн, теннис, том, лыжи ]

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

[ теннис, том, лыжи ]

Подытожим:

• Список - это структура данных, которая либо пуста, либо состоит из двух частей: головы и хвоста. Хвост в свою очередь сам является списком.
• Список рассматривается в Прологе как специальный частный случай двоичного дерева. Для повышения наглядности программ в Прологе предусматриваются специальные средства для списковой нотации, позволяющие представлять списки в виде
  [ Элемент1, Элемент2, ... ]
  или
  [ Голова | Хвост ]
  или
  [ Элемент1, Элемент2, ... | Остальные]

Некоторые операции над списками

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

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

Составление программы для отношения принадлежности может быть основано на следующих соображениях:

· (1) Х есть голова L, либо

· (2) Х принадлежит хвосту L.

· Это можно записать в виде двух предложений, первое из которых есть простой факт, а второе - правило:

· принадлежит( X, [X | Хвост ] ).

· принадлежит ( X, [Голова | Хвост ] ) :-
принадлежит( X, Хвост).

Сцепление ( конкатенация)

Для сцепления списков мы определим отношение

Конк( L1, L2, L3)

Здесь L1 и L2 - два списка, a L3 - список, получаемый при их сцеплении.

На прологе это можно записать следующим образом:

конк( [X | L1, L2, [X | L3]):-
конк( L1, L2, L3).