Add powerSet to Data.Set
[packages/containers.git] / Data / Set.hs
index 297cee2..bf19d2a 100644 (file)
@@ -11,7 +11,6 @@
 -- Copyright   :  (c) Daan Leijen 2002
 -- License     :  BSD-style
 -- Maintainer  :  libraries@haskell.org
--- Stability   :  provisional
 -- Portability :  portable
 --
 -- An efficient implementation of sets.
 --    * Stephen Adams, \"/Efficient sets: a balancing act/\",
 --      Journal of Functional Programming 3(4):553-562, October 1993,
 --      <http://www.swiss.ai.mit.edu/~adams/BB/>.
---
 --    * J. Nievergelt and E.M. Reingold,
 --      \"/Binary search trees of bounded balance/\",
 --      SIAM journal of computing 2(1), March 1973.
 --
+--  Bounds for 'union', 'intersection', and 'difference' are as given
+--  by
+--
+--    * Guy Blelloch, Daniel Ferizovic, and Yihan Sun,
+--      \"/Just Join for Parallel Ordered Sets/\",
+--      <https://arxiv.org/abs/1602.02120v3>.
+--
 -- Note that the implementation is /left-biased/ -- the elements of a
 -- first argument are always preferred to the second, for example in
 -- 'union' or 'insert'.  Of course, left-biasing can only be observed
@@ -75,6 +80,7 @@ module Data.Set (
             , singleton
             , insert
             , delete
+            , powerSet
 
             -- * Combine
             , union
@@ -84,6 +90,9 @@ module Data.Set (
 
             -- * Filter
             , S.filter
+            , takeWhileAntitone
+            , dropWhileAntitone
+            , spanAntitone
             , partition
             , split
             , splitMember
@@ -94,6 +103,9 @@ module Data.Set (
             , findIndex
             , elemAt
             , deleteAt
+            , S.take
+            , S.drop
+            , S.splitAt
 
             -- * Map
             , S.map
@@ -109,6 +121,8 @@ module Data.Set (
             , fold
 
             -- * Min\/Max
+            , lookupMin
+            , lookupMax
             , findMin
             , findMax
             , deleteMin
@@ -147,7 +161,7 @@ module Data.Set (
 #endif
             ) where
 
-import Data.Set.Base as S
+import Data.Set.Internal as S
 
 -- $strictness
 --