Рассмотрим обработку списков.
Пример. Создадим предикат, позволяющий вычислить длину списка, т.е. количество элементов в списке.
Для решения этой задачи воспользуемся очевидным фактом, что в пустом списке элементов нет, а количество элементов непустого списка, представленного в виде объединения первого элемента и хвоста, равно количеству элементов хвоста, увеличенному на единицу. Запишем эту идею:
length([], 0). /* в пустом списке элементов нет */
length([_|T], L) :–
length(T, L_T), /* L_T — количество
элементов в хвосте */
L = L_T + 1. /* L — количество элементов
исходного списка */
Обратите внимание, что при переходе от всего списка к его хвосту нам неважно, чему равен первый элемент списка, поэтому мы используем анонимную переменную.
Разберем на примере, как это будет работать. Пусть нас интересует количество элементов в списке [1,2,3]. Запишем соответствующий вопрос Пролог-системе:
Система попытается вначале сопоставить нашу цель с первым предложением length([], 0), однако ей это не удается сделать, потому что первый аргумент цели является непустым списком. Система переходит ко второму предложению процедуры. Сопоставление с заголовком правила проходит успешно, переменная X связывается с переменной L, список [1,2,3] будет сопоставлен со списком [_|T], переменная T будет конкретизирована значением [2,3]. Теперь система переходит к попытке достижения подцели length(T,L_T). Как и в предыдущем случае, первое предложение с подцелью не сопоставляется, так как список T не пустой. При сопоставлении заголовка правила с подцелью хвост T конкретизируется одноэлементным списком [3]. На следующем шаге рекурсии переменная T означена пустым списком (хвост одноэлементного списка). И, значит, наша подцель выглядит следующим образом: length([], L_T). Эта цель сопоставляется с фактом, переменная L_T становится равной нулю. Раскручивается обратный ход рекурсии: переменная L_T увеличивается на единицу, результат попадает в переменную L. Получаем, что длина списка [3] равна единице. На следующем обратном шаге происходит еще одно добавление единицы, после чего длина списка [2,3] конкретизируется двойкой. И, наконец, на последнем возвратном шаге получаем означивание переменной L числом 3 (количеством элементов в списке [1,2,3]).
Пример. Создадим предикат, позволяющий проверить принадлежность элемента списку. Предикат будет иметь два аргумента: первый — искомое значение, второй — список, в котором производится поиск.
Построим данный предикат, опираясь на тот факт, что объект принадлежит списку, если он либо является первым элементом списка, либо элементом хвоста. Это может быть записано в виде двух предложений:
member(X,[X|_]). /* X — первый элемент списка */
member(X,[_|T]) :–
member(X,T). /* X принадлежит хвосту T*/
Заметим, что в первом случае (когда первый элемент списка совпадает с исходным элементом), нам неважно, какой у списка хвост, и можно в качестве хвоста указать анонимную переменную. Аналогично, во втором случае, если X принадлежит хвосту, нам не важно, какой элемент первый.
Отметим, что описанный предикат можно использовать двояко: во-первых, конечно, для того, для чего мы его и создавали, т.е. для проверки, имеется ли в списке конкретное значение. Мы можем, например, поинтересоваться, принадлежит ли двойка списку [1, 2, 3]:
Получим, естественно, ответ: "Yes".
Подобным образом можно спросить, является ли число 4 элементом списка [1, 2, 3]:
Ответом, конечно, будет "No".
Второй способ использования данного предиката — это получение по списку его элементов. Для этого нужно в качестве первого аргумента предиката указать свободную переменную. Например:
В качестве результата получим список всех элементов списка:
Третий способ позволит получить по элементу варианты списков, которые могут его содержать. Теперь свободную переменную запишем вторым аргументом предиката, а первым — конкретное значение. Например,
Вначале Пролог-система выдаст предупреждение о том, что переменная X не связана в первом предложении ("708 WARNING: The variable is not bound in this clause. (F10=ok, Esc=abort)").
У нас есть два способа отреагировать на это предупреждение: нажать кнопку Esc, чтобы отказаться от генерации списков, содержащих единицу в качестве элемента; нажать F10 для того, чтобы продолжить выполнение цели. Во втором случае Пролог-система начнет выдавать варианты списков, содержащих единицу:
X=[1|_] /* единица — первый элемент списка */
X=[_,1|_] /* единица — второй элемент списка */
X=[_,_,1|_] /* единица — третий элемент списка */
и т.д.
Этот процесс будет продолжаться до тех пор, пока не будет нажата комбинация клавиш Ctrl+Break.
Если данный предикат планируется использовать только первым способом, то можно ускорить его работу, устранив поиск элемента в хвосте списка, если он уже найден в качестве первого элемента списка. Это можно сделать двумя способами.
