ПОИСК ЭЛЕМЕНТА В СПИСКЕ

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

member(3, [1,2,3,4,5])

Первый из объектов утверждения, 3, есть объект поиска. Второй — это список [1,2,3,4,5].

Для выделения элемента из списка и сравнения его с объектом поиска можно применить метод разделения списка на голову и хвост. Стратегия поиска при этом будет состоять в рекурсивном выделении головы списка и сравнении ее с элементом поиска.

Так же, как в программе «Голова-хвост», при рекурсии хвостом каждый раз становится новый список, голова которого присваивается переменной, сравниваемой с объектом поиска.

member(Head,[Head|_])

Этот вариант правила соответствует случаю, когда объект поиска совпадает с головой списка. Отметим, что хвост списка при этом присваивается анонимной переменной. Если объект поиска и голова списка действительно соответствуют друг другу, то результатом сравнения явится успех.

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

member(Head, [_,Tail]) :-

member(Head, Tail).

При этом уже проверенный первый элемент списка ставится в соответствие анонимной переменной. Попытка удовлетворить рекурсивное правило member(Head,Tail) заставляет Турбо-Пролог представить хвост текущего, как новый самостоятельный список.

Процесс повторяется до тех пор, пока это утверждение дает либо успех в случае установления соответствия на очередной рекурсии, либо неуспех в случае исчерпания списка.

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

/* Программа 6.3 «Элементы». Назначение: */

/* поиск нужного элемента в списке. */

domains

number_list = integer *

person_list = symbol *

predicates

member(number, number_list)

member(person, person_list)

goal

member(3,[1,2,3,4,5]), write(” нашли 3 ”),

member(john, [tom, bob, jerry, john],

write(” нашли Джона ”).

clauses

member(Head, [Head|_]).

member(Head, [_|Tail]) :-

member(Head, Tail).

/* Конец программы */

На экране появится True и печать двух сообщений.

Упражнение 6.2.

Задайте следующую внешнюю цель:

member(44,[11,44,11,33,44,44,55])

В скольких случаях будет достигнут успех?