% Collected Prolog code of Chapter 12 from
% Kenneth C. Louden, Programming Languages
% Principles and Practice 2nd Edition
% Copyright (C) Brooks-Cole/ITP, 2003

% page 552

ancestor(X,Y) :- parent(X,Z), ancestor(Z,Y).
ancestor(X,X).
parent(amy,bob).

natural(0).
natural(successor(X)) :- natural(X).

% page 555

valequal(Term1, Term2) :-
	X is Term1, Y is Term2, X=Y.

gcd(U,0,U).
gcd(U,V,W) :- 
	not(V=0) , R is U mod V, gcd(V,R,W).

% page 557

cons(X,Y,[X|Y]).

% name changed to append1 to avoid conflict
% with built-in append
append1([],Y,Y).
append1([A|B], Y, [A|W]) :- append1(B,Y,W).

% page 558

% name changed to reverse1 to avoid conflict
% with built-in reverse
reverse1([],[]).
reverse1([H|T],L) :- reverse1(T,L1),
                    append(L1,[H],L).

% page 560

printpieces(L) :- append(X,Y,L),
                  write(X),
                  write(Y),
                  nl,
                  fail.

% page 562

num(0).
num(X) :- num(Y), X is Y+1 .
writenum(I,J) :- num(X),
                 I =< X,
                 X =< J,
                 write(X), nl,
                 X = J, !,
                 fail.

% page 563

primes(Limit, Ps) :- integers(2,Limit,Is),
                     sieve(Is,Ps).
integers(Low, High, [Low|Rest]) :-
	Low =< 	High, !, M is Low+1,
	integers(M,High,Rest).
integers(Low,High,[]).
sieve([],[]).
sieve([I|Is],[I|Ps]) :- remove(I,Is,New),
                        sieve(New,Ps).
remove(P,[],[]).
remove(P,[I|Is],[I|Nis]) :-
	not(0 is I mod P), !, remove(P,Is,Nis).
remove(P,[I|Is],Nis) :-
	0 is I mod P, !, remove(P,Is,Nis).

% page 567

% name changed to sort1 to avoid conflict
% with built-in sort
sort1(S,T) :- permutation(S,T), sorted(T).

sorted([]).
sorted([X]).
sorted([X,Y|Z]) :- X =< Y, sorted([Y|Z]).

permutation([],[]).
permutation(X,[Y|Z]) :- append(U,[Y|V],X),
                        append(U,V,W),
                        permutation(W,Z).

qsort([],[]).
qsort([H|T],S) :- partition(H,T,L,R),
                  qsort(L,L1),
                  qsort(R,R1),
                  append(L1,[H|R1],S).
partition(P, [A|X], [A|Y], Z) :- A < P,
		partition(P,X,Y,Z).
partition(P, [A|X], Y, [A|Z]) :- A >= P,
                                 partition(P,X,Y,Z).
partition(P,[],[],[]).