Декларативное программирование

[ Содержание | 1 | 2 | 3 | 4 | 5 | 5.1 | 5.2 | 5.3 | 5.4 | 5.5 | 5.6 | 5.7 | 5.8 | 5.9 | 6 | 6.1 | 6.2 | 6.3 | 6.4 | 6.5 | 7 | 7.1 | Литература ]

© 2003 И.А. Дехтяренко

6.2. Особенности логических программ.

Многие функциональные программы нетрудно преобразовать в реляционные. Достаточно перейти от функций к отношениям и при необходимости ввести дополнительные переменные для представления промежуточных результатов. Логические программы подобно функциональными могут вызывать итерационные, линейно-рекурсивные и древесно-рекурсивные процессы¹. Сравните процедуры на двух языках.

sqr(X,Y) :- Y is X*X.

sqr(X)-> X*X.

sign(0,0).
sign(X,1) :- X > 0.
sign(X,-1):- X < 0.

sign(0)  -> 0;
sign(X) when X > 0 -> 1;
sign(X) when X < 0 -> -1

fac(1,1).
fac(N,F) :- 
    N > 1, M is N - 1, 
    fac(M,F1), F is N*F1.

fac(1) -> 1;
fac(N) when N > 1 -> 
    N * fac(N-1).

member(X, [X|_]). 
member(X, [_|T]) :- member(X,T).

member(X, [X|_]) -> true;
member(X, [_|T]) -> member(X,T);
member(X, []) -> false;

length([],0).
length([_|T],N) :- 
    length(T,M), N is M+1.

length([])-> 0;
length([H|T])-> 
    1 + length(T).

append([], L, L).
append([H|T], L, [H|R]) :- 
    append(T, L, R).

append([], L) -> L.
append([H|T], L) -> 
    [H|append(T, L)].

reverse([], []).
reverse([H|T],L) :- 
    reverse(T,S), append(S,[H],L).

reverse([])->[].
reverse([H|T]) -> 
    append(reverse(T),[H]).

reverse(L,R):-  
    reverse_a(L,[],R).

reverse_a([],L,L).
reverse_a([H|T],L,R):- 
    reverse_a(T,[H|L],R).

reverse(L)->  
    reverse_a(L,[]).

reverse_a([],L)-> L;
reverse_a([H|T],L) -> 
    reverse_a(T,[H|L]).

Выполняются логические процедуры почти так же, как их функциональные прототипы.

?- sqr(2,X).
X = 4
yes

?- fac(2,X).
X = 2 
yes

?- append([1,2],[3,4],X).
X = [1,2,3,4]
yes

member(b, [a,b,c]). 
yes

length([a,b,c],N).
N = 3
yes

Обратимость и недетерминизм.

И все же логические программы обладают своими особыми свойствами. Функциональная процедура действует подобно математической функции: получает аргумент (или набор аргументов) и возвращает для него строго единственный результат. Логическая процедура соответствует математическому понятию отношения и обладает большей гибкостью.

1. Определение отношения ничего не говорит о том, какие аргументы исходные, а какие результаты - в разных запросах одни и те же аргументы могут играть различные роли.
2. Логическая процедура может выдавать любое количество ответов на запрос: нуль (нет ответов), один или больше.

Эта гибкость делает логическое программирование хорошо подходящим для некоторых классов задач, в частности для баз данных. Например, отношение boss можно использовать с разными целями:

1. Проверить конкретное утверждение boss(diana, barbara).
2. Найти начальника boss(diana, B).
3. Найти подчиненного boss(A,diana).
4. Найти все пары начальник-подчиненный boss(A, B).

Предположим что мы захотели описать базу данных на функциональном языке. Естественно было бы определить функцию boss.

boss(barbara) -> anthony.
boss(charles) -> anthony.
и т.д.

Имея эту функцию, нетрудно решить две первые задачи boss(barbara) = anthony или X = boss(barbara), но для двух оставшихся нам потребуются дополнительные средства². Еще одна проблема - вызов boss(anthony). Как поступать если для данного аргумента  результат не определен?  Обычно в таких в случаях возвращают специальное значение, свидетельствующее о выходе аргумента из области определения функции. При использовании отношений в этом нет необходимости - отношение может выполняться, а может не выполняться.

Конечно, базы данных не единственная и даже не основная область применения Пролога. Предикаты для работы со списками демонстрируют ту же гибкость. Например, предикат member можно использовать не только для проверки того, что данный объект входит в список, но и для того чтобы получить все элементы списка.

?- member(X,[a,b,c]).
X = a ;
X = b ;
X = c ;
No

Предикат append можно использовать не только для слияния, но и для разбиения списков.

?- append(X,[3,4],[1,2,3,4]).
X = [1,2] ? 
yes

?- append([1,2],X,[1,2,3,4]).
X = [3,4]
yes

?- append(X,Y,[1,2,3]).
X = []
Y = [1,2,3] ;
X = [1]
Y = [2,3] ;
X = [1,2]
Y = [3] ;
X = [1,2,3]
Y = [] ;
No

Это свойство обратимости дает нам возможность легко и изящно формулировать определения новых отношений на списках.

last(X,Y) :- append(_,[X],Y).
butlast(X,Y) :- append(X,[_],Y).
prefix(X,Y) :- append(X,_,Y).
suffix(X,Y) :- append(_,X,Y).
sublist(X,Y) :- prefix(Z,Y), suffix(X,Z).

Можно даже определить member через append.

member(X,L):- append(_,[X|_],L).

Эти определения менее эффективны (хотя и не настолько, как может показаться на первый взгляд) и имеет смысл записать для них рекурсивные процедуры. Но предположим, нам понадобилось проверить, что X и Y расположены в списке L по соседству. Вряд ли эта операция встретится еще и нерационально придумывать для нее специальную процедуру. Мы просто запишем append(_,[X,Y|_],L).

Упражнение.

Напишите прямые рекурсивные определения предикатов last, butlast, prefix и suffix.

Упражнение.

Найдите недостаток процедуры sublist и устраните его.

Немного изменив определение member, получим предикат select, который проверяет, что данный элемент входит в список и возвращает оставшуюся часть списка.

select(X, [X|L], L). 
select(X, [Y|L], [Y|R]) :- select(X, L, R).

Обратите внимание, что удаляется только одно вхождение X.

?- select(1,[1,2,1,3],R).

R = [2, 1, 3] ;
R = [1, 2, 3] ;
No

Теперь уже не покажется удивительным, что select можно использовать для извлечения элементов из списка.

?- select(X,[1,2,3],R).
X = 1
R = [2, 3] ;
X = 2
R = [1, 3] ;
X = 3
R = [1, 2] ;
No

Но его же можно использовать и для вставки элемента в список.

?- select(x, L, [1,2,3]).
L = [x, 1, 2, 3] ;
L = [1, x, 2, 3] ;
L = [1, 2, x, 3] ;
L = [1, 2, 3, x] ;
No

Интересно сравнить два варианта процедуры генерации перестановок.

permutation([],[]).
permutation(L,[X|T]):- select(X,L,R), permutation(R,T).

permutation2([],[]). 
permutation2([X|T],R):- permutation2(T,L), select(X,L,R).

В первой из них select извлекает различные элементы из списка, а во второй вставляет элемент в разные позиции списка. Оба варианта выдадут все перестановки, но в разном порядке.

?- permutation([1,2,3], L).

L = [1, 2, 3] ;
L = [1, 3, 2] ;
L = [2, 1, 3] ;
L = [2, 3, 1] ;
L = [3, 1, 2] ;
L = [3, 2, 1] ;
No

?- permutation2([1,2,3], L).
L = [1, 2, 3] ;
L = [2, 1, 3] ;
L = [2, 3, 1] ;
L = [1, 3, 2] ;
L = [3, 1, 2] ;
L = [3, 2, 1] ;
No

Упражнение.

Сравните поведение двух процедур, выражающих отношение подмножество.

members([],_).
members([X|Xs], Ys) :- member(X, Ys), members(Xs, Ys ).

selects([],_).
selects([X|Xs], Ys) :- select(X,Ys,Zs), selects(Xs,Zs).

Воодушевленные этими примерами, попробуем найти квадратный корень, используя sqr.

?- sqr(X,4).
ERROR: Arguments are not sufficiently instantiated
^  Exception: (8) 4 is _G160*_G160 

Но нас ждет разочарование. Пролог не умеет решать уравнения. Предикат is, а с ним и sqr, работает только в одну сторону. Можно сказать, что арифметические вычисления выполняются в функциональном стиле.

В SWI-Prolog есть и "разнонаправленные" арифметические предикаты succ и plus, определенные для целых чисел и более соответствующие реляционному духу Пролога. Предикат succ выдает следующее или предыдущее число, а plus складывает или вычитает числа.

?- succ(1,X).
X = 2 
Yes

?- succ(X,2).
X = 1 
Yes

?- plus(2,3,X).
X = 5 
Yes

?- plus(2,X,5).
X = 5 
Yes

Можно придать двунаправленность и отношению sqr. Для этого надо явно разделить различные случаи вызова этой процедуры.

sqr(X,Y) :- nonvar(X)-> Y is X*X ; X is sqrt(Y).

Но в таком виде процедура не совсем соответствует подразумеваемому смыслу отношения sqr. Действительно, мы исходим из того, что sqr(X,Y) означает X² = Y. Тогда, например, запрос sqr(X,4) должен вернуть такое X, что X² = 4. Но это уравнение имеет два решения, а наша процедура вернет только одно. Далее, запрос sqr(X,-4) завершится ошибкой, в то время как разумно было бы ожидать ответа "нет". Нетрудно придать предикату sqr "более логические" свойства, например так.

sqr(X,Y) :- nonvar(X), Y is X*X .
sqr(X,Y) :- var(X), Y >= 0, X is sqrt(Y).
sqr(X,Y) :- var(X), Y >= 0, X is -sqrt(Y).

Хотя этот предикат и не очень полезен, ему можно найти забавное применение.

root_sqr_eq(A,B,C,X):- 
  D is B*B-4*A*C,
  sqr(S,D),
  X is (-B+S)/(2*A).

Эта процедура ищет корни квадратного уравнения знакомым всем методом. Обратите внимание как предикат sqr управляет поведением root_sqr_eq.

Упражнение.

Какой ответ последует на запрос sqr(X,0)?

Упражнение.

Попробуйте с помощью условных операторов или отсечений избавиться от некоторой степени избыточности, присущей данной процедуре.

Заметим, что мы не пытались обрабатывать случай, когда оба параметра окажутся свободными переменными. Не возвращать же, в самом деле, все возможные пары чисел! И все же, толика здравого смысла в этом есть. Если множество решений конечно, мы можем захотеть получить их все или хотя бы часть. Рассмотрим простейший случай - множество целых чисел на отрезке [L..R] и запишем процедуру  between, возвращающую такие числа. Ее определение совсем несложно.

between(L,R,L):- L =< R.
between(L,R,N):- L < R, succ(L,L1), between(L1,R,N).

Первое правило говорит, что нижняя граница отрезка будет ответом (при условии, что она не превосходит верхней), а второе что ответами будут и все числа от L+1 до R.

Упражнение.

Используя between, можно проверить, входит ли число в заданный диапазон. Но это приведет к перебору всех чисел из этого диапазона. Результат будет верным, но мы то знаем, что получить его можно гораздо быстрее. Дополните определение, чтобы избежать неэффективности. (Это уже сделано во встроенном предикате between).

С помощью between можно организовывать циклы, придавая им декларативный вид, например.

?- between(1,5,A), between(1,A,B), A + B =:= 5.

X = 1
Y = 4 ;

X = 2
Y = 3 ;

No

С операционной точки зрения это определение предписывает выполнение двух вложенных циклов, но его можно рассматривать и чисто логически - как описание условий, которым должны удовлетворять A и B и C. Это простейший пример метода  "образовать и проверить", характерного для Пролога. Схематичеки его можно описать как.

find(X) :- generate(X), test(X).

Предикат generate перечисляет некоторое множество, среди элементов которого мы ищем решения, а test проверяет, является ли предполагаемое решение приемлемым. В качестве генератора часто используют предикаты between, member или запросы к базам данных. Иногда один и тот же предикат может выступать и генератором и проверкой.

member_both(X,L1,L2) :- member(X,L1), member(X,L2).

Генератор может возвращать и бесконечное множество значений.

natural(1).
natural(N):- natural(M),succ(M,N).

Эта предикат будет последовательно возвращать натуральные числа, начиная с 1. Конечно, при использовании бесконечных множеств следует заранее убедиться, что решение существует, иначе программа зациклится.

Предикат natural интересен с теоретической точки зрения, как индуктивное определение множества натуральных чисел. Аналогичные предикаты можно записать и для других множеств, например для списков или для двоичных деревьев.

list([]).
list([H|T]) :- list(T).

binary_tree(empty).
binary_tree(bt(X,L,R)) :- binary_tree(L), binary_tree(R).

Такого рода предикаты часто называют типовыми потому что они описывают множества, которые мы склонны трактовать как типы данных³.

?- list(X).

X = [] ;

X = [_G214] ;

X = [_G214, _G217] ;

X = [_G214, _G217, _G220] 

Yes

?- list([1,2,3]).

Yes 

Упражнение.

Что будет, если попытаться проверить с помощью natural является ли данный терм натуральным числом?

Можно было бы избежать многих проблем, если выбрать другое представление для чисел, например представлять натуральные числа термами 1,1+1,1+1+1, и т.д. Но, конечно, такое представление годится разве что для упражнений.

Упражнение.

Рассмотрим множество термов, определяемых предикатом peano_number.
peano_number(1).
peano_number(N+1):- peano_number(N).
Определите для него операции сложения и умножения. Убедитесь в их обратимости.

Гибкость логических программ имеет обратную сторону. Она может легко привести к неэффективным программам. Грубо говоря, можно выделить два источника неэффективности: избыточный недерменизм и злоупотребление перебором.

Пролог не различает детерминированный и недетерминированный выбор. Рассмотрим процедуру разбиения списка.

partition([],C,[],[]).
partition([X|L],C,[X|L1],L2) :- X =< C, partition(L,C,L1,L2).
partition([X|L],C,L1,[X|L2]) :- X > C, partition(L,C,L1,L2).

Два последних правила являются взаимоисключающими, но большинство реализаций Пролога не в состоянии это определить. При каждом вызове процедуры создается точка выбора и, как следсвие, потенциально итерационный процесс превращается в линейно-рекурсивный. Обычно в таких случаях вводят в программу элементы управления.

partition([],C,[],[]).
partition([X|L],C,[X|L1],L2) :- X =< C,!, partition(L,C,L1,L2).
partition([X|L],C,L1,[X|L2]) :- X > C, partition(L,C,L1,L2).

Отсечение устраняет точку выбора и процедура становится итерационной. Можно еще немного сэкономить и удалить ставшее неужным сравнение.

partition([],C,[],[]).
partition([X|L],C,[X|L1],L2) :- X =< C,!, partition(L,C,L1,L2).
partition([X|L],C,L1,[X|L2]) :- partition(L,C,L1,L2).

Правда, теперь процедура несколько потеряла в логической ясности.

Другой источник неэффективности содержится не в самом языке, а скорее в практике его применения. Многие задачи допускают простые решения "в лоб" методом перебора. Эти решения легко программируются на Прологе, что стимулирует их использование. Но полученные программы часто очень неэффективны. И все же такое "неалгоритмическое программирование" иногда оказывается практически оправданным. Поскольку решение задачи не требует разработки алгоритмов, программу можно написать очень быстро. Далее, если объем данных невелик или область поиска мала, даже неэффективное решение может оказаться вполне приемлемым. К тому же эксперименты на небольших примерах часто помогают лучше понять проблему  и спроектировать эффективный алгоритм.

Как писать программы на Прологе.

Как правило программы пишутся исходя из процедурной семантики Пролога, а затем слегка приукрашиваются с целью придать им декларативный смысл. Это вполне оправданная методика и она оказывается особенно удачной в случае если задача хорошо знакома и известен алгоритм ее решения. Но для очень сложных программ более практическим оказывается противоположный подход.

Сначала программа записывается как набор чисто логических утверждений. Она может быть очень неэффективной или даже не завершаться, но она обязана быть логически правильной. Затем в программу включаются алгоритмические знания. Программа (или часть программы) переписывается с учетом процедурной семантики. Часто модификация программы состоит в переупорядочивании последовательности правил или целей в правилах. Иногда полезным оказывается изменение представления данных. В то же время следует заботиться о том, чтобы не нарушить логическую семантику. Наконец, при необходимости добавляются элементы управления и другие внелогические операции. Полностью сохранить логическую семантику при этом удается далеко не всегда, но по крайней мере надо постараться это сделать.

Достоинства этого способа в том, что обычно намного проще понять задачу, рассматривая только ее логику, а попытка одновременно учитывать порядок выполнения операций только запутывает.

Логические переменные.

Переменные в Прологе обладают некоторым сходством с переменными функциональных и императивных языков. Логические переменные подобно функциональным получают значения только однажды⁴, но в отличие от них эти значения не обязательно должны быть определены перед использованием переменных. Эта разница становится интересной когда переменные входят в структуры данных.

?- L = [A,A,B,B].

L = [_G160, _G160, _G166, _G166]
A = _G160
B = _G166 

Yes

?- L = [A,A,B,B],A = a.

L = [a, a, _G166, _G166]
A = a
B = _G166 

Yes

?- L = [A,A,B,B], A = a, member(b,L).

L = [a, a, b, b]
A = a
B = b 

Yes

Видно как значение L "уточняется" по мере выполнения запроса.

Рассмотрим известную задачу о раскраске карты. Имеется географическая карта и набор цветов. Надо раскрасить карту так, чтобы соседние страны были раскрашены в разные цвета.

Простейшее, хотя и не самое эффективное, решение основано на переборе с возвратами. Для каждой страны выбирается цвет, а затем выбираются (или проверяются) цвета для ее соседей. Будем представлять карту списком пар (страна - список соседей). Например, карта

описывается списком

[ M-[A,B,D,E,F], A-[B,C,D,M], B-[A,C,E,M], C-[A,B,D,E,F], D-[A,C,F,M], E-[B,C,F,M], F-[C,D,E,M]].

С таким представлением программа становится почти тривиальной - значительную часть работы выполняет механизм унификации.

paint_map([Сountry-Neighbours|RestOfMap],Palette) :- 
    select(Сountry, Palette, Palette1),
    members(Neighbours, Palette1),
    paint_map(RestOfMap, Palette).
paint_map([],_).

На самом деле нет необходимости дважды указывать каждое соседство и описание карты можно сократить до

[M-[A,B,D,E,F], A-[B,C,D], B-[C,E], C-[D,E,F], D-[F], E-[F]].

Как известно, для раскрашивания любой плоской карты достаточно четырех цветов. Первый ответ

?- paint_map([M-[A,B,D,E,F], A-[B,C,D], B-[C,E], C-[D,E,F], D-[F], E-[F]],
|    [blue, red, green, yellow]).

M = blue
A = red
B = green
D = green
E = red
F = yellow
C = blue 

Yes

дает такую раскраску.

Один интересный трюк изобретенный Пролог-программистами для повышения эффективности программ - неполные структуры данных. Например, неполный список отличается от обычного тем, что завершается не пустым списком, а свободной переменной. Такой список возвращается предикатом member при запросах вида

?- member(1,L).
L = [1|_G208] 
Yes

?- member(1,L), member(2,L).

L = [1, 2|_G226] 
Yes

Неполные списки часто используются для организации небольших словарей. Доступ к словарю осуществляется процедурой lookup, которая возвращает значение соответствующее ключу или добавляет пару ключ-значение в словарь. Простейшее определение этой процедуры

lookup(Key,Dict,Val):- member(Key-Val,Dict).

Например

?- lookup(a,Dict,1),lookup(b,Dict,2),lookup(a,Dict,A).

Dict = [a-1, b-2|_G268]
A = 1 

Yes

Упражнение.

Запишите рекурсивное определение lookup не использующее member.
Эта процедура обладает существенным недостатком: вызов
lookup(a,Dict,1), lookup(a,Dict,2)
приведет к добавлению в словарь второго значения для a.
Исправьте определение ее так, чтобы подобные запросы завершались неудачей.

Примером применения словаря может послужить игрушечный калькулятор, допускающий однократные присваивания переменным.

eval(X+Y,Z,D):- eval(X,X1,D), eval(Y,Y1,D), Z is X1+Y1.
eval(X-Y,Z,D):- eval(X,X1,D), eval(Y,Y1,D), Z is X1-Y1.
eval(X*Y,Z,D):- eval(X,X1,D), eval(Y,Y1,D), Z is X1*Y1.
eval(X/Y,Z,D):- eval(X,X1,D), eval(Y,Y1,D), Z is X1/Y1.
eval(X;Y,Z,D):- eval(X,X1,D), eval(Y,Z,D).
eval(X=Y,Z,D):- atom(X), eval(Y,Z,D), lookup(X,D,Z).
eval(X,X,_) :- integer(X).
eval(X,Z,D) :- atom(X), lookup(X,D,Z).

?- eval(a=3+2; b=5; a/b, Val,_).
Val = 1 
Yes

?- eval(a=3+2; a=5; a*a, Val,_).
Val = 25 
Yes

?- eval(a=3+2; a=4; a*a, Val,_).
No

Упражнение.

Для больших словарей поиск в списке может оказаться медленным.
Напишите процедуру, аналогичную lookup но использующую неполное бинарное дерево.

К неполному списку можно очень быстро присоединить другой список, присваивая его переменной, завершающей неполный список. Правда, сделать это можно только один раз.

?- X=[1,2,3|A],A=[4,5,6].

X = [1, 2, 3, 4, 5, 6]
A = [4, 5, 6] 
Yes

Но если присоединяемый список тоже неполный, можно присоединить к нему еще один список и т.д.

?- A=[1,2,3|B], B=[4,5,6|C], C=[7,8,9].

A = [1, 2, 3, 4, 5, 6, 7, 8, 9]
B = [4, 5, 6, 7, 8, 9]
C = [7, 8, 9] 
Yes

Мы можем оформить эту идею, определив отношение

append_incomplete(A,B,B,C,A,C).

?- append_incomplete([1,2,3|A],A,[4,5,6|B],B,C,[]).

A = [4, 5, 6]
B = []
C = [1, 2, 3, 4, 5, 6] 

Yes

Естественно объединить список и относящуюся к нему переменную в одну структуру. Такие структуры называют разностными списками и записывают обычно в виде [1,2,3|A]-A. В этих обозначениях определение соединения примет вид.

append_d(A-B,B-C,A-C).

Название "разностный список" объясняется тем, что структура A-B представляет список, получающийся при "вычитании" списка B из списка A. Например [1,2,3,4,5]-[4,5] и  [1,2,3]-[] представляют один и тот же список [1,2,3], а выражение  [1,2,3|A]-A -наиболее общий образец такого представления. При такой интерпретации определение append_d совершенно очевидно: A-B + B-C = A-C.

Разностные списки полезны главным образом в тех случаях, когда создается большое количество коротких списков, которые затем объединяются в один. Возьмем простой и хорошо знакомый пример. При "наивном" обращении к списку многократно присоединяется  список из одного элемента.

reverse([], []).
reverse([H|T],L) :- reverse(T,S), append(S,[H],L).

Попробуем заменить результат процедуры разностным списком. Процедура reverse_d создает разностный список, представляющий обращение данного списка.

reverse_d([], X-X).
reverse_d([H|T],L-L1) :- reverse_d(T,S-S1), append_d(S-S1,[H|X]-X,L-L1).

Используя определение append_d, можно переписать второе правило

reverse_d([H|T],L-L1) :- reverse_d(T,S-S1), S1=[H|X],L=S,L1=X.

или, выполнив подстановки

reverse_d([H|T],L-X) :- reverse_d(T,L-[H|X]).

Собирая все вместе, получаем

reverse(L,R):-  reverse_d(L,R-[]).

reverse_d([],X-X).
reverse_d([H|T],L-X) :- reverse_d(T,L-[H|X]).

Можно заметить, что это определение практически эквивалентно процедуре с накопителем. Вообще разностные списки часто позволяют получать программы, аналогичные использующим накопители, но имеющие ясный декларативный смысл.

Еще один типичный пример - создание списка узлов двоичного дерева. Прямая реализация

nodes(empty,[]).
nodes(bt(X,Lt,Rt), [X|Xs]) :- 
    nodes(Lt,Ls), 
    nodes(Rt,Rs), 
    append(Ls,Rs,Xs).

неэффективна из-за большого количества операций соединения. Используя разностные списки, можно избавится от них и значительно повысить скорость.

nodes(T,L):-nodes_d(T,L-[]).

nodes_d(empty,L-L).
nodes_d(bt(X,Lt,Rt),[X|L]-Z) :- 
    nodes_d(Lt,L-Y), 
    nodes_d(Rt,Y-Z).

Упражнение.

Процедура nodes выдает узлы дерева в префиксном порядке. Напишите процедуры, выдающие узлы в инфиксном и постфиксном порядке.

Все эти процедуры используют обход дерева в глубину - каждый узел обрабатывается совместно с его сыновьями. Он легко реализуется, поскольку хорошо согласуется с тем, как выполняются вложенные вызовы процедур. При обходе в ширину сначала обрабатывается корневой узел, затем узлы первого уровня и .т.д. Его  реализация не так очевидна. Один достаточно простой алгоритм использует очередь деревьев. Сначала в очередь помещается исходное дерево. Затем на каждом шаге обрабатывается вершина дерева, находящегося в голове очереди, а его сыновья помещаются в хвост. Для представления очереди естественно использовать список.

bf_nodes(T,L):- bf_nodes_a([T],L).

bf_nodes_a([],[]).
bf_nodes_a([empty|Ts],L) :- bf_nodes_a(Ts,L).
bf_nodes_a([bt(X,Lt,Rt)|Ts],[X|L]) :- 
    append(Ts,[Lt,Rt],Ts1),
    bf_nodes_a(Ts1,L).

Однако, эта процедура оказывается очень медленной. Накладные расходы, вызванные обращениями к append, еще значительнее, чем при обходе в глубину. Применение разностных списков позволяет исключить эти вызовы.

bf_nodes(T,L):- :- bf_nodes_d([T|Z]-Z,L).

bf_nodes_d([]-[],[]).
bf_nodes_d([empty|Ts]-Z,L) :- bf_nodes_d(Ts-Z,L).
bf_nodes_d([bt(X,Lt,Rt)|Ts]-[Lt,Rt|Z],[X|L]) :- bf_nodes_d(Ts-Z,L).

Упражнение.

Оцените вычислительную сложность различных процедур обхода дерева.

¹ Кстати, термин "хвостовая рекурсия" приобретает наглядность: процедура состоит из предложений, в которых рекурсивный вызов стоит в конце.

² Такие средства есть, например, в языке запросов к функциональным базам данных Daplex. Там бы можно было бы записать что-то вроде "for the p such that boss(p)= barbara..." Но, очевидно, эта конструкция выходит за рамки функционального программирования. 

³ В принципе, ничто не мешает нам написать произвольный одноместный предикат и объявить его определением типа данных. Вопрос: будет ли в этом смысл?

⁴ Конечно, при откате переменные теряют свои значения и могут получить новые, но это совсем не похоже на деструктивное присваивание императивных языков и проявляется только при использовании побочных эффектов.

[ Содержание | 1 | 2 | 3 | 4 | 5 | 5.1 | 5.2 | 5.3 | 5.4 | 5.5 | 5.6 | 5.7 | 5.8 | 5.9 | 6 | 6.1 | 6.2 | 6.3 | 6.4 | 6.5 | 7 | 7.1 | Литература ]