» » »

Язык Prolog. Некоторые операции над списками.

Язык Prolog. Некоторые операции над списками

Наиболее часто используемые операции над списками аналогичны операциям над множествами.

· проверка, является ли некоторый объект элементом списка;

· конкатенация (сцепление) двух списков, что соответствует объединению множеств;

· добавление некоторого объекта в список или удаление некоторого объекта из него.

Принадлежность к списку

Мы представим отношение принадлежности как

принадлежит ( Х, L)

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

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

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

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

но

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

истинно.

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

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

2) Х принадлежит хвосту L.

Это можно записать в виде двух предложений, первое из которых есть простой факт, а второе правило:

принадлежит (Х, [Х | Хвост] ).

принадлежит (Х, [Голова | Хвост] ) :-

принадлежит (Х, Хвост).

Сцепление (конкатенация)

Для сцепления списков мы определим отношение

конк( L1, L2, L3)

Здесь L1 и L2 два списка, а L3 - список, получаемый при их сцеплении. Например,

конк( [a, b], [c, d], [a,b,c,d])

истинно, а

конк( [a, b], [c, d], [a,b, а. c,d])

ложно.

Определение отношения конк, как и раньше, содержит два случая в зависимости от вида первого аргумента L1:

1) Если первый пуст, тогда второй и третий аргумент представляют собой один и тот же список (назовем его L), что выражается в виде следующего прологовского факта:

конк ([], L, L)

2) Если первый аргумент отношения конк не пуст, то он имеет голову и хвост и выглядит так

[X | L1]

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

? - конк (L1, L2, [a, b, c] )

L1 = []

L2 =[a, b, c];

L1 = [a]

L2=[b, c];

L1=[a,b]

L2=[c];

L1=[a,b,c]

L2=[];

no

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

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

? - конк ( До, [май | После], [янв, фев, март, апр, май, июнь, июль, авг, сент, окт, ноябрь, дек]).

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

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

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

?- конк(_, [Мсяц1, май, Месяц2 | _],[янв, фев, март, апр, май, июнь, июль, авг, сент, окт, ноябрь, дек])

Месяц1 = апр

Месяц2 = июнь

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

? - L1 = [a, b, z,z, c,z, z, z, d, e],

конк (L2, [z, z, z | _ ], L1).

L1 = [a, b, z,z, c,z, z, z, d, e],

L2 = [a, b, z,z, c]

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

принадлежит1( X, L) :-

конк(L1, [X |L2], L).

В этом предложении сказано: «Х принадлежит L, если список L можно разбить на два списка таким образом, чтобы элемент Х являлся головой второго из них. Разумеется принадлежит1 определяет то же самое отношение, что и принадлежит. Мы использовали другое имя только для того, чтобы различать таким образом реализации этого отношения. Заметим, что используя анонимную переменную, можно записать вышеприведенное предложение так

принадлежит1( X, L) :-

конк(_, [X |_], L).

Добавление элемента.

Наиболее простой способ добавить элемент в список - это вставить его в самое начало так, чтобы он стал его новой головой. Если Х - это новый элемент, а список, в который Х добавляется - L, тогда результирующий список - это просто

[X | L]

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

добавить(Х , L, [X | L] ).

Удаление элемента

Удаление элемента Х из списка L можно запрограммировать в виде отношения

удалить (Х, L, L1)

где L1 совпадает со списком L, у которого удален элемент Х. отношение удалить можно определить аналогично отношению принадлежности. Имеем снова два случая:

1) Если Х является головой списка, тогда результатом удаления будет хвост списка.

2) Если Х находится в конце списка, тогда его нужно удалить оттуда.

удалить (Х, [X | Хвост], Хвост).

удалить (Х, [Y | Хвост], [Y | Хвост1]) :-

удалить (Х, Хвост, Хвост1).

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

? - удалить (a, [a, b, a, с,a], L).

L = [b, a, с,a];

L= [a, b, с,a];

L= [a, b, a,с];

no

При попытке исключить элемент, не содержащийся в списке, отношение удалить потерпит неудачу.

Отношение удалить можно использовать в обратном направлении для того, чтобы добавлять элементы в список, вставляя их в произвольные места. Например, если мы хотим во всевозможные места списка [1, 2, 3] вставить атом а, то мы можем это сделать задав вопрос: «Каким должен быть список L, чтобы после удаления из него элемента а получился список [1, 2, 3]?»

?- удалить (a, L, [1, 2, 3] ).

L=[a,1, 2, 3];

L=[1,a, 2, 3];

L=[1, 2, a,3];

L=[1, 2, 3,a];

no

Вообще операция по внесению Х в произвольное месть некоторого списка Список, дающее в результате БольшийСписок, может быть определена предложением:

внести( Х, Список, БольшийСписок):-

удалить(Х, БольшийСписок, Список).

В принадлежит1 мы изящно реализовали отношение принадлежности через конк. Для проверки на принадлежность можно также использовать и удалить. Идея простая: некоторый Х принадлежит списку Список, если Х можно из него удалить:

принадлежит2(Х, Список) :-

удалить( Х, Список, _).


Друзья! Приглашаем вас к обсуждению. Если у вас есть своё мнение, напишите нам в комментарии.