Clauses. Length_of([_|T], L) :- length_of(T, TailLength)

length_of([], 0).

length_of([_|T], L) :- length_of(T, TailLength),

L = TailLength + 1.

Поглянемо спочатку на другу фразу. Так, length_of [_ ,|T] порівнює любий непустий список, прив`язуючи Tдо хвосту списка. Значення голови не суттєво, ЕОМ буде її рахувати як один елемент.

Так ціль

goal: length_of([1,2,3], L) ,

використовуючи другу фразу, зв'яже з T значення [2,3]. Наступний крок - обчислити довжину T. Коли це зроблено, не важливо як, тоді TailLength отримає значення 2, і ЭВМ потім зможе добавити до неї 1 та прив'язатиL до 3.

Для того, щоб визначити довжину [2,3] рекурсивно викличеться length_of([2,3], TailLength. Ця ціль зрівнює другу фразу, прив'язуючи - [3] до T . Тепер виникає задача, як знайти довжину [3], яка дорівнює 1, а потім добавить1, щоб отримати довжину [2,3], яка буде 2. І так далі і тому подібно. Тому length_of знов викличе себе рекурсивно, щоб отримати довжину списку [3]. Хвіст для [3] рівний [ ], тому T зв'яжеться з [], і задача зараз полягає в тому , щоб знайти довжину [], потім додати до неї 1, і знайти довжину [3]. На цей раз це зробити легко. Ціль length_of([], Tail Length зрівнюючи першу фразу, зв'яже TailLengthз 0. Тепер ЭОМ може додати 1до неї, отримуючи довжину списку [3] і повернутися до фрази виклику. Яка , в свою чергу , прибавить знову 1 , отримуючи довжину [2,3] і повернеться до фрази, яка викликала її; ця початкова фраза прибавить знову 1 , знаходячи довжину списку [1,2,3].

Малюнок 8.1 показує дійсний процес обчислення довжини списку. Ми використали тут різні змінні, щоб підкреслити той факт, що змінні з одинаковими іменами в різних фразах , або різних викликах однієї і тієї ж фрази, будуть різними.

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

Мал.8.1.Обчислення довжини списку.

8.2.3.Іще один варіант підрахунку довжини списку.

Як ви бачите, предикат length_of не є хвостовою рекурсією. Чи можливо створити рекурсивно-хвостовий предикат визначення довжини списку? Можливо, але для цього потрібно прикласти певні зусилля.

Проблема з length_ of заключається в тому, що ми не можемо обчислити довжину списку, пока не підрахуємо довжину хвоста. Та все ж така можливість мається. Використаємо предикат з трьома аргументами.

- Перший є список, котрий ЕОМ буде читати при кожному виклику, поки він не стане пустим.

- Другий є вільним аргументом, який в кінці роботи буде визначати результат.

- Третій є лічильником, котрий починається з 0 і збільшується з кожним викликом. В кінці лічильник можна уніфікувати з незв'язаним результатом.

Наступна програма реалізує наш підхід.

Domains

list = integer*

Predicates

Length_of(list, integer, integer)