Prolog

        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)

где Х - объект, а L - список. Цель принадлежит( X, L) истинна, если элемент Х встречается в L. Например, верно что

        принадлежит( b, [а, b, с] )

и, наоборот, не верно, что

        принадлежит b, [а, [b, с] ] )

но

        принадлежит [b, с], [а, [b, с]] )

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

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

    (2)        Х принадлежит хвосту 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)        Если первый аргумент отношения конк не пуст, то он имеет голову и хвост в выглядит так:

        [X | L1]

На рис. 3.2 показано, как производится сцепление списка [X | L1] с произвольным списком L2. Результат сцепления - список [X | L3], где L3 получен после сцепления списков L1 и L2. На прологе это можно записать следующим образом:

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

              конк( L1, L2, L3).

Рис. 3. 2.  Конкатенация списков.

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

        ?- конк( [a, b, с], [1, 2, 3], L ).