Список1 = [а, b, с]
Список2 = [а, b, с]
?- Увлечения1 = .( теннис, .(музыка, [] ) ),
Увлечения2 = [лыжи, еда],
L = [энн, Увлечения1, том, Увлечения2].
Увлечения1 = [теннис, музыка]
Увлечения2 = [лыжи, еда]
L = [энн, [теннис, музыка], том, [лыжи, еда]]
Рис. 3.1. Представление списка [энн, теннис, том, лыжи] в виде дерева.
Приведенный пример также напоминает вам о том, что элементами списка могут быть любые объекты, в частности тоже списки.
На практике часто бывает удобным трактовать хвост списка как самостоятельный объект. Например, пусть
L = [а, b, с]
Тогда можно написать:
Хвост = [b, с] и L = .(а, Хвост)
Для того, чтобы выразить это при помощи квадратных скобок, в Прологе предусмотрено еще одно расширение нотации для представления списка, а именно вертикальная черта, отделяющая голову от хвоста:
L = [а | Хвост]
На самом деле вертикальная черта имеет более общий смысл: мы можем перечислить любое количество элементов списка, затем поставить символ '|', а после этого — список остальных элементов. Так, только что рассмотренный пример можно представить следующими различными способами:
[а, b, с] = [а | [b, с]] = [a, b | [c]] = [a, b, c | [ ]]
Подытожим:
• Список — это структура данных, которая либо пуста, либо состоит из двух частей:
• Список рассматривается в Прологе как специальный частный случай двоичного дерева. Для повышения наглядности программ в Прологе предусматриваются специальные средства для списковой нотации, позволяющие представлять списки в виде
[ Элемент1, Элемент2, ... ]
или
[ Голова | Хвост ]
или
[ Элемент1, Элемент2, ... | Остальные]
3.2. Некоторые операции над списками
Списки можно применять для представления множеств, хотя и существует некоторое различие между этими понятиями: порядок элементов множества не существенен, в то время как для списка этот порядок имеет значение; кроме того, один н тот же объект может встретиться в списке несколько раз. Однако наиболее часто используемые операции над списками аналогичны операциям над множествами. Среди них
• проверка, является ли некоторый объект элементом списка, что соответствует проверке объекта на принадлежность множеству;
• конкатенация (сцепление) двух списков, что соответствует объединению множеств;
• добавление нового объекта в список или удаление некоторого объекта из него.
В оставшейся части раздела мы покажем программы, реализующие эти и некоторые другие операции над списками.
3.2.1. Принадлежность к списку
Мы представим отношение принадлежности как
принадлежит( X, L)
где X — объект, а L — список. Цель принадлежит( X, L) истинна, если элемент X встречается в L. Например, верно что
принадлежит( b, [а, b, с] )
и, наоборот, не верно, что
принадлежит b, [а, [b, с] ] )
но
принадлежит [b, с], [а, [b, с]] )
истинно. Составление программы для отношения принадлежности может быть основано на следующих соображениях:
(1) X есть голова L, либо
(2) X принадлежит хвосту L.
Это можно записать в виде двух предложений, первое из которых есть простой факт, а второе — правило:
принадлежит( X, [X | Хвост ] ).
принадлежит ( X, [Голова | Хвост ] ) :-
принадлежит( X, Хвост).
3.2.2. Сцепление (конкатенация)
Для сцепления списков мы определим отношение
конк( L1, L2, L3)
Здесь L1 и L2 — два списка, a L3 — список, получаемый при их сцеплении. Например,
конк( [а, b], [c, d], [a, b, c, d] )
истинно, а
конк( [а, b], [c, d], [a, b, a, c, d] )
ложно. Определение отношения конк, как и раньше, содержит два случая в зависимости от вида первого аргумента L1:
(1) Если первый аргумент пуст, тогда второй и третий аргументы представляют собой один и тот же список (назовем его L), что выражается в виде следующего прологовского факта:
конк( [], L, L ).
(2) Если первый аргумент отношения конк не пуст, то он имеет голову и хвост в
