ы использования структур
Сортировка списка с использованием дерева
% tree_sort(+X,-Y)
% X - исходный список, результат Y - упорядоченный список
tree_sort(X,Y):-
make_tree(X,Z),
flat(Z,Y).
% make_tree(+X, -Y) - создание упорядоченного дерева Y из списка X
make_tree([],nil).
make_tree([H|T],Z):-
make_tree(T,Y),
insert(H,Y,Z).
% insert(+N,+X,-Y) - вставка элемента N в упорядоченное дерево X
insert(N,nil,tree(nil,N,nil)).
insert(N,tree(L,Root,R),tree(L1,Root,R)):-
N =< Root,
insert(N,L,L1).
insert(N,tree(L,Root,R),tree(L,Root,R1)):-
N > Root,
insert(N,R,R1).
% flat(+X,-Y) - разглаживание дерева X в список Y
flat(nil,[]).
flat(tree(L,N,R),Z):-
flat(L,L1),
flat(R,R1),
append(L1,[N|R1],Z).
?- make_tree([8,10,6,5],X).
X = tree(nil, 5, tree(nil, 6, tree(tree(nil, 8, nil), 10, nil)))
Yes
Дифференцирование
Задача. Написать предикат dv(+Term,+Atom,-Term2), где Term2 есть результат дифференцирования Term1 по математической переменной Atom. Term1 - арифметическое выражение, составленное из атомов и чисел с использованием скобок, знаков операций +, -, *, /, ^ и функций sin(x), cos(x), ln(x) и e^x.
Логическая программа дифференцирования - просто набор соответствующих правил дифференцирования.
dv(X,X,1).
dv(Y,_,0):-
number(Y).
dv(Y,X,0):-
atom(Y),
X \= Y.
dv(X^N,X,N*X^(N-1)):-
number(N).
dv(sin(X),X,cos(X)).
dv(cos(X),X,-sin(X)).
dv(e^X,X,e^X).
dv(ln(X),X,1/X).
dv(Y+Z,X,(DY+DZ)):-
dv(Y,X,DY),
dv(Z,X,DZ).
dv(Y-Z,X,(DY-DZ)):-
dv(Y,X,DY),
dv(Z,X,DZ).
dv(Y*Z,X,DY*Z+DZ*Y):-
dv(Y,X,DY),
dv(Z,X,DZ).
dv(Y/Z,X,(DZ*Y-DY*Z)/Z*Z):-
dv(Y,X,DY),
dv(Z,X,DZ).
Правило дифференцирования сложной функции представляет собой более тонкий случай. В правиле утверждается, что производная от f(g(x)) по x есть производная f(g(x)) по g(x), умноженная на производную g(x) по x.
В данной форме правило использует квантор по функциям и находится вне области логического программирования, рассматриваемого нами. Нам понадобится встроенный предикат =../2.
?Term =.. ?List
List есть список, голова которого есть функтор терма Term и остальные элементы суть аргументы терма. Каждый из аргументов может быть переменной, но не оба сразу. Этот предикат называется `Univ'.
?- foo(hello, X) =.. List.
List = [foo, hello, X]
?- Term =.. [baz, foo(1)]
Term = baz(foo(1))
Использование предиката univ позволяет изящно задать правило дифференцирования сложных функций.
dv(F_G_X,X,DF*DG):-
F_G_X =.. [_,G_X],
dv(F_G_X,G_X,DF),
dv(G_X,X,DG).
Предикат dv выдает результат дифференцирования в неупрощенном виде.
?-dv(3*y+a,y,D).
D = 3*1 +0*y +0
Yes
Последовательность одинакова плоха и для ума и для тела. Последовательность чужда человеческой природе, чужда жизни. До конца последовательны только мертвецы.
Олдос Хаксли
