Clauses

%искомый элемент совпадает с головой списка

 find(Elem, [Elem|_]).

%иначе ищем элемент в хвосте списка

‚ find(Elem, [_|Tail]):-find(Elem, Tail).

 

?- find(“3”, [“1”’, “3”, “4”])

Yes

При задании целевого утверждения Пролог попытается вначале применить первое правило. Если искомый элемент не совпадает с первым элементом списка (головой списка), то делается откат и Пролог пытается для доказательства целевого утверждения применить второе правило. Пролог унифицирует имеющиеся термы с заголовком второго правила
find(Elem, [_|Tail]). При этом первый элемент списка ставится в соответствие анонимной переменной. Так делается потому, что значение первого элемента списка не представляет для нас интереса (второе правило не было бы задействовано, если бы первый элемент списка совпадал с объектом поиска – первое правило). Теперь мы хотим присвоить переменной Tail хвост списка, чтобы Пролог попытался установить соответствие между объектом поиска и головой хвоста списка. Попытка согласовать подцель find(Elem, Tail) заставляет Пролог представить хвост текущего списка как новый самостоятельный список. Этот процесс повторяется до тех пор, пока либо выполнится первое правило (успешное завершение программы), либо пока не исчерпается весь список (неуспешное завершение программы). Так при выполнении целевого утверждения find(“3”, [“1”, “3”, “4”]) получим следующую последовательность рекурсивных вызовов:

?- find(“3”, [“1”, “3”, “4”])

 не подходит, так как искомый элемент не

совпадает с головой списка

‚ Elem=3, Tail=[“3”, “4”]

?- find(“3”, [“3”, “4”])

 Elem=“3” совпадает с головой списка

ответ Yes

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

Например, в результате выполнения целевого утверждения

?- find(X, [“1”, “3”, “4”])

получим следующие значения переменной X:

X = “1”

X = “3”

X = “4”