почему 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 fast union должен дать ему ускорение по сравнению со списком версий.