Copyright  (c) Justin Le 2018 

License  BSD3 
Maintainer  justin@jle.im 
Stability  experimental 
Portability  nonportable 
Safe Haskell  None 
Language  Haskell2010 
Unsafe internaluse functions used in the implementation of
Data.Set.NonEmpty. These functions can potentially be used to break
the abstraction of NESet
and produce unsound sets, so be wary!
Synopsis
 data NESet a = NESet {}
 nonEmptySet :: Set a > Maybe (NESet a)
 withNonEmpty :: r > (NESet a > r) > Set a > r
 toSet :: NESet a > Set a
 singleton :: a > NESet a
 fromList :: Ord a => NonEmpty a > NESet a
 toList :: NESet a > NonEmpty a
 size :: NESet a > Int
 union :: Ord a => NESet a > NESet a > NESet a
 unions :: (Foldable1 f, Ord a) => f (NESet a) > NESet a
 foldr :: (a > b > b) > b > NESet a > b
 foldl :: (a > b > a) > a > NESet b > a
 foldr' :: (a > b > b) > b > NESet a > b
 foldl' :: (a > b > a) > a > NESet b > a
 newtype MergeNESet a = MergeNESet {
 getMergeNESet :: NESet a
 merge :: NESet a > NESet a > NESet a
 valid :: Ord a => NESet a > Bool
 insertMinSet :: a > Set a > Set a
 insertMaxSet :: a > Set a > Set a
 disjointSet :: Ord a => Set a > Set a > Bool
 powerSetSet :: Set a > Set (Set a)
 disjointUnionSet :: Set a > Set b > Set (Either a b)
 cartesianProductSet :: Set a > Set b > Set (a, b)
Documentation
A nonempty (by construction) set of values a
. At least one value
exists in an
at all times.NESet
a
Functions that take an NESet
can safely operate on it with the
assumption that it has at least one item.
Functions that return an NESet
provide an assurance that the result
has at least one item.
Data.Set.NonEmpty reexports the API of Data.Set, faithfully
reproducing asymptotics, typeclass constraints, and semantics.
Functions that ensure that input and output sets are both nonempty
(like insert
) return NESet
, but functions that
might potentially return an empty map (like delete
)
return a Set
instead.
You can directly construct an NESet
with the API from
Data.Set.NonEmpty; it's more or less the same as constructing a normal
Set
, except you don't have access to empty
. There are also
a few ways to construct an NESet
from a Set
:
 The
nonEmptySet
smart constructor will convert a
into aSet
a
, returningMaybe
(NESet
a)Nothing
if the originalSet
was empty.  You can use the
insertSet
family of functions to insert a value into aSet
to create a guaranteedNESet
.  You can use the
IsNonEmpty
andIsEmpty
patterns to "pattern match" on aSet
to reveal it as either containing aNESet
or an empty map. withNonEmpty
offers a continuationbased interface for deconstructing aSet
and treating it as if it were anNESet
.
You can convert an NESet
into a Set
with toSet
or
IsNonEmpty
, essentially "obscuring" the nonempty
property from the type.
Instances
Foldable NESet Source #  Traverses elements in ascending order 
Defined in Data.Set.NonEmpty.Internal fold :: Monoid m => NESet m > m # foldMap :: Monoid m => (a > m) > NESet a > m # foldMap' :: Monoid m => (a > m) > NESet a > m # foldr :: (a > b > b) > b > NESet a > b # foldr' :: (a > b > b) > b > NESet a > b # foldl :: (b > a > b) > b > NESet a > b # foldl' :: (b > a > b) > b > NESet a > b # foldr1 :: (a > a > a) > NESet a > a # foldl1 :: (a > a > a) > NESet a > a # elem :: Eq a => a > NESet a > Bool # maximum :: Ord a => NESet a > a # minimum :: Ord a => NESet a > a #  
Eq1 NESet Source #  
Ord1 NESet Source #  
Defined in Data.Set.NonEmpty.Internal  
Show1 NESet Source #  
Foldable1 NESet Source #  Traverses elements in ascending order 
Defined in Data.Set.NonEmpty.Internal  
Eq a => Eq (NESet a) Source #  
(Data a, Ord a) => Data (NESet a) Source #  
Defined in Data.Set.NonEmpty.Internal gfoldl :: (forall d b. Data d => c (d > b) > d > c b) > (forall g. g > c g) > NESet a > c (NESet a) # gunfold :: (forall b r. Data b => c (b > r) > c r) > (forall r. r > c r) > Constr > c (NESet a) # toConstr :: NESet a > Constr # dataTypeOf :: NESet a > DataType # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) > Maybe (c (NESet a)) # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) > Maybe (c (NESet a)) # gmapT :: (forall b. Data b => b > b) > NESet a > NESet a # gmapQl :: (r > r' > r) > r > (forall d. Data d => d > r') > NESet a > r # gmapQr :: forall r r'. (r' > r > r) > r > (forall d. Data d => d > r') > NESet a > r # gmapQ :: (forall d. Data d => d > u) > NESet a > [u] # gmapQi :: Int > (forall d. Data d => d > u) > NESet a > u # gmapM :: Monad m => (forall d. Data d => d > m d) > NESet a > m (NESet a) # gmapMp :: MonadPlus m => (forall d. Data d => d > m d) > NESet a > m (NESet a) # gmapMo :: MonadPlus m => (forall d. Data d => d > m d) > NESet a > m (NESet a) #  
Ord a => Ord (NESet a) Source #  
(Read a, Ord a) => Read (NESet a) Source #  
Show a => Show (NESet a) Source #  
Ord a => Semigroup (NESet a) Source #  Leftbiased union 
NFData a => NFData (NESet a) Source #  
Defined in Data.Set.NonEmpty.Internal  
(FromJSON a, Ord a) => FromJSON (NESet a) Source #  
Defined in Data.Set.NonEmpty.Internal parseJSON :: Value > Parser (NESet a) parseJSONList :: Value > Parser [NESet a]  
ToJSON a => ToJSON (NESet a) Source #  
Defined in Data.Set.NonEmpty.Internal toEncoding :: NESet a > Encoding toJSONList :: [NESet a] > Value toEncodingList :: [NESet a] > Encoding 
nonEmptySet :: Set a > Maybe (NESet a) Source #
O(log n). Smart constructor for an NESet
from a Set
. Returns
Nothing
if the Set
was originally actually empty, and
with an Just
nNESet
, if the Set
was not empty.
nonEmptySet
and
form an
isomorphism: they are perfect structurepreserving inverses of
eachother.maybe
empty
toSet
See IsNonEmpty
for a pattern synonym that lets you
"match on" the possiblity of a Set
being an NESet
.
nonEmptySet (Data.Set.fromList [3,5]) == Just (fromList (3:[5]))
:: r  value to return if set is empty 
> (NESet a > r)  function to apply if set is not empty 
> Set a  
> r 
O(log n). A general continuationbased way to consume a Set
as if
it were an NESet
.
will take a withNonEmpty
def fSet
. If set is
empty, it will evaluate to def
. Otherwise, a nonempty set NESet
will be fed to the function f
instead.
nonEmptySet
==withNonEmpty
Nothing
Just
toSet :: NESet a > Set a Source #
O(log n).
Convert a nonempty set back into a normal possiblyempty map, for usage
with functions that expect Set
.
Can be thought of as "obscuring" the nonemptiness of the set in its
type. See the IsNotEmpty
pattern.
nonEmptySet
and
form an
isomorphism: they are perfect structurepreserving inverses of
eachother.maybe
empty
toSet
toSet (fromList ((3,"a") : [(5,"b")])) == Data.Set.fromList [(3,"a"), (5,"b")]
fromList :: Ord a => NonEmpty a > NESet a Source #
O(n*log n). Create a set from a list of elements.
size :: NESet a > Int Source #
O(1). The number of elements in the set. Guaranteed to be greater than zero.
union :: Ord a => NESet a > NESet a > NESet a Source #
O(m*log(n/m + 1)), m <= n. The union of two sets, preferring the first set when equal elements are encountered.
unions :: (Foldable1 f, Ord a) => f (NESet a) > NESet a Source #
The union of a nonempty list of sets
foldr' :: (a > b > b) > b > NESet a > b Source #
O(n). A strict version of foldr
. Each application of the operator is
evaluated before using the result in the next application. This
function is strict in the starting value.
foldl' :: (a > b > a) > a > NESet b > a Source #
O(n). A strict version of foldl
. Each application of the operator is
evaluated before using the result in the next application. This
function is strict in the starting value.
newtype MergeNESet a Source #
Used for cartesianProduct
MergeNESet  

Instances
Semigroup (MergeNESet a) Source #  
Defined in Data.Set.NonEmpty.Internal (<>) :: MergeNESet a > MergeNESet a > MergeNESet a # sconcat :: NonEmpty (MergeNESet a) > MergeNESet a # stimes :: Integral b => b > MergeNESet a > MergeNESet a # 
merge :: NESet a > NESet a > NESet a Source #
Unsafely merge two disjoint sets. Only legal if all items in the first set are less than all items in the second set
insertMinSet :: a > Set a > Set a Source #
O(log n). Insert new value into a set where values are
strictly greater than the new values That is, the new value must be
strictly less than all values present in the Set
. /The precondition
is not checked./
While this has the same asymptotics as Data.Set.insert
, it saves
a constant factor for value comparison (so may be helpful if comparison
is expensive) and also does not require an Ord
instance for the value
type.
insertMaxSet :: a > Set a > Set a Source #
O(log n). Insert new value into a set where values are /strictly
less than the new value. That is, the new value must be strictly
greater than all values present in the Set
. The precondition is not
checked./
While this has the same asymptotics as Data.Set.insert
, it saves
a constant factor for value comparison (so may be helpful if comparison
is expensive) and also does not require an Ord
instance for the value
type.
disjointSet :: Ord a => Set a > Set a > Bool Source #
CPP for new functions not in old containers 
Comptability layer for disjoint
.
disjointUnionSet :: Set a > Set b > Set (Either a b) Source #
Comptability layer for disjointUnion
.
cartesianProductSet :: Set a > Set b > Set (a, b) Source #
Comptability layer for cartesianProduct
.