Списки можно применять для представления множеств, хотя и существует некоторое различие между этими понятиями: порядок элементов множества не существенен, в то время как для списка этот порядок имеет значение; кроме того, один н тот же объект может встретиться в списке несколько раз. Однако наиболее часто используемые операции над списками аналогичны операциям над множествами. Среди них
• проверка, является ли некоторый объект элементом списка, что соответствует проверке объекта на принадлежность множеству;
• конкатенация (сцепление) двух списков, что соответствует объединению множеств;
• добавление нового объекта в список или удаление некоторого объекта из него.
В оставшейся части раздела мы покажем программы, реализующие эти и некоторые другие операции над списками.
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 | Хвост ] ).
