male(gustav).
male(X) :- father(X, _).
feamale(stina).
feamale(eva).
feamale(lena).
father(gustav, eva).
father(gustav, lena).
father(oskar, gustav).
mother(stina, eva).
wife(gustav, stina).

husband(X, Y) :- wife(Y, X).
son(X, Y) :- male(X), father(Y, X).
sonOfGustav(X) :- male(X), father(gustav, X).
grandfather(X, Z) :- father(X, Y), father(Y, Z).

num(0).
num(suc(N)) :- num(N).
plus(N, 0, N) :- num(N).
plus(N, suc(M), suc(NpM) ) :- plus(N, M, NpM).

lst(empty).
lst(cons(_, Xs)) :- lst(Xs).

app([], Ys, Ys).
app([X|Xs], Ys, [X|Zs]) :- app(Xs, Ys, Zs).

sorted(Xs,Ys) :-  permutation_(Xs,Ys), ordered(Ys).

ordered([]).
ordered([_]).
ordered([X,Y|Ys]) :- X =< Y, ordered([Y|Ys]).

select_(X,[X|Xs],Xs).
select_(X, [Y|Ys], [Y|Zs]) :- select_(X,Ys,Zs).

permutation_([], []).
permutation_(Xs, [Z|Zs]) :- select_(Z,Xs,Ys), permutation_(Ys,Zs).

split([], [], []).
split([X], [X], []).
split([X,Y|Zs], [X|Xs], [Y|Ys]) :- split(Zs,Xs,Ys).

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

mergesort([],[]).
mergesort([X],[X]).
mergesort([X, Y|Xs], Rs) :- split([X,Y|Xs], Ys, Zs), mergesort(Ys, Ys1),
	mergesort(Zs, Zs1), merge(Ys1, Zs1, Rs).

%%% Local Variables:
%%% mode: prolog
%%% End:
