Логическое программирование

ы использования структур


Сортировка списка  с использованием дерева

% 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
Последовательность одинакова плоха и для ума и для тела. Последовательность чужда человеческой природе, чужда жизни. До конца последовательны только мертвецы.
Олдос Хаксли

Содержание раздела