我查看了Data.Set
,发现它没有powerset
函数。为什么?
我可以这样实现:
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)
但这似乎不是最有效的方法。好的,我也可以写
powerList :: [a] -> [[a]]
powerList = filterM (const [True, False])
但我还是想知道为什么Data.Set
没有powerset
函数。
此外,powerset::(Ord a) => Set a -> Set (Set a)
的最佳编写方式是什么?
最佳答案
有趣的是,前几天我实际上在 Haskell 中实现了 powerset
只是为了好玩 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
这很像 camccann 在上面的评论中所描述的那样。 Set
的快速 union
应该会比列表版本提高速度。
关于haskell - 为什么Data.Set没有powerset函数?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6428279/