[a, b, c].Пустой список представляется []. Для того, чтобы определить правила для манипулирования списками, нам требуется конструкторы списка, так же как и селекторы для разделения списков на части. Мы видели эти операции в Hugs, там это оператор “:” и функции head и tail. Prolog комбинирует все эти операции в одну, при помощи унификации (похожим на применение сопоставления по образцу в Hugs). Для иллюстрации приведем программу для соединения списков. Она содержит два правила:
append([], List, List).[Помните, что мы читаем эти правила как “левая сторона верна если правая верна”]. Вызов append требует три аргумента. Естественным образом из просмотра использования этих аргументов становится понятным, что первые два аргумента представляют собой два списка, которые мы хотим объединить, а третий аргумент возвращает результат объединения. Например, если мы запускаем следующий запрос:
append([H|Tail], X, [H|NewTail]) :- append(Tail, X, NewTail).
?- append([a, b, c], [d, e], X).то мы хотим получить ответ X = [a, b, c, d, e]. Чтобы увидеть, как на самом деле работает объединение, требуется объяснить, что означает “|”. Он действует и как конструктор и как селектор для списков.
Когда мы пишем [X|Y], получается список, где голова – это X, а весь хвост (оставшаяся часть списка) – это Y. Основываясь на этой интерпретации, унификация работает так, как вы могли бы ожидать:
[X|Y] унифицируется с [a,b,c], унификатор - {X = a, Y = [b,c]}.Теперь, вспомнив информацию из предыдущего раздела,будем считать, что переменная находящаяся в голове правила считается универсальной (“квантор для любого”), в то время время как находящаяся в теле правила считается экзистенциальной(квантор “существует”). Таким образом, первое правило в определении append
[X|Y] унифицируется с [a,b,c,d], унификатор - {X = a, Y = [b,c,d]}.
[X|Y] унифицируется с [a], унификатор - {X = a, Y = []}.
[X|Y] не унифицируется с [].
append([], List, List).интуитивно можно прочитать как как “Результатом присоединения пустого списка [] к любому списку List является список List”. Обратите внимание, что это первый пример правила без тела. Вызов этого правила будет успешен до тех пор, пока первый аргумент унифицируется с [], а последние два аргумента унифицируются друг с другом.
Запрос
|
Унификатор
|
Ответ Пролога
|
?-append([],[ b,c,d], [b,c,d]).
|
{List = [b,c,d]}
|
yes
|
?- append([],[b,c,d],X).
|
{List = [b,c,d],
X = [b,c,d]} |
X = [b,c,d]
|
?- append(X,Y,Z).
|
{X = [],
Y = List, Z = List} |
X = [], Y = Z
|
?- append([],[b,c],[b,c,d]).
|
None
|
no
|
Второй вызов в приведенной выше таблице является обычным вызовом append, который зачастую будет использоваться, с заданными первыми двумя аргументами, а также третий аргументом в виде переменной, в которой будет храниться ответ.
Теперь рассмотрим второе правило, которая является общим случаем присоединения непустого списка к другому списку.
append([H|Tail], List, [H|NewTail]) :- append(Tail, List, NewTail).
Все переменные которые есть в этом правиле являются универсальными, потому что каждая из них есть в голове правила. Если мы вызовем append запросом:
?- append([a,b,c], [d,e], Result).
Атом в запросе не унифицируется с первым правилом потому что список [a, b, c] и [] не совпадают. Запрос, однако, унифицируется с головой второго правила. Согласно унификации, итоговым унификатором будет
{ H = a, Tail = [b,c], List = [d,e], Result = [a|NewTail] }
Эта подстановка применяется к телу правила, генерируя новый запрос:
?- append([b,c], [d,e], NewTail).
Продолжение следует…
Комментариев нет:
Отправить комментарий