Mestint nyelvek 3.gyak all

%2.gyak anyaga:
%elso(x,l) : X az első eleme L-nek, L az egy lista, X pedig egy elem
elso(X,L) :- L=[X|_].
%utolso(X,L): X az utolsó eleme L-nek
utolso(X, [X]).
utolso(X,[_,Z|L]) :- utolso(X,[Z|L]).
%nemb(X,L) : X eleme L-nek
memb(X, [X|_]).
memb(X[_|L]) :- memb(X,L).
%ins(X,L,M) : X-et L-be beszúrással kapjuk M-et
ins(X,L,[X|L]).
ins(X,[Y|L1],[Y|M1]) :- ins(X,L1,M1).
%sel(X,L,M): X n példáját elhagyva L-ből kapunk M-et
sel(X,L,M) :- ins(X,M,L).
%rev
rev([],[]).
rev([X],[X]).
rev([X|L],M) :- rev(L,N),append(N,[X],M).

revuj(L,M) :- revuj(L,[],M).
revuj([],M,M).
revuj([X|L], A, M) :- revuj(L, [X|A], M).
%Kap egy listát, a fejet átrakja A-ba, és az egészet M-be.
%
%app(L,M,N): L + M konkatenálása N-be
app([],M,M).
app([X|L],M,N) :- app(L,M,K),N=[X|K].

lth([],0).
lth([_|L],N) :- lth(L,M), N is M+1.

inssort([],[]).
inssort([X|L],M) :- inssort(L,N), insop(X,N,M).

insop(X,[],[X]).
insop(X, [Y|N], S) :- X=<Y, S = [X,Y|N].
insop(X, [Y|N], [Y|S]) :- Y<X, insop(X,N,S).

%3. gyak anyaga:
%összefűzéses rendezés
%Van egy lista, kettébontjuk, L1 és L2
%Rekurzív lépés:
%   L1 első eleme: X
%   L2 első eleme: Y
%   Ha X =< Y
%       X berak, L1 első eleme: M, L2 első eleme: Y
%   Ha X > Y
%       Y berak, ...
%Bemeneti lista: L
%Kimeneti lista: N
%Bemeneti: SO, SE (listák)
%Kimeneti: N
%! --> több alternatívát ne nézzen
mergesort([], []) :- !.
mergesort([X], [X]) :- !.
mergesort(L,N) :- split(L,O,E), mergesort(O, SO), mergesort(E,SE), merge(SO,SE,N).
merge(SO,SE,N) :- merge(SO,SE,[],N).
merge([X|SO],[Y|SE], A, N) :- X=<Y, merge(SO,[Y|SE],[X|A], N).
merge([X|SO],[Y|SE],A,N) :- X>Y, merge([X|SO], SE, [Y|A], N).
%Az SE-ben van egy olyan nagy elem, ami nagyobb, mint a többi
merge([], SE, A, N) :- reverse(A,B), append(B,SE,N).
merge(SO,[],A,N) :- merge([], SO, A, N).

split(L, O, E) :- odd(L, [], [], O, E).
odd([], A, B, A, B).
odd([X|L], A, B, O, E) :- even(L, [X|A], B, O, E).
even([], A, B, A, B).
even([X|L], A, B, O, E) :- odd(L, A, [X|B], O, E).