为什么Data.Set没有powerset功能？

Question

我在看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)什么？

Answer 1

有趣的是,我实际上是powerset在Haskell中实现的,只是为了在/ 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应该比列表版本提速.