% Lista összefűzese segedfüggveny
% SzP:  helyesen:   segédeljárás
app([], L2, L2).
app([X|L1], L2, [X|L3]) :- app(L1, L2, L3).

% 1. feladat
% seq(+N, +M, −L): Az L lista M−N+1 hosszú, elemei 1 különbsegű szamtani
% sorozatot alkotnak, es L elso eleme (ha van) N, ahol N es M egesz szamok.
seq(N, M, L) :-
	Length is M-N+1,           % (*)
	(   Length =:= 0,          % SzP: vessző helyett -> ajánlott, mert hatékonyabb 
	    L = []
	;   Length > 0,
	    seq(N, M - 1, L2),
	    % SzP: érdemes a seq hívás előtt  M - 1 -et is/2-vel kiszámolni, mert most, 
	    % ha pl. seq(5, 100, L) a cél, akkor a (*) sorban a rekurzió során rendre a
	    %     Length is 100-5+1
	    %     Length is 100-5-1+1
	    %     Length is 100-5-1-1+1
	    %     Length is 100-5-1-1-1+1
	    %     ...
	    % alakú hívások futnak, (N-M)^2 kiértékelési idővel
	    N2 is N + (M-N+1) -1,
	    % SzP: egszerűbb lett volna N2 helyett M-et írni :-)
	    app(L2, [N2], L)
	    % SzP: Ez megint egy négyzetes faktor, mert app/2 futása L2 hosszával arányos.
	    % Jobb ha a rekurzív hívás seq(``N+1'', M, ...), akkor az eredménylista *elé* 
	    % kell az N számot rakni, ami konstans idejű művelet.
	).

% 2. feladat
% max(+N, ?X): X egy egesz szam, melyre 0 < X =< N, ahol N adott
% pozitív egesz szam. Az eljaras a fenti felteteleknek megfelelo X
% szamokat sorolja fel. A felsorolas sorrendjere nem teszünk megkötest.
max(N, X) :-
 	(   N > 0,
	    X is N   % SzP: Én itt is/2 helyett = /2-t használnék, az is/2 ugyanis meg kell 
                     % vizsgálja az N változót, hogy értéke aritmetikai kifejezés-e, ami lassíthat.
	;   N > 1,
	    N2 is N - 1,
	    max(N2, X)
	).

% 3. feladat
% hatv(+A, +E, −H): H = A ^ E, ahol A egesz szam, E >= 0 egesz szam.
hatv(_, 0, 1).
hatv(A, 1, A).     % SzP: Ez a sor elhagyható, ha két sorral lejebb 1 helyett 0-t írunk
                   % SzP: 0,1,... helyett mindig jobb 0,...-ban gondolkodni !!!
hatv(A, E, H) :-
	E > 1,
	E2 is E - 1,
	hatv(A, E2, H2),
	H is H2*A.
% SzP: célszerűbb egy az if-then-else szerkezetet használó megoldás, 
% mert az nem hagy maga után választási pontot

% 4. feladat
% fa_pontszama(*Fa, −N): A Fa binaris fa csomópontjainak szama N.
 
fa_pontszama(leaf(_), SUM) :-
	SUM is 0.
% SzP: egyszerűbben:
% fa_pontszama(leaf(_), 0).
fa_pontszama(node(Left, Right), SUM) :-
	fa_pontszama(Left, SUM1),
	fa_pontszama(Right, SUM2),
	SUM is SUM1 + SUM2 + 1.

% 5. feladat
%fa_noveltje(*Fa0, ?Fa): Fa úgy all elo a Fa0 binaris faból, hogy az
% utóbbi minden egyes leveleben levo erteket 1−gyel megnöveljük.
fa_noveltje(leaf(V), FA) :-
	V2 is V + 1,
	FA = leaf(V2).
fa_noveltje(node(Left, Right), FA) :-
	fa_noveltje(Left, FA1),
	fa_noveltje(Right, FA2),
	FA = node(FA1, FA2).
% SzP: a fenti két klózban célszerű a FA = hívásokat kiküszöbölni a fejbeli 
% FA változót a megfelelő kifejezésre cserélve.

% 6. feladat
% lista_hossza(*Lista, −Hossz): A Lista egeszlista hossza Hossz.
lista_hossza([], 0).
lista_hossza([_|T], Hossz) :-
	lista_hossza(T, Hossz1),
	Hossz is Hossz1 + 1.

% 7. feladat
% lista_noveltje(*L0, ?L): Az L egeszlista úgy all elo az L0
% egeszlistaból, hogy az utóbbi minden egyes elemet 1−gyel megnöveljük.
lista_noveltje([], []).
lista_noveltje([H|T], L) :- 	
	lista_hossza(T, T_HOSSZ),
	(   T_HOSSZ > 0,   % SzP: vessző helyett '->' hatékonyabb
	    H2 is H + 1,
	    lista_noveltje(T, L2),
	    L = [H2|L2]    % SzP: érdemes a rek. hívás elé tenni (jobbrekurzíó)
	;   T_HOSSZ =:= 0, % ez az ág elhagyható (0,1,... helyett 0,...)  
	    H2 is H + 1,
	    L = [H2]
	).

% 8. feladat
% lista_utolso_eleme(*L, ?Ertek): Az L egeszlista utolsó eleme Ertek.
% SzP: eljárások közé mindig tegyünk üres sort, segédeljáráshoz írjunk fejkommentet
% SzP: lista_feje(L, H): L nem üres és feje H.
lista_feje([H|_], H).

lista_utolso_eleme([H|T], Ertek) :-
	lista_hossza(T, HOSSZ),
        % SzP: lista_hossza/2 futási ideje a lista hosszával arányos, 
        % emiatt lista_utolso_eleme négyzetes futású.
        % Ugyanakkor az hogy valami legalább egyelemű lista-e, konstans időben is eldönthető.
	(   HOSSZ > 1,
	    lista_utolso_eleme(T, Ertek1),
	    Ertek is Ertek1
	    % SzP: Ha is/2 helyett = van, akkor nemcsak számlistákra működik
	    % SzP: Ha az = /2 hívást kiküszöböljük azzal, hogy Ertek1 helyébe 
            % az Ertek változót írjuk, akkor jobbrekurzívvá is tesszük az eljárást
	;   HOSSZ =:= 1,
	    lista_feje(T, Ertek)
	;   HOSSZ =:= 0,
	    Ertek is H
	).
% SzP: A fenti megint "..., 1, 0" stílusú kód, egyszerűbb a csak kétfelé ágazó változat

% 9. feladat
% fa_levelerteke(*Fa, −Ertek): A Fa binaris fa egy leveleben talalható
% ertek az Ertek.
fa_levelerteke(leaf(V), V).
fa_levelerteke(node(Left, _), Ertek) :-
	fa_levelerteke(Left, Ertek).
fa_levelerteke(node(_, Right), Ertek) :-
	fa_levelerteke(Right, Ertek).

% 10. feladat
% fa_reszfaja(*Fa, −Resz): Resz a Fa binaris fa reszfaja.
fa_reszfaja(leaf(V), leaf(V)).                     %(**)
fa_reszfaja(node(Left, Right), ReszFa) :-
	(   fa_reszfaja(Left, ReszFa)
	;   fa_reszfaja(Right, ReszFa)
	;   ReszFa = node(Left, Right)             %(**)  
	).
% SzP: Egy apró optimalizálás: A (**) sorok kiválthatók ezzel a tényállítással:
% fa_reszfaja(Fa, Fa).

% Lista eleje segedfüggveny
lista_eleje([_], []).
lista_eleje([X|Xs], [X|ELEJE]) :-
	lista_eleje(Xs, ELEJE).
% SzP: hiányzó fejkomment:
% lista_eleje(L, E) :- Az L nem üres listából az utolsó elemet elhagyva kapjuk E-t.

% 11. feladat
% lista_prefixuma(*L0, −L): L az L0 egeszlista prefixuma.
lista_prefixuma(L0, L):-
	(   L = L0
	;   lista_eleje(L0, L2),
	    lista_prefixuma(L2, L)
	).
% SzP: a lista_eleje futási ideje arányos a lista hosszával, 
% ezért a lista_prefixuma négyzetes idejű.
% Az app/3 eljárás képes lineáris időben felsorolni a prefixumokat, ez
% ötletet adhat a lineáris idejű lista_prefixuma megírásához.