%%% FCP Ex. 3.3 %%%

:-lib(ic).


%%%%%%% 3.3 a) %%%%

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


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


%%%%%%% 3.3 b) %%%%

sorted([]).
sorted([_]).
sorted([X,Y|R]):- X#=<Y, sorted([Y|R]).

permsort(L,SL) :- perm(L,SL), sorted(SL).


%%%%%%% 3.3 c) %%%%

permsort2(L,SL) :- samelength(L,SL), sorted(SL), perm(L,SL).

samelength([],[]).
samelength([_|T1],[_|T2]) :- samelength(T1,T2).