Подсчет элементов списка

Рассмотрим, как можно определить число элементов в списке. Что такое

длина списка? Вот простое логическое определение:

Длина [] - 0.

Длина любого другого списка - 1 плюс длина его тела.

Можно ли применить это на компьютере? В Прологе - да. Для этого нуж-

но два предложения:

/* Программа CH08EX02.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] подхо-

дит к любому непустому списку, присвоением хвосту списка значения 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 вызывает сама себя рекурсивно. Это целе-

вое утверждение подходит второму предложению с присвоением

[3] в T согласно предложению

TailLength из целевого утверждения в L в предложении

Напомним, что TailLength в целевом утверждении не совпадает с

TailLength в предложении потому, что каждый рекурсивный вызов в правиле

имеет свой собственный набор переменных. Если это не ясно, почитайте раз-

дел по рекурсии в Главе 7.

Итак, целевое утверждение в том, чтобы найти длину [3], т.е. 1, а

затем добавить 1 к длине [2,3], т.е. к 2. И так далее.

Таким образом length_of вызывает сама себя рекурсивно, чтобы полу-

чить длину [3]. Хвост [3] - [] так, что T будет присвоен [], а целевое

утверждение будет в том, чтобы найти длину [] и добавив к ней 1 получить

длину [3].

На сей раз просто. Целевое утверждение

length_of([], TailLength)

удовлетворяет первому предложению, которое присвоит 0 переменной

TailLength. Компьютер добавит к нему 1 и получит длину [3], затем вернет-

ся к вызывающему предложению. Оно в свою очередь добавит 1 снова, получит

длину [2, 3] и вернется в вызывающее его предложение. Это начальное пред-

ложение снова добавит 1 и получит длину [1, 2, 3].

Не запутались? Надеемся, что нет. На самом деле так и происходит. (В

этом примере мы пользовались названиями, чтобы показать, что переменные с

одним идентификатором, но из разных предложений или из разных вызовов от-

личаются друг от друга.

/* Замечание: Далее следует пример, а не коды программы*/

length_of([1, 2, 3], L1).

length_of([2, 3], L2).

length_of([3], L3).

length_of([]), 0).

L3 = 0+1 = 1.

L2 = L3+1 = 2.

L1 = L2+1 = 3.