haskell - 为什么 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应该给它比列表版本更快的速度。