Пролог-автомат (pa) в поисковом движке FAIND: списки

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

[джек, джон, фред, джилл, джон]

[имя (джон, смит), возраст (джек, 24), X]

[Х.У.дата (12,январь, 1986) ,Х]

[]

Запись [ H | T ] определяет список, полученный добавлением Н в начало списка Т. Говорят, что Н - голова, а Т - хвост списка [ H I T ]. На вопрос

L=[a | [b, c, d]] ?

будет получен ответ

L=[a, b, c, d]

а на запрос

L= [a, b, c, d], L2=[2 | L]?

ответ

L=[a, b, c, d], L2- [2, a, b, c, d]

Запись [Н | Т] используется для того, чтобы определить голову и хвост списка. Так, запрос

[X | Y]=[a, b, c]?

дает

Х=а, Y=[b, c]

Заметим, что употребление имен переменных Н и Т необязательно. Кроме записи вида [H|T], для выборки термов используются переменные. Запрос

[a, X, Y]=[a, b, c]?

определит значения

X=b

Y=c

а запрос

[личность(Х) | Т]=[личность(джон), а, b]?

значения

Х=джон

Т=[а, Ь]

Покажем на примерах, как можно использовать запись вида [Н | T] вместе с рекурсией для определения некоторых полезных целевых утверждений для работы со списками.

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

Сформулируем задачу проверки принадлежности данного терма списку.

Граничное условие:

Терм R содержится в списке [H|T], если R=H.

Рекурсивное условие:

Терм R содержится в списке [H|T], если R содержится в списке Т.

Первый вариант записи определения на Прологе имеет вид:

содержится (R, L) :-
        L=[H I T],
        H=R.

содержится(Р, L) :-
        L=[H|T],
        содержится (R, T).

Цель L=[H I T] в теле обоих утверждений служит для того, чтобы разделить список L на голову и хвост.

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

принадлежит (R, [R | Т]).

принадлежит (R, [H | Т]) :- принадлежит (R, T).

На запрос

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

будет получен ответ

да

на запрос

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

- ответ

да

но на запрос

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

Пролог дает ответ

нет

В большинстве реализации Пролога предикат принадлежит является встроенным.

Соединение двух списков.

Задача присоединения списка Q к списку Р, в результате чего получается список R, формулируется следующим образом:

Граничное условие:

Присоединение списка Q к [] дает Q.

Рекурсивное условие:

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

Определение можно непосредственно написать на Прологе:

соединить([],0,0).

соединить(Р,Q,Р) :-
        Р=[НР | ТР],
        соединить(TP, Q, TR),

R=[HP | TR].

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

присоединить([] ,Q,Q).

присоединить(HP | TP], Q, [HP | TR]) :-
        присоединить (TP, Q, TR).

На запрос

присоединить [а, b, с], [d, e], L)?

будет получен ответ

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

но на запрос

присоединить([a, b], [c, d], [e, f])?

ответом будет

нет

Часто процедура присоединить используется для получения списков, находящихся слева и справа от данного элемента:

присоединить (L [джим, р], [джек,.билл, джим, тим, джим, боб] ) .

L = [джек, билл]

R = [тим, джим, боб]

L=[джек, билл, джим, тим]

R=[боб]

Индексирование списка

Задача получения N-ro терма в списке определяется следующим образом:

Граничное условие:

Первый терм в списке [Н | Т] есть Н.

Рекурсивное условие:

N-й терм в списке [Н | Т] является (N-I)-м термом в списке Т.

Данному определению соответствует программа:

получить ([H | Т], 1, Н).

получить([Н | Т], N, У) :-
        М is N - 1,
        получить (Т, М ,Y).

Построение списков из фактов

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

bagof(X,Y,L) определяет список термов L, конкретизирующих переменную Х как аргумент предиката Y, которые делают истинным предикат Y

setof(X,Y,L) все сказанное о предикате bagof относится и к setof, за исключением того, что список L отсортирован и из него удалены все повторения.

Если имеются факты:

собака(рекс).

собака (голди).

собака (фидо).

собака(реке).

то на запрос

bagof(D, co6aкa(D), L)?

будет получен ответ

L=[реке, голди, фидо, рекс]

в то время как

?-setof(D, co6aкa(D), L). дает значение

L=[фидо, голди, рекc]

 

  © Mental Computing 2010