Power set: Difference between revisions
Content added Content deleted
(Added Oz solution.) |
|||
Line 633: | Line 633: | ||
version for lists: |
version for lists: |
||
<lang ocaml>let subsets xs = List.fold_right (fun x rest -> rest @ List.map (fun ys -> x::ys) rest) xs [[]]</lang> |
<lang ocaml>let subsets xs = List.fold_right (fun x rest -> rest @ List.map (fun ys -> x::ys) rest) xs [[]]</lang> |
||
=={{header|Oz}}== |
|||
Oz has a library for finite set constraints. Creating a power set is a trivial application of that: |
|||
<lang oz>declare |
|||
%% Given a set as a list, returns its powerset (again as a list) |
|||
fun {Powerset Set} |
|||
proc {Describe Root} |
|||
%% Describe sets by lower bound (nil) and upper bound (Set) |
|||
Root = {FS.var.bounds nil Set} |
|||
%% enumerate all possible sets |
|||
{FS.distribute naive [Root]} |
|||
end |
|||
AllSets = {SearchAll Describe} |
|||
in |
|||
%% convert to list representation |
|||
{Map AllSets FS.reflect.lowerBoundList} |
|||
end |
|||
in |
|||
{Inspect {Powerset [1 2 3 4]}}</lang> |
|||
A more convential implementation without finite set constaints: |
|||
<lang oz>fun {Powerset2 Set} |
|||
case Set of nil then [nil] |
|||
[] H|T then |
|||
Acc = {Powerset2 T} |
|||
in |
|||
{Append Acc {Map Acc fun {$ A} H|A end}} |
|||
end |
|||
end</lang> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |