-module(futam). -compile(export_all). %%% Első változat: futam és maradék előállítása két függvénnyel %% @spec futam:futamok1(Pred:pred(),List:[elem()]) -> Lists:[[elem()]] %% @type pred() = elem() * elem() -> bool() %% @type elem() = any() %% Lists a List szomszédos elemeiből álló, Pred-et kielégítő futamok listája %% fun futamok1 p [] = [] %% | futamok1 p (x::xs) = %% let val fs = futam1 p (x, xs) %% val ms = maradek1 p (x, xs) %% in %% if null ms then [fs] else fs :: futamok1 p ms %% end futamok1(_P,[]) -> []; futamok1(P,[X|Xs]) -> Fs = futam1(P,X,Xs), Ms = maradek1(P,X,Xs), case Ms of [] -> [Fs]; Zs -> [Fs|futamok1(P,Zs)] end. %% (* futam : ('a * 'a -> bool) -> ('a * 'a list) -> 'a list %% futam p (x, ys) = az x::ys p-t kielégítő első (prefix) futama *) %% fun futam p (x, []) = [x] %% | futam p (x, y::ys) = if p(x, y) then x :: futam p (y, ys) else [x] futam1(_P,X,[]) -> [X]; futam1(P,X,[Y|Ys]) -> case P(X,Y) of true -> [X|futam1(P,Y,Ys)]; false -> [X] end. %% (* maradek : ('a * 'a -> bool) -> ('a * 'a list) -> 'a list %% maradek p (x, ys) = az x::ys p-t kielegítő futama utáni maradéka *) %% fun maradek p (x, []) = [] %% | maradek p (x, yys as y::ys) = %% if p(x ,y) then maradek p (y, ys) else yys maradek1(_P,_X,[]) -> []; maradek1(P,X,[Y|Ys]=YYs) -> case P(X,Y) of true -> maradek1(P,Y,Ys); false -> YYs end. %%% Példa t1(0) -> futamok1(fun(A,B) -> A bool) -> 'a list -> 'a list list %% futamok2 p xs = az xs p-t kielégítő futamaiból álló lista %% *) %% fun futamok2 p [] = [] %% | futamok2 p (x::xs) = %% let (* futam : ('a * 'a list) -> 'a list * 'a list %% futam (x, ys) zs = olyan pár, amelynek első tagja az x::ys p-t %% kielégítő első (prefix) futama a zs elé %% fűzve, második tagja pedig az x::ys maradéka %% *) %% fun futam (x, []) zs = (rev(x::zs), []) %% | futam (x, yys as y::ys) zs = if p(x, y) %% then futam (y, ys) (x::zs) %% else (rev(x::zs), yys); %% val (fs, ms) = futam (x, xs) [] %% in %% fs :: futamok2 p ms %% end futamok2(_P,[]) -> []; futamok2(P,[X|Xs]) -> {Fs, Ms} = futam2(P,X,Xs,[]), [Fs|futamok2(P,Ms)]. futam2(_P,X,[],Zs) -> {lists:reverse([X|Zs]), []}; futam2(P,X,[Y|Ys]=YYs,Zs) -> case P(X,Y) of true -> futam2(P,Y,Ys,[X|Zs]); false -> {lists:reverse([X|Zs]), YYs} end. %%% Példák t2(0) -> futamok2(fun(A,B) -> A futamok2(fun(A,B) -> A>=B end, [1,3,9,5,7,2,5,9,1,6,0,0,3,5,6,2]). %%% Harmadik változat: az aktuális futamot és a futamok listáját egyszerre gyűjtjük, %%% ezzel futamok2-t is jobbrekurzívvá tesszük %% (* futamok3 : ('a * 'a -> bool) -> 'a list -> 'a list list %% futamok3 p xs = az xs p-t kielégítő futamaiból álló lista %% *) %% fun futamok3 p [] = [] %% | futamok3 p (x::xs) = %% let (* futamok : ('a * 'a list) -> 'a list -> 'a list * 'a list %% futamok (x, ys) zs zss = az x::ys p-t kielégítő futamaiból %% álló lista zss elé fűzve %% *) %% fun futamok (x, []) zs zss = rev(rev(x::zs)::zss) %% | futamok (x, yys as y::ys) zs zss = %% if p(x, y) %% then futamok (y, ys) (x::zs) zss %% else futamok (y, ys) [] (rev(x::zs)::zss) %% in %% futamok (x, xs) [] [] %% end; futamok3(_P,[]) -> []; futamok3(P,[X|Xs]) -> futamok3(P,X,Xs,[],[]). futamok3(_P,X,[],Zs,Zss) -> lists:reverse([lists:reverse([X|Zs])|Zss]); futamok3(P,X,[Y|Ys],Zs,Zss) -> case P(X,Y) of true -> futamok3(P,Y,Ys,[X|Zs],Zss); false -> futamok3(P,Y,Ys,[],[lists:reverse([X|Zs])|Zss]) end. %%% Példák t3(0) -> futamok3(fun(A,B) -> A futamok3(fun(A,B) -> A>=B end, [1,3,9,5,7,2,5,9,1,6,0,0,3,5,6,2]); t3(2) -> futamok3(fun(A,B) -> 2*A>B end, [1,3,9,5,7,2,5,9,1,6,0,0,3,5,6,2]). %%% További példák t4(0) -> futam1(fun(A,B) -> A= maradek1(fun(A,B) -> A= futamok1(fun(A,B) -> A= futamok1(fun(A,B) -> A= futamok1(fun(A,B) -> A= futamok1(fun(A,B) -> A=