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]

Leave a Reply