Чтение онлайн

принадлежит( X, [X | L] ) :- !.

принадлежит( X, [Y | L] ) :- принадлежит( X, L).

Эта программа породит только одно решение. Например:

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

Х = а;

nо (нет)

5. 2. 3. Добавление элемента к списку, если он в нем отсутствует (добавление без дублирования)

Часто требуется добавлять элемент Х в список L только в том случае, когда в списке еще нет такого элемента. Если же Х уже есть в L, тогда L необходимо оставить без изменения, поскольку нам не нужны лишние дубликаты X. Отношение добавить имеет три аргумента:

добавить( X, L, L1)

где Х - элемент, который нужно добавить, L - список, в который его нужно добавить, L1 - результирующий новый список. Правила добавления можно сформулировать так:

если Х принадлежит к L, то L1 = L,

иначе L1 - это список L с добавленным к нему

элементом X.

Проще всего добавлять Х в начало списка L так, чтобы Х стал головой списка L1. Запрограммировать это можно так:

добавить( X, L, L) :- принадлежит( X, L), !.

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

Поведение этой процедуры можно проиллюстрировать следующим примером:

?- добавить( а, [b,с], L).

L = [a, b, c]

?- до6авить( X, [b, с], L).

L = [b, с]

Х = b

?- добавить( а, [b, с, X], L).

L = [b, с, а]

Х = а

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

?- добавить( a, [a, b, c], L),

L = [а, b, с]

L = [а, а, b, с]

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

5. 2. 4. Задача классификации объектов

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

победил( том, джон).

победил( энн, том).

победил( пат, джим).

Мы хотим определить

отношение класс( Игрок, Категория)

которое распределяет игроков по категориям. У нас будет три категории:

победитель– любой игрок, победивший во всех сыгранных им играх

боец– любой игрок, в некоторых играх победивший, а в некоторых проигравший

спортсмен– любой игрок, проигравший во всех сыгранных им партиях

Например, если в нашем распоряжении есть лишь приведенные выше результаты, то ясно, что Энн и Пат - победители. Том - боец и Джим - спортсмен.

Легко сформулировать правило для бойца:

Х - боец, если существует некоторый Y, такой, что Х победил

Y, и

существует некоторый Z, такой, что Z победил

X.

Теперь правило для победителя:

Х - победитель, если

X победил некоторого Y и

Х не был побежден никем.

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

Если Х победил кого-либо и Х был кем-то

побежден,

то Х - боец,

иначе, если Х победил кого-либо,

то Х - победитель,

иначе, если Х был кем-то побежден,

то Х - спортсмен.

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

класс( X, боец) :-

победил( X, _ ),

победил( _, X), !.

класс( X, победитель) :-

победил( X, _ ), !.

класс( X, спортсмен) :-

победил( _, X).

Заметьте, что использование отсечения в предложении для категории победитель не обязательно, что связано с особенностями наших трех классов.

Упражнения

5. 1. Пусть есть программа:

р( 1).

р( 2) :- !.

р( 3).

Напишите все ответы пролог-системы на следующие вопросы:

(a) ?- р( X).

(b) ?- р( X), p(Y).

(c) ?- р( X), !, p(Y).