и констатирует, что X является элементом списка, если X является элементом хвоста этого списка. Заметим, что мы использовали анонимную переменную '_', так как нас не интересует имя переменной, обозначающей голову списка. Два этих правила в совокупности определяют предикат для отношения принадлежности и указывают Прологу, каким образом просматривать список от начала до конца при поиске некоторого элемента в списке. Наиболее важный момент, о котором следует помнить, встретившись с рекурсивно определенным предикатом, заключается в том, что прежде всего надо найти граничные условия и способ использования рекурсии.
Для предиката принадлежит в действительности имеются два типа граничных условий. Либо объект, который мы ищем, содержится в списке, либо он не содержится в нем. Первое граничное условие для предиката принадлежит распознается первым утверждением, которое приведет к прекращению поиска в списке, если первый аргумент предиката принадлежит совпадает с головой списка, соответствующего второму аргументу. Второе граничное условие встречается, когда второй аргумент предиката принадлежит является пустым списком.
Как мы можем убедиться в том, что граничные условия будут когда-либо удовлетворены? Для этого необходимо обратить внимание на то, как используется рекурсия во втором правиле для предиката принадлежит. Заметим, что каждый раз, когда при поиске соответствия для целевого предиката принадлежит происходит рекурсивное обращение к тому же предикату, новая цель формируется для более короткого списка. Хвост списка всегда является более коротким списком, чем исходный список. Очевидно, что рано или поздно произойдет одно из двух событий: либо произойдет сопоставление с первым правилом для принадлежит, либо в качестве второго аргумента принадлежит будет задан список длины 0, т. е. пустой список. Как только возникнет одна из этих ситуаций, прекратится рекуррентное порождение целей для предиката принадлежит. Первое граничное условие распознается фактом, который не вызывает порождения новых подцелей. Второе граничное условие не распознается ни одним из утверждений для принадлежит, так что процесс поиска сопоставимого элемента списка для целевого утверждения принадлежит закончится неудачей. Это демонстрирует следующий пример на Прологе:
принадлежит(Х, [X | _]).
принадлежит(Х,[_|Y]):- принадлежит (X,Y).
?- принадлежит(d,[a,b,с,d,e,f,g]).
да
?- принадлежит(2,[3,a,4,f]).
нет
Предположим, мы введем вопрос
