Power set

The power set of S is the set of all subsets of S.
There will be total 2n sets where n is the number element of S.
For example, the set S={a,b,c}, we could use all 3 bits value to find the power set.

000 {} == {} union {}
001 {c} == {} union {c}
010 {b} == {} union {b}
011 {b,c}  == {} union {b,c}
100 {a} == {a} union {}
101 {a,c} == {a} union {c}
110 {a,b} == {a} union {b}
111 {a,b,c} == {a} union {b,c}

By using this hint (the color red represents power set of {b,c}), the power set function can be defined as:


powerset :: [a] -> [[a]]
powerset []     = [[]]
powerset (x:xs) = powerset xs ++ map (x:) (powerset xs)
-- powerset (x:xs) = powerset xs ++ [x:xs' | xs' <- powerset xs]

2 Responses to “Power set”

  1. MAKOUR Says:

    thank you, but i need to define powerset by comprehension so i can declare
    x=powerset [1..] or powerset [1,3..]

    i tried with pow A=[B| subset B A==True]
    but it didn’t work

  2. admin Says:

    Hmm… I didn’t expect that use powerset in such condition.

    Well, you can take a look about the implementation of
    Data.List.subsequences.

    In fact, subsequences function “is” powerset and can apply with [1..].

Leave a Reply