Add powerSet to Data.Set
[packages/containers.git] / Data / Set.hs
index 9a32f16..bf19d2a 100644 (file)
@@ -2,13 +2,15 @@
 #if !defined(TESTING) && __GLASGOW_HASKELL__ >= 703
 {-# LANGUAGE Safe #-}
 #endif
+
+#include "containers.h"
+
 -----------------------------------------------------------------------------
 -- |
 -- Module      :  Data.Set
 -- 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
 -- when equality is an equivalence relation instead of structural
 -- equality.
+--
+-- /Warning/: The size of the set must not exceed @maxBound::Int@. Violation of
+-- this condition is not detected and if the size limit is exceeded, its
+-- behaviour is undefined.
 -----------------------------------------------------------------------------
 
 module Data.Set (
@@ -68,6 +80,7 @@ module Data.Set (
             , singleton
             , insert
             , delete
+            , powerSet
 
             -- * Combine
             , union
@@ -77,9 +90,22 @@ module Data.Set (
 
             -- * Filter
             , S.filter
+            , takeWhileAntitone
+            , dropWhileAntitone
+            , spanAntitone
             , partition
             , split
             , splitMember
+            , splitRoot
+
+            -- * Indexed
+            , lookupIndex
+            , findIndex
+            , elemAt
+            , deleteAt
+            , S.take
+            , S.drop
+            , S.splitAt
 
             -- * Map
             , S.map
@@ -95,6 +121,8 @@ module Data.Set (
             , fold
 
             -- * Min\/Max
+            , lookupMin
+            , lookupMax
             , findMin
             , findMax
             , deleteMin
@@ -115,7 +143,9 @@ module Data.Set (
             , toAscList
             , toDescList
             , fromAscList
+            , fromDescList
             , fromDistinctAscList
+            , fromDistinctDescList
 
             -- * Debugging
             , showTree
@@ -126,12 +156,12 @@ module Data.Set (
             -- Internals (for testing)
             , bin
             , balanced
-            , join
+            , link
             , merge
 #endif
             ) where
 
-import Data.Set.Base as S
+import Data.Set.Internal as S
 
 -- $strictness
 --