Иван Братко - Программирование на языке Пролог для искусственного интеллекта Страница 16

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

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

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

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

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

.( Голова, Хвост)

Поскольку Хвост — это список, он либо пуст, либо имеет свои собственную голову и хвост. Таким образом, выбранного способа представления списков достаточно для представления списков любой длины. Наш список представляется следующим образом:

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

На рис. 3.1 изображена соответствующая древовидная структура. Заметим, что показанный выше пример содержит пустой список []. Дело в том, что самый последний хвост является одноэлементным списком:

[ лыжи ]

Хвост этого списка пуст

[ лыжи ] = .( лыжи, [] )

Рассмотренный пример показывает, как общий принцип структуризации объектов данных можно применить к спискам любой длины. Из нашего примера также видно, что такой примитивный способ представления в случае большой глубины вложенности подэлементов в хвостовой части списка может привести к довольно запутанным выражениям. Вот почему в Прологе предусматривается более лаконичный способ изображения списков, при котором они записываются как последовательности элементов, заключенные в квадратные скобки. Программист может использовать оба способа, но представление с квадратными скобками, конечно, в большинстве случаев пользуется предпочтением. Мы, однако, всегда будем помнить, что это всего лишь косметическое улучшение и что во внутреннем представлении наши списки выглядят как деревья. При выводе же они автоматически преобразуются в более лаконичную форму представления. Так, например, возможен следующий диалог:

?- Список1 = [а, b, с],

 Список2 = (a, .(b, .(c,[]) ) ).

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

[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 ).

L = [a, b, c, 1, 2, 3]

?- конк( [а, [b, с], d], [а, [], b], L ).

L = [a, [b, c], d, а, [], b]

Хотя программа для конк выглядит довольно просто, она обладает большой гибкостью и ее можно использовать многими другими способами. Например, ее можно применять как бы в обратном направлении для разбиения заданного списка на две части:

?- конк( L1, L2, [а, b, с] ).

L1 = []

L2 = [а, b, c];

L1 = [а]

L2 = [b, с];

L1 = [а, b]

L2 = [c];

L1 = [а, b, с]

L2 = [];

no            (нет)

Список [а, b, с] разбивается на два списка четырьмя способами, и все они были обнаружены нашей программой при помощи механизма автоматического перебора.

Нашу программу можно также применить для поиска в списке комбинации элементов, отвечающей некоторому условию, задаваемому в виде шаблона или образца. Например, можно найти все месяцы, предшествующие данному, и все месяцы, следующие за ним, сформулировав такую цель:

?- конк( До, [май | После ],

 [янв, фев, март, апр, май, июнь,

  июль, авг, сент, окт, ноябрь, дек]).

До = [янв, фев, март, апр]

После = [июнь, июль, авг, сент, окт, ноябрь, дек].

Далее мы сможем найти месяц, непосредственно предшествующий маю, и месяц, непосредственно следующий за ним, задав вопрос:

?- конк( _, [Месяц1, май, Месяц2 | _ ],

 [янв, февр, март, апр, май, июнь,

  июль, авг, сент, окт, ноябрь, дек]).

Месяц1 = апр

Месяц2 = июнь

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