Prologの技芸 11.1節の練習問題

(1)

% クイックソート
% quicksort(Xs,Ys) :-
%  リストYsはリストXsの順序付けられた順列である．

quicksort([X|Xs],Ys) :-
 partition(Xs,X,Littles,Bigs),
 quicksort(Littles,Ls),
 quicksort(Bigs,Bs),
 append(Ls,[X|Bs],Ys).
quicksort([],[]).

partition([X|Xs],Y,[X|Ls],Bs) :-
 X =< Y, !, partition(Xs,Y,Ls,Bs).
partition([X|Xs],Y,Ls,[X|Bs]) :-
 X > Y, !, partition(Xs,Y,Ls,Bs).
partition([],Y,[],[]).

(2)

% derivative(Expression,X,DifferentiatedExpression) :-
%  DifferentiatedExpressionは，
% 式ExpressionのXに関する導関数である．

constant(X) :- integer(X).
constant(X) :- atom(X).

derivative(X,_,0) :- constant(X), !.
derivative(X,X,s(0)) :- !.
derivative(X^N,X,N*X^M) :- integer(N), !, M is N-1.
derivative(sin(X),X,cos(X)) :- !.
derivative(cos(X),X,-sin(X)) :- !.
derivative(e^X,X,e^X) :- !.
derivative(log(X),X,1/X) :- !.
derivative(F+G,X,DF+DG) :-
 !, derivative(F,X,DF), derivative(G,X,DG).
derivative(F-G,X,DF-DG) :-
 !, derivative(F,X,DF), derivative(G,X,DG).
derivative(F*G,X,F*DG+DF*G) :-
 !, derivative(F,X,DF), derivative(G,X,DG).
derivative(1/F,X,-DF / (F*F)) :-
 !, derivative(F,X,DF).
derivative(F/G,X,(G*DF-F*DG)/(G*G)) :-
 !, derivative(F,X,DF), derivative(G,X,DG).

(3)

% 挿入ソート
% insertionsort(Xs,Ys) :-
%  リストYsはリストXsの順序付けられた順列である．
insertionsort([X|Xs],Ys) :-
 !, insertionsort(Xs,Zs), insert(X,Zs,Ys).
insertionsort([],[]).

insert(X,[],[X]) :- !.
insert(X,[Y|Ys],[Y|Zs]) :- X > Y, !, insert(X,Ys,Zs).
insert(X,[Y|Ys],[X,Y|Ys]) :- X =< Y, !.