% Programming assignment 4 - Prolog 1
% Don Hopkins
% CMSC 412

fact(1,1) :- !.
fact(X,Y) :- A is X-1, fact(A,B), Y is X*B, !.

fib(1,1) :- !.
fib(2,1) :- !.
fib(X,Y) :- A is X-1, B is X-2, fib(A,C), fib(B,D), Y is C+D, !.

member(X,[X|_]) :- !.
member(X,[_|Y]) :- member(X,Y).

efface(A,[A|L],L) :- !.
efface(A,[B|L],[B|M]) :- efface(A,L,M).
efface(_,[],[]).

difference([],Y,Y).
difference([A|X],Y,Z) :- member(A,Y), !,
			 efface(A,Y,B), 
			 difference(X,B,Z).
difference([A|X],Y,[A|Z]) :- difference(X,Y,Z).

aless(X,Y) :- name(X,L), name(Y,M), alessx(L,M). 
alessx([],[_|_]). 
alessx([X|_],[Y|_]) :- X < Y. 
alessx([A|X],[A|Y]) :- alessx(X,Y). 

printstring([]).
printstring([H|T]) :- put(H), printstring(T).

program(R) :- printstring("What sentence should be sorted? "),
	      readlist(L),
	      quisort(L,R).

white(32).
white(10).

getword([],C) :- white(C), !.
getword([C|W],C) :- get0(D), getword(W,D).

readlist(L) :- get0(C), getword(W,C), name(Y,W), rl(L,Y).

rl([],end) :- !.
rl([W|L],W) :- get0(C), getword(X,C), name(Y,X), rl(L,Y).

order(X,Y) :- aless(X,Y).

split(H,[A|X],[A|Y],Z) :- order(A,H), split(H,X,Y,Z).
split(H,[A|X],Y,[A|Z]) :- not(order(A,H)), split(H,X,Y,Z).
split(_,[],[],[]).

quisort(A,B) :- quisortx(A,B,[]).
quisortx([],X,X).
quisortx([H|T],S,X) :- split(H,T,A,B),
		       quisortx(A,S,[H|Y]),
		       quisortx(B,Y,X).

ordered_union([],X,X).
ordered_union(X,[],X).
ordered_union([A|X],[A|Y],[A|Z]) :- !, ordered_union(X,Y,Z).
ordered_union([A|X],[B|Y],[A|Z]) :- aless(A,B), !, ordered_union(X,[B|Y],Z).
ordered_union([A|X],[B|Y],[B|Z]) :- !, ordered_union([A|X],Y,Z).