Add powerSet to Data.Set
authorEdward Kmett <ekmett@gmail.com>
Wed, 3 Jan 2018 21:10:55 +0000 (16:10 -0500)
committerDavid Feuer <David.Feuer@gmail.com>
Thu, 4 Jan 2018 07:38:09 +0000 (02:38 -0500)
This should be considerably more efficient than what can be written
using the public API because it can glue trees together without
needing to perform a full divide-and-conquer union.

Addresses #442

Data/Set.hs
Data/Set/Internal.hs
changelog.md

index 2608785..bf19d2a 100644 (file)
@@ -80,6 +80,7 @@ module Data.Set (
             , singleton
             , insert
             , delete
+            , powerSet
 
             -- * Combine
             , union
index a5cf9b8..4dd5341 100644 (file)
@@ -145,6 +145,7 @@ module Data.Set.Internal (
             , singleton
             , insert
             , delete
+            , powerSet
 
             -- * Combine
             , union
@@ -246,7 +247,8 @@ import GHC.Exts ( build, lazy )
 #if __GLASGOW_HASKELL__ >= 708
 import qualified GHC.Exts as GHCExts
 #endif
-import Text.Read
+import Text.Read ( readPrec, Read (..), Lexeme (..), parens, prec
+                 , lexP, readListPrecDefault )
 import Data.Data
 #endif
 
@@ -1661,6 +1663,17 @@ splitRoot orig =
 {-# INLINE splitRoot #-}
 
 
+-- | Calculate the power set of a set: the set of all its subsets.
+--
+-- @
+-- t `member` powerSet s == t `isSubsetOf` s
+-- @
+--
+-- @since 0.5.11
+powerSet :: Set a -> Set (Set a)
+powerSet xs0 = insertMin empty (foldr' step Tip xs0) where
+  step x pxs = insertMin (singleton x) (insertMin x `mapMonotonic` pxs) `glue` pxs
+
 {--------------------------------------------------------------------
   Debugging
 --------------------------------------------------------------------}
index d86d351..b7d06f4 100644 (file)
@@ -9,6 +9,8 @@
 
 * Add a `MonadFix` instance for `Data.Tree`.
 
+* Add `powerSet` for `Data.Set` (Thanks, Edward Kmett!)
+
 * Make `>>=` for `Data.Tree` strict in the result of its second argument;
   being too lazy here is almost useless, and violates one of the monad identity
   laws. Specifically, `return () >>= \_ -> undefined` should always be