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

有趣的是，前几天我实际上在 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 应该会比列表版本提高速度。