export qsort($X,Y).

/*
export app($X,$Y,Z).
export app($X,Y,$Z).
export app(X,$Y,$Z).
export app($X,$Y,$Z).
export reverse($X,Y).
export reverse($X,$Y).
export reverse1($X,Y).
export reverse1($X,$Y).
export fib($X,Y).
export factorial($X, F).
export power($X,$Y,Z).
export sum($X,$Y,Z).
export hanoi($X,Y).
export move($X,$Y,$Z,$W,Q).
export ack($X,$Y,Z).
*/

qsort([],[]).
qsort([X|L],S) <-
	split(L,X,L1,L2),
      	qsort(L1,S1),
        qsort(L2,S2),
	append(S1,[X|S2],S).

split([],_,[],[]).
split([Y|M],X,[Y|M1],M2) <-
	Y <= X,
	split(M,X,M1,M2).
split([Y|N],X,N1,[Y|N2]) <-
	Y > X,
	split(N,X,N1,N2).

/*
qsort([],[]).
qsort([X|L],S) <-
	split(L,X,L1,L2),
      	qsort(L1,S1),
        qsort(L2,S2),
	append(S1,[X|S2],S).

split([],_,[],[]).
split([Y|L],X,[Y|L1],L2) <-
	Y <= X,
	split(L,X,L1,L2).
split([Y|L],X,L1,[Y|L2]) <-
	Y > X,
	split(L,X,L1,L2).
*/

app([], List, List).
app([X|List1], List2, [X|List3]) <-
	app(List1, List2, List3).

reverse([], []).
reverse([X|List], ReverseList) <-
	reverse(List, ReverseList0),
	app(ReverseList0, [X], ReverseList).

reverse1([], []).
reverse1([X|List], ReverseList) <-
	reverse1(List, ReverseList0),
	append(ReverseList0, [X], ReverseList).

fib(0,1).
fib(1,1).
fib(X,Y) <-
	X > 1,
	X1 = X-1,
	X2 = X1-1,
	fib(X1,Y1),
	fib(X2,Y2),
	Y = Y1+Y2.

fibo(N,F) <-
	N > 0,
	fibacc(N,0,1,F).

fibacc(1,_,F,F).
fibacc(N,A1,A2,F) <-
	N > 1,
	N1 = N-1,
	Acc = A1+A2,
	fibacc(N1,A2,Acc,F).

factorial(0, 1).
factorial(X, F) <-
	X > 0,
	X1 = X - 1,
	factorial(X1, F1),
	F = F1 * X.

power(_, 0, 1).
power(X, N, P) <-
	N > 0,
	N1 = N - 1,
	power(X, N1, P1),
	P = P1 * X.

sum(_, 0, 0).
sum(X, N, P) <-
	N > 0,
	N1 = N - 1,
	sum(X, N1, P1),
	P = P1 + X.

% hanoi(N,M) :- move(N,a,b,c,M).
hanoi(N,M) :- move(N,'A','B','C',M).

move(0,_,_,_,0).
move(N,A,B,C,M) <-
	N > 0,
 	N1 = N - 1,
        move(N1,A,C,B,M1),
        move(N1,C,B,A,M2),
        M = M1 + M2 + 1.

ack(0,0,1).                                                       
ack(0,N,V) <-
	N > 0,
	N1 = N-1,
	ack(0,N1,V1),
	V = V1+1.                  
ack(M,0,V) <-
	M > 0,
	M1 = M-1,
	ack(M1,1,V).
ack(M,N,V) <-
	M > 0,
	N > 0,
	N2 = N-1,
	ack(M,N2,V1),
	M1 = M-1,
	ack(M1,V1,V).