A   set   is a collection (container) of certain values,
without any particular order, and no repeated values.

It corresponds with a finite set in mathematics.

A set can be implemented as an associative array (partial mapping)
in which the value of each key-value pair is ignored.

Given a set S, the power set (or powerset) of S, written P(S), or 2S, is the set of all subsets of S.



Task

By using a library or built-in set type, or by defining a set type with necessary operations, write a function with a set S as input that yields the power set 2S of S.



For example, the power set of     {1,2,3,4}     is

 {{}, {1}, {2}, {1,2}, {3}, {1,3}, {2,3}, {1,2,3}, {4}, {1,4}, {2,4}, {1,2,4}, {3,4}, {1,3,4}, {2,3,4}, {1,2,3,4}}.
For a set which contains n elements, the corresponding power set has 2n elements, including the edge cases of empty set.


The power set of the empty set is the set which contains itself (20 = 1):


 





P




{\displaystyle {\mathcal {P}}}

(



∅


{\displaystyle \varnothing }

) = { 



∅


{\displaystyle \varnothing }

 }

And the power set of the set which contains only the empty set, has two subsets, the empty set and the set which contains the empty set (21 = 2):


 





P




{\displaystyle {\mathcal {P}}}

({



∅


{\displaystyle \varnothing }

}) = { 



∅


{\displaystyle \varnothing }

, { 



∅


{\displaystyle \varnothing }

 } }


Extra credit:  Demonstrate that your language supports these last two powersets.




 
(* ****** ****** *)
//
#include
"share/atspre_define.hats" // defines some names
#include
"share/atspre_staload.hats" // for targeting C
#include
"share/HATS/atspre_staload_libats_ML.hats" // for ...
//
(* ****** ****** *)
//
extern
fun
Power_set(xs: list0(int)): void
//
(* ****** ****** *)
 
// Helper: fast power function.
fun power(n: int, p: int): int =
	if p = 1 then n
	else if p = 0 then 1
	else if p % 2 = 0 then power(n*n, p/2)
	else n * power(n, p-1)
 
fun print_list(list: list0(int)): void =
  case+ list of
  | nil0() => println!(" ")
  | cons0(car, crd) =>
    let
      val () = begin print car; print ','; end
      val () = print_list(crd)
    in
    end
 
fun get_list_length(list: list0(int), length: int): int =
  case+ list of
  | nil0() => length
  | cons0(car, crd) => get_list_length(crd, length+1)
 
 
fun get_list_from_bit_mask(mask: int, list: list0(int), result: list0(int)): list0(int) =
  if mask = 0 then result
  else
    case+ list of
    | nil0() => result
    | cons0(car, crd) =>
      let
        val current: int = mask % 2
      in
        if current = 0 then
          get_list_from_bit_mask(mask >> 1, crd, result)
        else
          get_list_from_bit_mask(mask >> 1, crd, list0_cons(car, result))
      end
 
 
implement
Power_set(xs) = let
  val len: int = get_list_length(xs, 0)
  val pow: int = power(2, len)
  fun loop(mask: int, list: list0(int)): void =
    if mask > 0 && mask >= pow then ()
    else
      let
        val () = print_list(get_list_from_bit_mask(mask, list, list0_nil()))
      in
        loop(mask+1, list)
      end
  in
    loop(0, xs)
  end
 
(* ****** ****** *)
 
implement
main0() =
let
  val xs: list0(int) = cons0(1, list0_pair(2, 3))
in
  Power_set(xs)
end (* end of [main0] *)
 
(* ****** ****** *)
 