Программирование на языке ПРОЛОГ для искуственного интеллекта

       

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


Часто требуется добавлять элемент Х в список 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, с]

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



Содержание раздела