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)
