I was looking at Data.Set
, and I found out that it has no powerset
function. Why?
I can implement it like this:
import Data.Set (Set, empty, fromList, toList, insert)
powerset :: (Ord a) => Set a -> Set (Set a)
powerset s = fromList $ map (fromList) (powerList $ toList s)
powerList :: [a] -> [[a]]
powerList [] = [[]]
powerList (x:xs) = powerList xs ++ map (x:) (powerList xs)
But this doesn't seem the most efficient way of doing it. OK, I can also write
powerList :: [a] -> [[a]]
powerList = filterM (const [True, False])
but still, I wonder why Data.Set
has no powerset
function.
Also, what is the best way to write powerset :: (Ord a) => Set a -> Set (Set a)
?
Funny, I actually implemented powerset
in Haskell the other day just for fun in a comment at /r/python.
import Data.Set
import Prelude hiding (map)
powerset s
| s == empty = singleton empty
| otherwise = map (insert x) pxs `union` pxs
where (x, xs) = deleteFindMin s
pxs = powerset xs
It is much as camccann described in his comment above. Set
's fast union
should give it a speed boost over the list version.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With