-module(halmaz). -compile(export_all). %% (* isMem : ''a * ''a list -> bool %% isMem(x, ys) = x eleme-e ys-nek %% *) %% fun op isMem (_, []) = false %% | op isMem (x, y::ys) = x = y orelse op isMem(x, ys) %% infix isMem isMember(_,[]) -> false; isMember(X,[Y|Ys]) -> X==Y orelse isMember(X,Ys). isMember2(_,[]) -> false; isMember2(X,[X|_]) -> true; isMember2(X,[_Y|Ys]) -> isMember2(X,Ys). %% (* newMem : ''a * ''a list -> ''a list %% newMem(x, xs) = [x] és xs listaként ábrázolt uniója %% *) %% fun newMem (x, xs) = if x isMem xs %% then xs %% else x::xs newMember(X,Xs) -> case isMember(X,Xs) of true -> Xs; false -> [X|Xs] end. %% (* setof : ''a list -> ''a list %% setof xs = xs elemeinek listaként ábrázolt halmaza %% *) %% fun setof [] = [] %% | setof (x::xs) = newMem(x, setof xs) listToSet([]) -> []; listToSet([X|Xs]) -> newMember(X,listToSet(Xs)). %% (* union : ''a list * ''a list -> ''a list %% union(xs, ys) = az xs és ys elemeiből álló halmazok uniója %% *) %% fun union ([], ys) = ys %% | union (x::xs, ys) = newMem(x, union(xs, ys)) union([],Ys) -> Ys; union([X|Xs],Ys) -> newMember(X,union(Xs,Ys)). %% (* inter : ''a list * ''a list -> ''a list %% inter(xs, ys) = az xs és ys elemeiből álló halmazok metszete %% *) %% fun inter ([], _) = [] %% | inter (x::xs, ys) = let val zs = inter(xs, ys) %% in %% if x isMem ys then x::zs else zs %% end intersect([],_) -> []; intersect([X|Xs],Ys) -> Zs = intersect(Xs,Ys), case isMember(X,Ys) of true -> [X|Zs]; false -> Zs end. intersect2([],_) -> []; intersect2([X|Xs],Ys) -> case isMember(X,Ys) of true -> [X|intersect2(Xs,Ys)]; false -> intersect2(Xs,Ys) end. %% (* isSubset : ''a list * ''a list -> bool %% isSubset (xs, ys) = az xs elemeiből álló halmaz részhalmaza-e %% az ys elemeiből álló halmaznak %% *) %% fun op isSubset ([], _) = true %% | op isSubset (x::xs, ys) = x isMem ys andalso %% op isSubset(xs, ys) %% infix isSubset isSubset([],_) -> true; isSubset([X|Xs],Ys) -> isMember(X,Ys) andalso isSubset(Xs,Ys). %% (* isSetEq : ''a list * ''a list -> bool %% isSetEq(xs, ys) = az xs elemeiből álló halmaz egyenlő-e %% az ys elemeiből álló halmazzal %% *) %% fun isSetEq (xs, ys) = (xs isSubset ys) andalso (ys isSubset xs) isEqual(Xs,Ys) -> isSubset(Xs,Ys) andalso isSubset(Ys,Xs). %% (* pws : 'a list * 'a list -> 'a list list %% pws(xs, base) = mindazon halmazok listája, amelyek előállnak xs egy %% részhalmazának és a base halmaznak az uniójaként *) %% fun pws ([], base) = [base] %% | pws (x::xs, base) = pws(xs, base) @ pws(xs, x::base) pws([],Zs) -> [lists:reverse(Zs)]; %% [Zs] pws([X|Xs],Zs) -> pws(Xs,Zs) ++ pws(Xs,[X|Zs]). %% (* powerSet : 'a list -> 'a list list %% powerSet xs = az xs halmaz hatványhalmaza *) %% fun powerSet xs = pws(xs, []) powerSet1(Xs) -> pws(Xs,[]). %% (* insAll : 'a * 'a list list * 'a list list -> 'a list list %% insAll(x, yss, zss) = az yss lista ys elemeinek zss elé fűzött %% listája, amelyben minden ys elem elé x van beszúrva *) %% fun insAll (x, [], zss) = zss %% | insAll (x, ys::yss, zss) = insAll(x, yss, (x::ys)::zss) insAll(_X,[],Zss) -> Zss; insAll(X,[Ys|Yss],Zss) -> insAll(X,Yss,[[X|Ys]|Zss]). %% lineáris-rekurzív processzt előállító változat %% fun powerSet [] = [[]] %% | powerSet (x::xs) = let val pws = powerSet xs %% in pws @ insAll(x, pws, []) end powerSet21([]) -> [[]]; powerSet21([X|Xs]) -> Pws = powerSet21(Xs), Pws ++ insAll(X,Pws,[]). %% lineáris-iteratív processzt előállító változat %% fun powerSet [] = [[]] %% | powerSet (x::xs) = let val pws = powerSet xs %% in insAll(x, pws, pws) end powerSet22([]) -> [[]]; powerSet22([X|Xs]) -> Pws = powerSet22(Xs), insAll(X,Pws,Pws). %%% Példák t1(0) -> isMember(f,[1,5,g,v,6,7,d,c,y,q,w,",","=",alma,f,akna]); t1(1) -> isMember2(a,[1,5,g,v,6,7,d,c,y,q,w,",","=",alma,akna]); t1(2) -> newMember(5,[0,2,4,6,8]); t1(3) -> newMember(5,[1,3,5,7,9]); t1(4) -> listToSet([1,2,3,4,5,6,7,8,9,8,6,4]); t1(5) -> union([6,4,2],[9,7,3,5]); t1(6) -> union([7,6,4,3,2],[9,7,3,5,6]); t1(7) -> intersect([6,4,2],[9,7,3,5]); t1(8) -> intersect([7,6,4,3,2],[9,7,3,5,6]); t1(9) -> intersect2([6,4,2],[9,7,3,5]); t1(10) -> intersect2([7,6,4,3,2],[9,7,3,5,6]); t1(11) -> isSubset([2,7,6,3],[9,7,3,5,6]); t1(12) -> isSubset([7,6,3],[9,7,3,5,6]); t1(13) -> isSubset([9,7,3,5,6],[7,6,3]); t1(14) -> isEqual([7,6,3],[6,3,7]); t1(15) -> isEqual([7,6,3],[7,6,3]); t1(16) -> isEqual([7,6,3],[7,6,3,0]). tp(0) -> powerSet1([1,2,3]); tp(1) -> powerSet21([1,2,3]); tp(2) -> powerSet22([1,2,3]); tp(10) -> powerSet1([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,19,20]); tp(11) -> powerSet1([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,19,20,21,22]); tp(12) -> powerSet21([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,19,20,21,22]); tp(13) -> powerSet22([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,19,20,21,22]).