2.5. Списки

Списки предоставляют удобный способ работы с информацией, состоящей из последовательностей разнородных элементов.

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

1. Список может быть представлен в виде последовательности элементов через запятую в квадратных скобках. Например:

[a, b, c, d] или [[“Л.Н. Толстой”, “Война и мир”], [“Ф.М. Достоевский”, “Преступление и наказание”]] или [] - пустой список.

2. Список может представляться в виде структуры, состоящей из «головы» и «хвоста». При этом «голова» - это первый элемент списка, а «хвост» - это список, состоящий из остальных элементов. При этом голову и хвост разделяет вертикальная черта «|»:

[ Голова | Хвост].

В списках, представленных в п. 1, головы - это, соответственно, а и [“Л.Н. Толстой”, “Война и мир”] , а хвосты - это [b, c, d] и [[“Ф.М. Достоевский”, “Преступление и наказание”]] . Список, представленный одним элементом, имеет пустой хвост. У пустого списка нет головы, и поэтому он не может быть представлен в виде головы и хвоста

3. Список может задаваться в виде «соединения»: .(Голова, Хвост). Такой список состоит из Головы, к которой приписан Хвост. Например:

.(а, [b,c,d])

или .(a.(b.(c.(d,[]))))

Рассмотрим некоторые операции над списками, часто используемые в программах на Прологе.

1. Операция «принадлежности». Это двухместный предикат, принимающий значение «истина», если первый аргумент является одним из элементов списка, представленного вторым аргументом. Этот предикат можно задать в виде следующих факта и правила:

belong(Х, [Х | Хвост]).

belong(X, [ Голова |Хвост ]) :- belong(Х, Хвост).

Здесь факт позволяет проверить, не совпадает ли первый аргумент с первым элементом списка. Если это не так, то с помощью правила первый элемент списка удаляется, второй элемент становится первым и выполняется та же проверка. Так последовательно перебираются все элементы списка и если хоть один из них совпадет с первым операндом, цель, представленная данным предикатом, будет достигнута.

2. Операция «сцепления» или «конкатенации». Это трехместный предикат, аргументы которого суть списки. Он принимает значение «истина», если третий список является сцеплением первых двух, т.е. он образован из первого списка, к которому справа приписан второй. Этот предикат также задается в виде факта и правила:

conc( [ ], С, С).

conc ( [ Х | С1], С2, [ Х | С3]) :- conc(С1, С2, С3).

Рассмотрим пример на использование данной операции. Пусть к указанным выше предложениям базы знаний приписан следующий вопрос:

? – conc( [ a, b, c], [d e], [a, b, c, d, e].

Цель: conc( [ a, b, c], [d, e], [a, b, c, d, e].

Возможна унификация с головой второго предложения.

Унификатор: { (X, a), (C1, [b, c]), (C2, [d, e]), (C3, [b, c, d, e]) }.

Цель: conc( [ b, c], [d, e], [ b, c, d, e]).

Возможна унификация с головой второго предложения.

Унификатор: { (X, b), (C1, [c]), (C2, [d, e]), (C3, [c, d, e]) }.

Цель: conc( [c], [d, e], [c, d, e]).

Возможна унификация с головой второго предложения.

Унификатор: { (X, c), (C1, [ ]), (C2, [d, e]), (C3, [d, e]) }.

Цель: conc([ ], [d, e], [d, e])

Теперь возможна унификация с первым предложением.

Унификатор: { (C, [d, e]) }.

После этого список целей оказывается пустым и, таким образом, ответ системы - «Yes».

3. Операция добавления элемента в начало списка. Представляется трехместным предикатом, первый аргумент которого - элемент, а второй и третий - списки. Предикат принимает значение «истина», если третий параметр - это список, полученный присоединением ко второму параметру первого параметра в качестве головы. Предикат задается в виде одного факта:

attach( Х, С, [ Х | С ]).

4. Операция удаления элементов из списка. Это наиболее сложная из перечисленных операций, поскольку она может выполняться в различных вариантах: удаление первого вхождения элемента из списка, удаление i-го вхождения, удаление вхождений по одному – сначала первого, потом второго и т.д., удаление всех вхождений и, наконец, все варианты удалений – по одному, по два и т.д. Вариант, который приведен ниже, выполняет удаление вхождений по одному.

delete( Х, [X | Хвост], Хвост).

delete( Х, [ Y | Хвост], [ Y | Хвост1]) :- delete( Х, Хвост, Хвост1).

Кроме приведенных операций применяются и другие, в большинстве являющиеся вариантами перечисленных.

Задайте следующие операции: добавление элемента в конец списка, варианты удаления, перечисленные в п. 4.