Haskell – Finding Power Set of a Set without using set functions

There are several built-in set functions that might help in finding the power set of a given set. But if the use of those build-in sets functions is prohibited as per the requirement, it can be implemented differently. The following code shows one of such ways to get the power set of a given set.

powerSet :: [Integer] -> [[Integer]]
powerSet [] = [[]]
powerSet xs = getSet (quicksort xs)

getSet :: [Integer] -> [[Integer]]
getSet [] = [[]]
getSet (x:xs) = map (x:) (getSet xs) ++ getSet xs 

quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort(e:es) = quicksort smaller ++ [e] ++ quicksort bigger
    where bigger = [b | b <- es, b>e]		
          smaller = [a | a <- es, a<e]

The output of the above code looks like this…

*Main> powerSet [1,2,3]
[[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]

Similar Posts

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.