Zdroj



% na přednášce: otočení seznamu v lineárním čase, apod.

% max(+Seznam, -MaxPrvek)
max1([M], M).
max1([S1|Sz], M) :- max1(Sz, Mz), M is max(S1,Mz).
% max1 není koncově rekurzivní (tail-recursive),
% 	pomožme hloupému interpreteru s optimalizací

max2([X|Xs], M) :- max2(Xs, X, M).
max2([], M, M).
max2([X|Xs], SoFar, M) :- M0 is max(X, SoFar), max2(Xs, M0, M).


% strom2sez(+Strom, -SeznamKlicu)
% 	list nebo uzel(L, K, P)
% 	tentokrát chceme v lineárním čase

strom2sez(T, L) :- strom2sez(T, L, []).
% strom2sez(+Strom, -SeznamKlíčů_spojený_s_Append, +Append)
strom2sez(list, S, S).
strom2sez(uzel(L, K, R), S, A) :-
	strom2sez(R, RS, A), strom2sez(L, S, [K|RS]).


% zplošťování seznamu v lineárním čase
% zplosti(+Seznam, -Zploštěný)
% ?- zplosti([a,2,[3,[4,c],a],1,[],2], S).
% S = [a, 2, 3, 4, c, a, 1, 2] .
zplosti([],[]).
zplosti([A|B],S):- ( A = [] ; A = [_|_] ),
	zplosti(A,U),zplosti(B,V),append(U,V,S).
zplosti([A|B],[A|V]):- ( A \= [] , A \= [_|_] ),
	zplosti(B,V).

% zplosti(+Seznam, -Zploštěný_spojený_s_Append, +Append)
zplosti2(S, F) :- zplosti2(S, F, []).
zplosti2([], A, A).
%zplosti2([H|T], F, A) :- ((H = [] ; H = [_|_]),
%	zplosti2(H, F, EH), ! ;F=[H|EH]),
%	zplosti2(T, EH, A).
% zase můžeme prohodit oba kroky
zplosti2([H|T], F, A) :- zplosti2(T, EH, A),
	((H = [] ; H = [_|_]), zplosti2(H, F, EH), ! ; F=[H|EH]).

Dotazy