Алгоритму этого типа обычно нужны два предложения. Первое из них говорит, что делать с обычным списком (списком, который можно разделить на голову и хвост), второе — что делать с пустым списком.
Если нужно напечатать элементы списка, это делается так, как показано в листинге 1.
Листинг 1. Программа ch07e01.pro;
domains
list = integer*% Или любой тип, какой вы хотите
predicates
write_a_list(list)
clauses
write_a_list([ ]),% Если список пустой — ничего не делать
write_a_list([Н|Т]):-% Присвоить Н-голова,Т-хвост, затем...
write(H),nl,
write_a_list(Т).
goal
write_a_list([1, 2, 3]).
Вот два целевых утверждения write_a_list, описанные на обычном языке:
Печатать пустой список — значит ничего не делать.
Иначе, печатать список — означает печатать его голову (которая является одним элементом), затем печатать его хвост (список) .
Рассмотрим, как можно определить число элементов в списке. Что такое длина списка? Вот простое логическое определение:
Длина [] — 0.
Длина любого другого списка — 1 плюс длина его хвоста.
Можно ли применить это? В Прологе — да. Для этого нужны два предложения (листинг 2).
Листинг 2. Программаch07e02.pro
domains
list = integer*
predicates
length_of(list,integer)
clauses
length_of ( [ ] , 0).
length_of ( [ _|T],L) :-
length_of(T,TailLength),
L = TailLength + 1.
Посмотрим сначала на второе предложение. Действительно, [_|T] можно сопоставить любому непустому списку, с присвоением т хвоста списка. Значение головы не важно, главное, что оно есть, и компьютер может посчитать его за один элемент.
Таким образом, целевое утверждение
length_of([1, 2, 3], L).
подходит второму предложению при T=[2, 3]. Следующим шагом будет подсчет длины T. Когда это будет сделано (не важно как), TailLength будет иметь значение 2, и компьютер добавит к нему 1 и затем присвоит L значение 3.
Итак, как компьютер выполнит промежуточный шаг? Это шаг, в котором определяется длина [2, 3] при выполнении целевого утверждения
length_of([2, 3], TailLength).
Другими словами, length_of вызывает сама себя рекурсивно.
[1] Имеются и другие стандартные домены.