Copyright | (c) Justin Le 2018 |
---|---|

License | BSD3 |

Maintainer | justin@jle.im |

Stability | experimental |

Portability | non-portable |

Safe Haskell | None |

Language | Haskell2010 |

# Non-Empty Finite Sets

The

type represents a non-empty set of elements of type `NESet`

e`e`

.
Most operations require that `e`

be an instance of the `Ord`

class.
A `NESet`

is strict in its elements.

See documentation for `NESet`

for information on how to convert and
manipulate such non-empty set.

This module essentially re-imports the API of Data.Set and its `Set`

type, along with semantics and asymptotics. In most situations,
asymptotics are different only by a constant factor. In some
situations, asmyptotics are even better (constant-time instead of
log-time). All typeclass constraints are identical to their Data.Set
counterparts.

Because `NESet`

is implemented using `Set`

, all of the caveats of using
`Set`

apply (such as the limitation of the maximum size of sets).

All functions take non-empty sets as inputs. In situations where their
results can be guarunteed to also be non-empty, they also return
non-empty sets. In situations where their results could potentially be
empty, `Set`

is returned instead.

Some functions (`partition`

, `spanAntitone`

, `split`

) have modified
return types to account for possible configurations of non-emptiness.

This module is intended to be imported qualified, to avoid name clashes with Prelude and Data.Set functions:

import qualified Data.Set.NonEmpty as NES

## Synopsis

- data NESet a
- pattern IsNonEmpty :: NESet a -> Set a
- pattern IsEmpty :: Set a
- nonEmptySet :: Set a -> Maybe (NESet a)
- toSet :: NESet a -> Set a
- withNonEmpty :: r -> (NESet a -> r) -> Set a -> r
- insertSet :: Ord a => a -> Set a -> NESet a
- insertSetMin :: a -> Set a -> NESet a
- insertSetMax :: a -> Set a -> NESet a
- unsafeFromSet :: Set a -> NESet a
- singleton :: a -> NESet a
- fromList :: Ord a => NonEmpty a -> NESet a
- fromAscList :: Eq a => NonEmpty a -> NESet a
- fromDescList :: Eq a => NonEmpty a -> NESet a
- fromDistinctAscList :: NonEmpty a -> NESet a
- fromDistinctDescList :: NonEmpty a -> NESet a
- powerSet :: forall a. NESet a -> NESet (NESet a)
- insert :: Ord a => a -> NESet a -> NESet a
- delete :: Ord a => a -> NESet a -> Set a
- member :: Ord a => a -> NESet a -> Bool
- notMember :: Ord a => a -> NESet a -> Bool
- lookupLT :: Ord a => a -> NESet a -> Maybe a
- lookupGT :: Ord a => a -> NESet a -> Maybe a
- lookupLE :: Ord a => a -> NESet a -> Maybe a
- lookupGE :: Ord a => a -> NESet a -> Maybe a
- size :: NESet a -> Int
- isSubsetOf :: Ord a => NESet a -> NESet a -> Bool
- isProperSubsetOf :: Ord a => NESet a -> NESet a -> Bool
- disjoint :: Ord a => NESet a -> NESet a -> Bool
- union :: Ord a => NESet a -> NESet a -> NESet a
- unions :: (Foldable1 f, Ord a) => f (NESet a) -> NESet a
- difference :: Ord a => NESet a -> NESet a -> Set a
- (\\) :: Ord a => NESet a -> NESet a -> Set a
- intersection :: Ord a => NESet a -> NESet a -> Set a
- cartesianProduct :: NESet a -> NESet b -> NESet (a, b)
- disjointUnion :: NESet a -> NESet b -> NESet (Either a b)
- filter :: (a -> Bool) -> NESet a -> Set a
- takeWhileAntitone :: (a -> Bool) -> NESet a -> Set a
- dropWhileAntitone :: (a -> Bool) -> NESet a -> Set a
- spanAntitone :: (a -> Bool) -> NESet a -> These (NESet a) (NESet a)
- partition :: (a -> Bool) -> NESet a -> These (NESet a) (NESet a)
- split :: Ord a => a -> NESet a -> Maybe (These (NESet a) (NESet a))
- splitMember :: Ord a => a -> NESet a -> (Bool, Maybe (These (NESet a) (NESet a)))
- splitRoot :: NESet a -> NonEmpty (NESet a)
- lookupIndex :: Ord a => a -> NESet a -> Maybe Int
- findIndex :: Ord a => a -> NESet a -> Int
- elemAt :: Int -> NESet a -> a
- deleteAt :: Int -> NESet a -> Set a
- take :: Int -> NESet a -> Set a
- drop :: Int -> NESet a -> Set a
- splitAt :: Int -> NESet a -> These (NESet a) (NESet a)
- map :: Ord b => (a -> b) -> NESet a -> NESet b
- mapMonotonic :: (a -> b) -> NESet a -> NESet b
- foldr :: (a -> b -> b) -> b -> NESet a -> b
- foldl :: (a -> b -> a) -> a -> NESet b -> a
- foldr1 :: Foldable t => (a -> a -> a) -> t a -> a
- foldl1 :: Foldable t => (a -> a -> a) -> t a -> a
- foldr' :: (a -> b -> b) -> b -> NESet a -> b
- foldl' :: (a -> b -> a) -> a -> NESet b -> a
- foldr1' :: (a -> a -> a) -> NESet a -> a
- foldl1' :: (a -> a -> a) -> NESet a -> a
- findMin :: NESet a -> a
- findMax :: NESet a -> a
- deleteMin :: NESet a -> Set a
- deleteMax :: NESet a -> Set a
- deleteFindMin :: NESet a -> (a, Set a)
- deleteFindMax :: NESet a -> (a, Set a)
- elems :: NESet a -> NonEmpty a
- toList :: NESet a -> NonEmpty a
- toAscList :: NESet a -> NonEmpty a
- toDescList :: NESet a -> NonEmpty a
- valid :: Ord a => NESet a -> Bool

# Non-Empty Set Type

A non-empty (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 re-exports the API of Data.Set, faithfully
reproducing asymptotics, typeclass constraints, and semantics.
Functions that ensure that input and output sets are both non-empty
(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 a`Set`

a

, returning`Maybe`

(`NESet`

a)`Nothing`

if the original`Set`

was empty. - You can use the
`insertSet`

family of functions to insert a value into a`Set`

to create a guaranteed`NESet`

. - You can use the
`IsNonEmpty`

and`IsEmpty`

patterns to "pattern match" on a`Set`

to reveal it as either containing a`NESet`

or an empty map. `withNonEmpty`

offers a continuation-based interface for deconstructing a`Set`

and treating it as if it were an`NESet`

.

You can convert an `NESet`

into a `Set`

with `toSet`

or
`IsNonEmpty`

, essentially "obscuring" the non-empty
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 |

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 # | Left-biased union |

ToJSON a => ToJSON (NESet a) Source # | |

Defined in Data.Set.NonEmpty.Internal | |

(FromJSON a, Ord a) => FromJSON (NESet a) Source # | |

NFData a => NFData (NESet a) Source # | |

Defined in Data.Set.NonEmpty.Internal |

## Conversions between empty and non-empty sets

pattern IsNonEmpty :: NESet a -> Set a Source #

*O(1)* match, *O(log n)* usage of contents. The `IsNonEmpty`

and
`IsEmpty`

patterns allow you to treat a `Set`

as if it were either
a

(where `IsNonEmpty`

n`n`

is a `NESet`

) or an `IsEmpty`

.

For example, you can pattern match on a `Set`

:

myFunc ::`Set`

X -> Y myFunc (`IsNonEmpty`

n) = -- here, the user provided a non-empty set, and`n`

is the`NESet`

myFunc`IsEmpty`

= -- here, the user provided an empty set

Matching on

means that the original `IsNonEmpty`

n`Set`

was *not*
empty, and you have a verified-non-empty `NESet`

`n`

to use.

Note that patching on this pattern is *O(1)*. However, using the
contents requires a *O(log n)* cost that is deferred until after the
pattern is matched on (and is not incurred at all if the contents are
never used).

A case statement handling both `IsNonEmpty`

and `IsEmpty`

provides
complete coverage.

This is a bidirectional pattern, so you can use `IsNonEmpty`

to convert
a `NESet`

back into a `Set`

, obscuring its non-emptiness (see `toSet`

).

pattern IsEmpty :: Set a Source #

*O(1)*. The `IsNonEmpty`

and `IsEmpty`

patterns allow you to treat
a `Set`

as if it were either a

(where `IsNonEmpty`

n`n`

is
a `NESet`

) or an `IsEmpty`

.

Matching on `IsEmpty`

means that the original `Set`

was empty.

A case statement handling both `IsNonEmpty`

and `IsEmpty`

provides
complete coverage.

This is a bidirectional pattern, so you can use `IsEmpty`

as an
expression, and it will be interpreted as `empty`

.

See `IsNonEmpty`

for more information.

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`

n`NESet`

, if the `Set`

was not empty.

`nonEmptySet`

and

form an
isomorphism: they are perfect structure-preserving 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]))

toSet :: NESet a -> Set a Source #

*O(log n)*.
Convert a non-empty set back into a normal possibly-empty map, for usage
with functions that expect `Set`

.

Can be thought of as "obscuring" the non-emptiness of the set in its
type. See the `IsNotEmpty`

pattern.

`nonEmptySet`

and

form an
isomorphism: they are perfect structure-preserving inverses of
eachother.`maybe`

`empty`

`toSet`

toSet (fromList ((3,"a") :| [(5,"b")])) == Data.Set.fromList [(3,"a"), (5,"b")]

:: 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 continuation-based way to consume a `Set`

as if
it were an `NESet`

.

will take a `withNonEmpty`

def f`Set`

. If set is
empty, it will evaluate to `def`

. Otherwise, a non-empty set `NESet`

will be fed to the function `f`

instead.

`nonEmptySet`

==`withNonEmpty`

`Nothing`

`Just`

insertSet :: Ord a => a -> Set a -> NESet a Source #

*O(log n)*. Convert a `Set`

into an `NESet`

by adding a value.
Because of this, we know that the set must have at least one
element, and so therefore cannot be empty.

See `insertSetMin`

for a version that is constant-time if the new value is
*strictly smaller than* all values in the original set

insertSet 4 (Data.Set.fromList [5, 3]) == fromList (3 :| [4, 5]) insertSet 4 Data.Set.empty == singleton 4 "c"

insertSetMin :: a -> Set a -> NESet a Source #

*O(1)* Convert a `Set`

into an `NESet`

by adding a value where the
value is *strictly less than* all values in the input set The values in
the original map must all be *strictly greater than* the new value.
*The precondition is not checked.*

insertSetMin 2 (Data.Set.fromList [5, 3]) == fromList (2 :| [3, 5]) valid (insertSetMin 2 (Data.Set.fromList [5, 3])) == True valid (insertSetMin 7 (Data.Set.fromList [5, 3])) == False valid (insertSetMin 3 (Data.Set.fromList [5, 3])) == False

insertSetMax :: a -> Set a -> NESet a Source #

*O(log n)* Convert a `Set`

into an `NESet`

by adding a value where the
value is *strictly less than* all values in the input set The values in
the original map must all be *strictly greater than* the new value.
*The precondition is not checked.*

While this has the same asymptotics as `insertSet`

, it saves a constant
factor for key comparison (so may be helpful if comparison is expensive)
and also does not require an `Ord`

instance for the key type.

insertSetMin 7 (Data.Set.fromList [5, 3]) == fromList (3 :| [5, 7]) valid (insertSetMin 7 (Data.Set.fromList [5, 3])) == True valid (insertSetMin 2 (Data.Set.fromList [5, 3])) == False valid (insertSetMin 5 (Data.Set.fromList [5, 3])) == False

unsafeFromSet :: Set a -> NESet a Source #

*O(log n)*. Unsafe version of `nonEmptySet`

. Coerces a `Set`

into an
`NESet`

, but is undefined (throws a runtime exception when evaluation is
attempted) for an empty `Set`

.

# Construction

fromList :: Ord a => NonEmpty a -> NESet a Source #

*O(n*log n)*. Create a set from a list of elements.

fromAscList :: Eq a => NonEmpty a -> NESet a Source #

*O(n)*. Build a set from an ascending list in linear time. /The
precondition (input list is ascending) is not checked./

fromDescList :: Eq a => NonEmpty a -> NESet a Source #

*O(n)*. Build a set from a descending list in linear time.
*The precondition (input list is descending) is not checked.*

fromDistinctAscList :: NonEmpty a -> NESet a Source #

*O(n)*. Build a set from an ascending list of distinct elements in linear time.
*The precondition (input list is strictly ascending) is not checked.*

fromDistinctDescList :: NonEmpty a -> NESet a Source #

*O(n)*. Build a set from a descending list of distinct elements in linear time.
*The precondition (input list is strictly descending) is not checked.*

powerSet :: forall a. NESet a -> NESet (NESet a) Source #

Calculate the power set of a non-empty: the set of all its (non-empty) subsets.

t``member``

powerSet s == t``isSubsetOf``

s

Example:

powerSet (fromList (1 :| [2,3])) = fromList (singleton 1 :| [ singleton 2 , singleton 3 , fromList (1 :| [2]) , fromList (1 :| [3]) , fromList (2 :| [3]) , fromList (1 :| [2,3]) ] )

We know that the result is non-empty because the result will always at least contain the original set.

# Insertion

insert :: Ord a => a -> NESet a -> NESet a Source #

*O(log n)*. Insert an element in a set.
If the set already contains an element equal to the given value,
it is replaced with the new value.

# Deletion

# Query

lookupLT :: Ord a => a -> NESet a -> Maybe a Source #

*O(log n)*. Find largest element smaller than the given one.

lookupLT 3 (fromList (3 :| [5])) == Nothing lookupLT 5 (fromList (3 :| [5])) == Just 3

lookupGT :: Ord a => a -> NESet a -> Maybe a Source #

*O(log n)*. Find smallest element greater than the given one.

lookupLT 4 (fromList (3 :| [5])) == Just 5 lookupLT 5 (fromList (3 :| [5])) == Nothing

lookupLE :: Ord a => a -> NESet a -> Maybe a Source #

*O(log n)*. Find largest element smaller or equal to the given one.

lookupLT 2 (fromList (3 :| [5])) == Nothing lookupLT 4 (fromList (3 :| [5])) == Just 3 lookupLT 5 (fromList (3 :| [5])) == Just 5

lookupGE :: Ord a => a -> NESet a -> Maybe a Source #

*O(log n)*. Find smallest element greater or equal to the given one.

lookupLT 3 (fromList (3 :| [5])) == Just 3 lookupLT 4 (fromList (3 :| [5])) == Just 5 lookupLT 6 (fromList (3 :| [5])) == Nothing

size :: NESet a -> Int Source #

*O(1)*. The number of elements in the set. Guaranteed to be greater
than zero.

isSubsetOf :: Ord a => NESet a -> NESet a -> Bool Source #

*O(n+m)*. Is this a subset?
`(s1 `isSubsetOf` s2)`

tells whether `s1`

is a subset of `s2`

.

isProperSubsetOf :: Ord a => NESet a -> NESet a -> Bool Source #

*O(n+m)*. Is this a proper subset? (ie. a subset but not equal).

disjoint :: Ord a => NESet a -> NESet a -> Bool Source #

*O(n+m)*. Check whether two sets are disjoint (i.e. their intersection
is empty).

disjoint (fromList (2:|[4,6])) (fromList (1:|[3])) == True disjoint (fromList (2:|[4,6,8])) (fromList (2:|[3,5,7])) == False disjoint (fromList (1:|[2])) (fromList (1:|[2,3,4])) == False

# Combine

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 non-empty list of sets

difference :: Ord a => NESet a -> NESet a -> Set a Source #

*O(m*log(n/m + 1)), m <= n*. Difference of two sets.

Returns a potentially empty set (`Set`

) because the first set might be
a subset of the second set, and therefore have all of its elements
removed.

intersection :: Ord a => NESet a -> NESet a -> Set a Source #

*O(m*log(n/m + 1)), m <= n*. The intersection of two sets.

Returns a potentially empty set (`Set`

), because the two sets might have
an empty intersection.

Elements of the result come from the first set, so for example

import qualified Data.Set.NonEmpty as NES data AB = A | B deriving Show instance Ord AB where compare _ _ = EQ instance Eq AB where _ == _ = True main = print (NES.singleton A `NES.intersection` NES.singleton B, NES.singleton B `NES.intersection` NES.singleton A)

prints `(fromList (A:|[]),fromList (B:|[]))`

.

cartesianProduct :: NESet a -> NESet b -> NESet (a, b) Source #

Calculate the Cartesian product of two sets.

cartesianProduct xs ys = fromList $ liftA2 (,) (toList xs) (toList ys)

Example:

cartesianProduct (fromList (1:|[2])) (fromList ('a':|['b'])) = fromList ((1,'a') :| [(1,'b'), (2,'a'), (2,'b')])

disjointUnion :: NESet a -> NESet b -> NESet (Either a b) Source #

Calculate the disjoint union of two sets.

` disjointUnion xs ys = map Left xs ```union``

map Right ys

Example:

disjointUnion (fromList (1:|[2])) (fromList ("hi":|["bye"])) = fromList (Left 1 :| [Left 2, Right "hi", Right "bye"])

# Filter

filter :: (a -> Bool) -> NESet a -> Set a Source #

*O(n)*. Filter all elements that satisfy the predicate.

Returns a potentially empty set (`Set`

) because the predicate might
filter out all items in the original non-empty set.

takeWhileAntitone :: (a -> Bool) -> NESet a -> Set a Source #

*O(log n)*. Take while a predicate on the elements holds. The user is
responsible for ensuring that for all elements `j`

and `k`

in the set,
`j < k ==> p j >= p k`

. See note at `spanAntitone`

.

Returns a potentially empty set (`Set`

) because the predicate might fail
on the first input.

takeWhileAntitone p = Data.Set.fromDistinctAscList . Data.List.NonEmpty.takeWhile p .`toList`

takeWhileAntitone p =`filter`

p

dropWhileAntitone :: (a -> Bool) -> NESet a -> Set a Source #

*O(log n)*. Drop while a predicate on the elements holds. The user is
responsible for ensuring that for all elements `j`

and `k`

in the set,
`j < k ==> p j >= p k`

. See note at `spanAntitone`

.

Returns a potentially empty set (`Set`

) because the predicate might be
true for all items.

dropWhileAntitone p = Data.Set.fromDistinctAscList . Data.List.NonEmpty.dropWhile p .`toList`

dropWhileAntitone p =`filter`

(not . p)

spanAntitone :: (a -> Bool) -> NESet a -> These (NESet a) (NESet a) Source #

*O(log n)*. Divide a set at the point where a predicate on the
elements stops holding. The user is responsible for ensuring that for
all elements `j`

and `k`

in the set, `j < k ==> p j >= p k`

.

Returns a `These`

with potentially two non-empty sets:

means that the predicate never failed for any item, returning the original set`This`

n1

means that the predicate failed for the first item, returning the original set`That`

n2

gives`These`

n1 n2`n1`

(the set up to the point where the predicate stops holding) and`n2`

(the set starting from the point where the predicate stops holding)

spanAntitone p xs = partition p xs

Note: if `p`

is not actually antitone, then `spanAntitone`

will split the set
at some *unspecified* point where the predicate switches from holding to not
holding (where the predicate is seen to hold before the first element and to fail
after the last element).

partition :: (a -> Bool) -> NESet a -> These (NESet a) (NESet a) Source #

*O(n)*. Partition the map according to a predicate.

Returns a `These`

with potentially two non-empty sets:

means that the predicate was true for all items.`This`

n1

means that the predicate was false for all items.`That`

n2

gives`These`

n1 n2`n1`

(all of the items that were true for the predicate) and`n2`

(all of the items that were false for the predicate).

See also `split`

.

partition (> 3) (fromList (5 :| [3])) == These (singleton 5) (singleton 3) partition (< 7) (fromList (5 :| [3])) == This (fromList (3 :| [5])) partition (> 7) (fromList (5 :| [3])) == That (fromList (3 :| [5]))

split :: Ord a => a -> NESet a -> Maybe (These (NESet a) (NESet a)) Source #

*O(log n)*. The expression (

) is potentially a `split`

x set`These`

containing up to two `NESet`

s based on splitting the set into sets
containing items before and after the value `x`

. It will never return
a set that contains `x`

itself.

`Nothing`

means that`x`

was the only value in the the original set, and so there are no items before or after it.

means`Just`

(`This`

n1)`x`

was larger than or equal to all items in the set, and`n1`

is the entire original set (minus`x`

, if it was present)

means`Just`

(`That`

n2)`x`

was smaller than or equal to all items in the set, and`n2`

is the entire original set (minus`x`

, if it was present)

gives`Just`

(`These`

n1 n2)`n1`

(the set of all values from the original set less than`x`

) and`n2`

(the set of all values from the original set greater than`x`

).

split 2 (fromList (5 :| [3])) == Just (That (fromList (3 :| [5])) ) split 3 (fromList (5 :| [3])) == Just (That (singleton 5) ) split 4 (fromList (5 :| [3])) == Just (These (singleton 3) (singleton 5)) split 5 (fromList (5 :| [3])) == Just (This (singleton 3) ) split 6 (fromList (5 :| [3])) == Just (This (fromList (3 :| [5])) ) split 5 (singleton 5) == Nothing

splitMember :: Ord a => a -> NESet a -> (Bool, Maybe (These (NESet a) (NESet a))) Source #

*O(log n)*. The expression (

) splits a set just
like `splitMember`

x set`split`

but also returns

(whether or not `member`

x set`x`

was
in `set`

)

splitMember 2 (fromList (5 :| [3])) == (False, Just (That (fromList (3 :| [5)])))) splitMember 3 (fromList (5 :| [3])) == (True , Just (That (singleton 5))) splitMember 4 (fromList (5 :| [3])) == (False, Just (These (singleton 3) (singleton 5))) splitMember 5 (fromList (5 :| [3])) == (True , Just (This (singleton 3)) splitMember 6 (fromList (5 :| [3])) == (False, Just (This (fromList (3 :| [5]))) splitMember 5 (singleton 5) == (True , Nothing)

splitRoot :: NESet a -> NonEmpty (NESet a) Source #

*O(1)*. Decompose a set into pieces based on the structure of the underlying
tree. This function is useful for consuming a set in parallel.

No guarantee is made as to the sizes of the pieces; an internal, but deterministic process determines this. However, it is guaranteed that the pieces returned will be in ascending order (all elements in the first subset less than all elements in the second, and so on).

Note that the current implementation does not return more than four subsets, but you should not depend on this behaviour because it can change in the future without notice.

# Indexed

lookupIndex :: Ord a => a -> NESet a -> Maybe Int Source #

*O(log n)*. Lookup the *index* of an element, which is its zero-based
index in the sorted sequence of elements. The index is a number from *0*
up to, but not including, the `size`

of the set.

isJust (lookupIndex 2 (fromList (5:|[3]))) == False fromJust (lookupIndex 3 (fromList (5:|[3]))) == 0 fromJust (lookupIndex 5 (fromList (5:|[3]))) == 1 isJust (lookupIndex 6 (fromList (5:|[3]))) == False

findIndex :: Ord a => a -> NESet a -> Int Source #

*O(log n)*. Return the *index* of an element, which is its zero-based
index in the sorted sequence of elements. The index is a number from *0*
up to, but not including, the `size`

of the set. Calls `error`

when the
element is not a `member`

of the set.

findIndex 2 (fromList (5:|[3])) Error: element is not in the set findIndex 3 (fromList (5:|[3])) == 0 findIndex 5 (fromList (5:|[3])) == 1 findIndex 6 (fromList (5:|[3])) Error: element is not in the set

elemAt :: Int -> NESet a -> a Source #

*O(log n)*. Retrieve an element by its *index*, i.e. by its zero-based
index in the sorted sequence of elements. If the *index* is out of range
(less than zero, greater or equal to `size`

of the set), `error`

is
called.

elemAt 0 (fromList (5:|[3])) == 3 elemAt 1 (fromList (5:|[3])) == 5 elemAt 2 (fromList (5:|[3])) Error: index out of range

deleteAt :: Int -> NESet a -> Set a Source #

*O(log n)*. Delete the element at *index*, i.e. by its zero-based
index in the sorted sequence of elements. If the *index* is out of range
(less than zero, greater or equal to `size`

of the set), `error`

is
called.

Returns a potentially empty set (`Set`

), because this could potentailly
delete the final element in a singleton set.

deleteAt 0 (fromList (5:|[3])) == singleton 5 deleteAt 1 (fromList (5:|[3])) == singleton 3 deleteAt 2 (fromList (5:|[3])) Error: index out of range deleteAt (-1) (fromList (5:|[3])) Error: index out of range

drop :: Int -> NESet a -> Set a Source #

Drop a given number of elements in order, beginning with the smallest ones.

Returns a potentailly empty set (`Set`

), in the case that `drop`

is
called with a number equal to or greater the number of items in the set,
and we drop every item.

`drop n = Data.Set.fromDistinctAscList . Data.List.NonEmpty.drop n . ``toAscList`

splitAt :: Int -> NESet a -> These (NESet a) (NESet a) Source #

*O(log n)*. Split a set at a particular index `i`

.

# Map

map :: Ord b => (a -> b) -> NESet a -> NESet b Source #

*O(n*log n)*.

is the set obtained by applying `map`

f s`f`

to each element of `s`

.

It's worth noting that the size of the result may be smaller if,
for some `(x,y)`

, `x /= y && f x == f y`

mapMonotonic :: (a -> b) -> NESet a -> NESet b Source #

*O(n)*.

, but works only when `mapMonotonic`

f s == `map`

f s`f`

is strictly
increasing. *The precondition is not checked.* Semi-formally, we have:

and [x < y ==> f x < f y | x <- ls, y <- ls] ==> mapMonotonic f s == map f s where ls = Data.Foldable.toList s

# Folds

## Strict folds

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.

foldr1' :: (a -> a -> a) -> NESet a -> a Source #

*O(n)*. A strict version of `foldr1`

. Each application of the operator
is evaluated before using the result in the next application. This
function is strict in the starting value.

foldl1' :: (a -> a -> a) -> NESet a -> a Source #

*O(n)*. A strict version of `foldl1`

. Each application of the operator
is evaluated before using the result in the next application. This
function is strict in the starting value.

# Min/Max

findMin :: NESet a -> a Source #

*O(1)*. The minimal element of a set. Note that this is total, making
`lookupMin`

obsolete. It is constant-time, so has better
asymptotics than `Data.Set.lookupMin`

and `Data.Map.findMin`

as well.

findMin (fromList (5 :| [3])) == 3

findMax :: NESet a -> a Source #

*O(log n)*. The maximal key of a set Note that this is total,
making `lookupMin`

obsolete.

findMax (fromList (5 :| [3])) == 5

deleteMin :: NESet a -> Set a Source #

*O(1)*. Delete the minimal element. Returns a potentially empty set
(`Set`

), because we might delete the final item in a singleton set. It
is constant-time, so has better asymptotics than `Data.Set.deleteMin`

.

deleteMin (fromList (5 :| [3, 7])) == Data.Set.fromList [5, 7] deleteMin (singleton 5) == Data.Set.empty

deleteMax :: NESet a -> Set a Source #

*O(log n)*. Delete the maximal element. Returns a potentially empty
set (`Set`

), because we might delete the final item in a singleton set.

deleteMax (fromList (5 :| [3, 7])) == Data.Set.fromList [3, 5] deleteMax (singleton 5) == Data.Set.empty

deleteFindMin :: NESet a -> (a, Set a) Source #

*O(1)*. Delete and find the minimal element. It is constant-time, so
has better asymptotics that `Data.Set.minView`

for `Set`

.

Note that unlike `Data.Set.deleteFindMin`

for `Set`

, this cannot ever
fail, and so is a total function. However, the result `Set`

is
potentially empty, since the original set might have contained just
a single item.

deleteFindMin (fromList (5 :| [3, 10])) == (3, Data.Set.fromList [5, 10])

deleteFindMax :: NESet a -> (a, Set a) Source #

*O(log n)*. Delete and find the minimal element.

Note that unlike `Data.Set.deleteFindMax`

for `Set`

, this cannot ever
fail, and so is a total function. However, the result `Set`

is
potentially empty, since the original set might have contained just
a single item.

deleteFindMax (fromList (5 :| [3, 10])) == (10, Data.Set.fromList [3, 5])

# Conversion

## List

elems :: NESet a -> NonEmpty a Source #

*O(n)*. An alias of `toAscList`

. The elements of a set in ascending
order.

toAscList :: NESet a -> NonEmpty a Source #

*O(n)*. Convert the set to an ascending non-empty list of elements.

toDescList :: NESet a -> NonEmpty a Source #

*O(n)*. Convert the set to a descending non-empty list of elements.