nonempty-containers-0.3.5.0: Non-empty variants of containers data types, with full API

Copyright | (c) Justin Le 2018
License | BSD3
Maintainer | justin@jle.im
Stability | experimental
Portability | non-portable
Safe Haskell | None
Language | Haskell2010

Data.IntSet.NonEmpty

Contents

- Non-Empty Set Type
  - Conversions between empty and non-empty sets
- Construction
- Insertion
- Deletion
- Query
- Combine
- Filter
- Map
- Folds
  - Strict folds
- Min/Max
- Conversion
  - List
- Debugging

Description

# Non-Empty Finite Integer Sets

The `NEIntSet` type represents a non-empty set of integers.

See documentation for `NEIntSet` for information on how to convert and manipulate such non-empty set.

This module essentially re-imports the API of Data.IntSet and its `IntSet` 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).

Because `NEIntSet` is implemented using `IntSet`, all of the caveats of using `IntSet` 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, `IntSet` is returned instead.

Some functions (`partition`, `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.IntSet functions:

    import qualified Data.IntSet.NonEmpty as NEIS

Note that all asmyptotics O(f(n)) in this module are actually O(min(W, f(n))), where `W` is the number of bits in an `Int` (32 or 64). That is, if `f(n)` is greater than `W`, all operations are constant-time.

Synopsis

- data NEIntSet
- type Key = Int
- pattern IsNonEmpty :: NEIntSet -> IntSet
- pattern IsEmpty :: IntSet
- nonEmptySet :: IntSet -> Maybe NEIntSet
- toSet :: NEIntSet -> IntSet
- withNonEmpty :: r -> (NEIntSet -> r) -> IntSet -> r
- insertSet :: Key -> IntSet -> NEIntSet
- insertSetMin :: Key -> IntSet -> NEIntSet
- insertSetMax :: Key -> IntSet -> NEIntSet
- unsafeFromSet :: IntSet -> NEIntSet
- singleton :: Key -> NEIntSet
- fromList :: NonEmpty Key -> NEIntSet
- fromAscList :: NonEmpty Key -> NEIntSet
- fromDistinctAscList :: NonEmpty Key -> NEIntSet
- insert :: Key -> NEIntSet -> NEIntSet
- delete :: Key -> NEIntSet -> IntSet
- member :: Key -> NEIntSet -> Bool
- notMember :: Key -> NEIntSet -> Bool
- lookupLT :: Key -> NEIntSet -> Maybe Key
- lookupGT :: Key -> NEIntSet -> Maybe Key
- lookupLE :: Key -> NEIntSet -> Maybe Key
- lookupGE :: Key -> NEIntSet -> Maybe Key
- size :: NEIntSet -> Int
- isSubsetOf :: NEIntSet -> NEIntSet -> Bool
- isProperSubsetOf :: NEIntSet -> NEIntSet -> Bool
- disjoint :: NEIntSet -> NEIntSet -> Bool
- union :: NEIntSet -> NEIntSet -> NEIntSet
- unions :: Foldable1 f => f NEIntSet -> NEIntSet
- difference :: NEIntSet -> NEIntSet -> IntSet
- (\\) :: NEIntSet -> NEIntSet -> IntSet
- intersection :: NEIntSet -> NEIntSet -> IntSet
- filter :: (Key -> Bool) -> NEIntSet -> IntSet
- partition :: (Key -> Bool) -> NEIntSet -> These NEIntSet NEIntSet
- split :: Key -> NEIntSet -> Maybe (These NEIntSet NEIntSet)
- splitMember :: Key -> NEIntSet -> (Bool, Maybe (These NEIntSet NEIntSet))
- splitRoot :: NEIntSet -> NonEmpty NEIntSet
- map :: (Key -> Key) -> NEIntSet -> NEIntSet
- foldr :: (Key -> b -> b) -> b -> NEIntSet -> b
- foldl :: (a -> Key -> a) -> a -> NEIntSet -> a
- foldr1 :: (Key -> Key -> Key) -> NEIntSet -> Key
- foldl1 :: (Key -> Key -> Key) -> NEIntSet -> Key
- foldr' :: (Key -> b -> b) -> b -> NEIntSet -> b
- foldl' :: (a -> Key -> a) -> a -> NEIntSet -> a
- foldr1' :: (Key -> Key -> Key) -> NEIntSet -> Key
- foldl1' :: (Key -> Key -> Key) -> NEIntSet -> Key
- findMin :: NEIntSet -> Key
- findMax :: NEIntSet -> Key
- deleteMin :: NEIntSet -> IntSet
- deleteMax :: NEIntSet -> IntSet
- deleteFindMin :: NEIntSet -> (Key, IntSet)
- deleteFindMax :: NEIntSet -> (Key, IntSet)
- elems :: NEIntSet -> NonEmpty Key
- toList :: NEIntSet -> NonEmpty Key
- toAscList :: NEIntSet -> NonEmpty Key
- toDescList :: NEIntSet -> NonEmpty Key
- valid :: NEIntSet -> Bool

# Non-Empty Set Type

data NEIntSet Source #

A non-empty (by construction) set of integers. At least one value exists in an ``NEIntSet` a` at all times.

Functions that take an `NEIntSet` can safely operate on it with the assumption that it has at least one item.

Functions that return an `NEIntSet` provide an assurance that the result has at least one item.

Data.IntSet.NonEmpty re-exports the API of Data.IntSet, faithfully reproducing asymptotics, typeclass constraints, and semantics. Functions that ensure that input and output sets are both non-empty (like `insert`) return `NEIntSet`, but functions that might potentially return an empty map (like `delete`) return a `IntSet` instead.

You can directly construct an `NEIntSet` with the API from Data.IntSet.NonEmpty; it's more or less the same as constructing a normal `IntSet`, except you don't have access to `empty`. There are also a few ways to construct an `NEIntSet` from a `IntSet`:

1. The `nonEmptySet` smart constructor will convert a ``IntSet` a` into a ``Maybe` (`NEIntSet` a)`, returning `Nothing` if the original `IntSet` was empty.
2. You can use the `insertIntSet` family of functions to insert a value into a `IntSet` to create a guaranteed `NEIntSet`.
3. You can use the `IsNonEmpty` and `IsEmpty` patterns to "pattern match" on a `IntSet` to reveal it as either containing a `NEIntSet` or an empty map.
4. `withNonEmpty` offers a continuation-based interface for deconstructing a `IntSet` and treating it as if it were an `NEIntSet`.

You can convert an `NEIntSet` into a `IntSet` with `toSet` or `IsNonEmpty`, essentially "obscuring" the non-empty property from the type.

#### Instances

Instances details

FromJSON NEIntSet Source # |
Instance details Defined in Data.IntSet.NonEmpty.Internal Methods parseJSON :: Value -> Parser NEIntSet Source # parseJSONList :: Value -> Parser [NEIntSet] Source # omittedField :: Maybe NEIntSet Source #
ToJSON NEIntSet Source # |
Instance details Defined in Data.IntSet.NonEmpty.Internal Methods toJSON :: NEIntSet -> Value Source # toEncoding :: NEIntSet -> Encoding Source # toJSONList :: [NEIntSet] -> Value Source # toEncodingList :: [NEIntSet] -> Encoding Source # omitField :: NEIntSet -> Bool Source #
NFData NEIntSet Source # |
Instance details Defined in Data.IntSet.NonEmpty.Internal Methods rnf :: NEIntSet -> () Source #
Semigroup NEIntSet Source # | Left-biased union
Instance details Defined in Data.IntSet.NonEmpty.Internal Methods (<>) :: NEIntSet -> NEIntSet -> NEIntSet Source # sconcat :: NonEmpty NEIntSet -> NEIntSet Source # stimes :: Integral b => b -> NEIntSet -> NEIntSet Source #
Data NEIntSet Source # |

Instance details

Defined in Data.IntSet.NonEmpty.Internal

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> NEIntSet -> c NEIntSet Source #

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c NEIntSet Source #

toConstr :: NEIntSet -> Constr Source #

dataTypeOf :: NEIntSet -> DataType Source #

dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c NEIntSet) Source #

dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c NEIntSet) Source #

gmapT :: (forall b. Data b => b -> b) -> NEIntSet -> NEIntSet Source #

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> NEIntSet -> r Source #

gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> NEIntSet -> r Source #

gmapQ :: (forall d. Data d => d -> u) -> NEIntSet -> [u] Source #

gmapQi :: Int -> (forall d. Data d => d -> u) -> NEIntSet -> u Source #

gmapM :: Monad m => (forall d. Data d => d -> m d) -> NEIntSet -> m NEIntSet Source #

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> NEIntSet -> m NEIntSet Source #

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> NEIntSet -> m NEIntSet Source #

Read NEIntSet Source # |
Instance details Defined in Data.IntSet.NonEmpty.Internal Methods readsPrec :: Int -> ReadS NEIntSet Source # readList :: ReadS [NEIntSet] Source # readPrec :: ReadPrec NEIntSet Source # readListPrec :: ReadPrec [NEIntSet] Source #
Show NEIntSet Source # |
Instance details Defined in Data.IntSet.NonEmpty.Internal Methods showsPrec :: Int -> NEIntSet -> ShowS Source # show :: NEIntSet -> String Source # showList :: [NEIntSet] -> ShowS Source #
Eq NEIntSet Source # |
Instance details Defined in Data.IntSet.NonEmpty.Internal Methods (==) :: NEIntSet -> NEIntSet -> Bool Source # (/=) :: NEIntSet -> NEIntSet -> Bool Source #
Ord NEIntSet Source # |
Instance details Defined in Data.IntSet.NonEmpty.Internal Methods compare :: NEIntSet -> NEIntSet -> Ordering Source # (<) :: NEIntSet -> NEIntSet -> Bool Source # (<=) :: NEIntSet -> NEIntSet -> Bool Source # (>) :: NEIntSet -> NEIntSet -> Bool Source # (>=) :: NEIntSet -> NEIntSet -> Bool Source # max :: NEIntSet -> NEIntSet -> NEIntSet Source # min :: NEIntSet -> NEIntSet -> NEIntSet Source #

type Key = Int Source #

## Conversions between empty and non-empty sets

pattern IsNonEmpty :: NEIntSet -> IntSet Source #

O(1) match, O(log n) usage of contents. The `IsNonEmpty` and `IsEmpty` patterns allow you to treat a `IntSet` as if it were either a ``IsNonEmpty` n` (where `n` is a `NEIntSet`) or an `IsEmpty`.

For example, you can pattern match on a `IntSet`:

    myFunc :: IntSet X -> Y
    myFunc (IsNonEmpty n) =  -- here, the user provided a non-empty set, and n is the NEIntSet
    myFunc IsEmpty        =  -- here, the user provided an empty set

Matching on ``IsNonEmpty` n` means that the original `IntSet` was not empty, and you have a verified-non-empty `NEIntSet` `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 `NEIntSet` back into a `IntSet`, obscuring its non-emptiness (see `toSet`).

pattern IsEmpty :: IntSet Source #

O(1). The `IsNonEmpty` and `IsEmpty` patterns allow you to treat a `IntSet` as if it were either a ``IsNonEmpty` n` (where `n` is a `NEIntSet`) or an `IsEmpty`.

Matching on `IsEmpty` means that the original `IntSet` 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 :: IntSet -> Maybe NEIntSet Source #

O(log n). Smart constructor for an `NEIntSet` from a `IntSet`. Returns `Nothing` if the `IntSet` was originally actually empty, and ``Just` n` with an `NEIntSet`, if the `IntSet` was not empty.

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

See `IsNonEmpty` for a pattern synonym that lets you "match on" the possiblity of a `IntSet` being an `NEIntSet`.

    nonEmptySet (Data.IntSet.fromList [3,5]) == Just (fromList (3:|[5]))

toSet :: NEIntSet -> IntSet Source #

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

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

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

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

withNonEmpty Source #

Arguments

:: r | value to return if set is empty
-> (NEIntSet -> r) | function to apply if set is not empty
-> IntSet |
-> r |

O(log n). A general continuation-based way to consume a `IntSet` as if it were an `NEIntSet`. ``withNonEmpty` def f` will take a `IntSet`. If set is empty, it will evaluate to `def`. Otherwise, a non-empty set `NEIntSet` will be fed to the function `f` instead.

    nonEmptySet == withNonEmpty Nothing Just

insertSet :: Key -> IntSet -> NEIntSet Source #

O(log n). Convert a `IntSet` into an `NEIntSet` 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.IntSet.fromList [5, 3]) == fromList (3 :| [4, 5])
    insertSet 4 Data.IntSet.empty == singleton 4 "c"

insertSetMin :: Key -> IntSet -> NEIntSet Source #

O(1) Convert a `IntSet` into an `NEIntSet` 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.IntSet.fromList [5, 3]) == fromList (2 :| [3, 5])
    valid (insertSetMin 2 (Data.IntSet.fromList [5, 3])) == True
    valid (insertSetMin 7 (Data.IntSet.fromList [5, 3])) == False
    valid (insertSetMin 3 (Data.IntSet.fromList [5, 3])) == False

insertSetMax :: Key -> IntSet -> NEIntSet Source #

O(log n) Convert a `IntSet` into an `NEIntSet` 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.

At the current moment, this is identical simply `insertSet`; however, it is left both for consistency and as a placeholder for a future version where optimizations are implemented to allow for a faster implementation.

    insertSetMin 7 (Data.IntSet.fromList [5, 3]) == fromList (3 :| [5, 7])

unsafeFromSet :: IntSet -> NEIntSet Source #

O(log n). Unsafe version of `nonEmptySet`. Coerces a `IntSet` into an `NEIntSet`, but is undefined (throws a runtime exception when evaluation is attempted) for an empty `IntSet`.

# Construction

singleton :: Key -> NEIntSet Source #

O(1). Create a singleton set.

fromList :: NonEmpty Key -> NEIntSet Source #

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

fromAscList :: NonEmpty Key -> NEIntSet Source #

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

fromDistinctAscList :: NonEmpty Key -> NEIntSet 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.

# Insertion

insert :: Key -> NEIntSet -> NEIntSet 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

delete :: Key -> NEIntSet -> IntSet Source #

O(log n). Delete an element from a set.

# Query

member :: Key -> NEIntSet -> Bool Source #

O(log n). Is the element in the set?

notMember :: Key -> NEIntSet -> Bool Source #

O(log n). Is the element not in the set?

lookupLT :: Key -> NEIntSet -> Maybe Key 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 :: Key -> NEIntSet -> Maybe Key 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 :: Key -> NEIntSet -> Maybe Key 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 :: Key -> NEIntSet -> Maybe Key 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 :: NEIntSet -> Int Source #

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

isSubsetOf :: NEIntSet -> NEIntSet -> Bool Source #

O(n+m). Is this a subset? `(s1 `isSubsetOf` s2)` tells whether `s1` is a subset of `s2`.

isProperSubsetOf :: NEIntSet -> NEIntSet -> Bool Source #

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

disjoint :: NEIntSet -> NEIntSet -> 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 :: NEIntSet -> NEIntSet -> NEIntSet 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 => f NEIntSet -> NEIntSet Source #

The union of a non-empty list of sets

difference :: NEIntSet -> NEIntSet -> IntSet Source #

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

Returns a potentially empty set (`IntSet`) because the first set might be a subset of the second set, and therefore have all of its elements removed.

(\\) :: NEIntSet -> NEIntSet -> IntSet Source #

Same as `difference`.

intersection :: NEIntSet -> NEIntSet -> IntSet Source #

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

Returns a potentially empty set (`IntSet`), because the two sets might have an empty intersection.

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

    import qualified Data.IntSet.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:|[]))`.

# Filter

filter :: (Key -> Bool) -> NEIntSet -> IntSet Source #

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

Returns a potentially empty set (`IntSet`) because the predicate might filter out all items in the original non-empty set.

partition :: (Key -> Bool) -> NEIntSet -> These NEIntSet NEIntSet Source #

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

Returns a `These` with potentially two non-empty sets:

- ``This` n1` means that the predicate was true for all items.
- ``That` n2` means that the predicate was false for all items.
- ``These` n1 n2` gives `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 :: Key -> NEIntSet -> Maybe (These NEIntSet NEIntSet) Source #

O(log n). The expression (``split` x set`) is potentially a `These` containing up to two `NEIntSet`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.
- ``Just` (`This` n1)` means `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)
- ``Just` (`That` n2)` means `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)
- ``Just` (`These` n1 n2)` gives `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 :: Key -> NEIntSet -> (Bool, Maybe (These NEIntSet NEIntSet)) Source #

O(log n). The expression (``splitMember` x set`) splits a set just like `split` but also returns ``member` x set` (whether or not `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 :: NEIntSet -> NonEmpty NEIntSet 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.

# Map

map :: (Key -> Key) -> NEIntSet -> NEIntSet Source #

O(n*log n). ``map` f s` is the set obtained by applying `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`

# Folds

foldr :: (Key -> b -> b) -> b -> NEIntSet -> b Source #

O(n). Fold the elements in the set using the given right-associative binary operator, such that ``foldr` f z == `foldr` f z . `toAscList``.

For example,

    elemsList set = foldr (:) [] set

foldl :: (a -> Key -> a) -> a -> NEIntSet -> a Source #

O(n). Fold the elements in the set using the given left-associative binary operator, such that ``foldl` f z == `foldl` f z . `toAscList``.

For example,

    descElemsList set = foldl (flip (:)) [] set

foldr1 :: (Key -> Key -> Key) -> NEIntSet -> Key Source #

O(n). A version of `foldr` that uses the value at the maximal value in the set as the starting value.

Note that, unlike `foldr1` for `IntSet`, this function is total if the input function is total.

foldl1 :: (Key -> Key -> Key) -> NEIntSet -> Key Source #

O(n). A version of `foldl` that uses the value at the minimal value in the set as the starting value.

Note that, unlike `foldl1` for `IntSet`, this function is total if the input function is total.

## Strict folds

foldr' :: (Key -> b -> b) -> b -> NEIntSet -> 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 -> Key -> a) -> a -> NEIntSet -> 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' :: (Key -> Key -> Key) -> NEIntSet -> Key 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' :: (Key -> Key -> Key) -> NEIntSet -> Key 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 :: NEIntSet -> Key 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.IntSet.lookupMin` and `Data.Map.findMin` as well.

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

findMax :: NEIntSet -> Key Source #

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

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

deleteMin :: NEIntSet -> IntSet Source #

O(1). Delete the minimal element. Returns a potentially empty set (`IntSet`), because we might delete the final item in a singleton set. It is constant-time, so has better asymptotics than `Data.IntSet.deleteMin`.

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

deleteMax :: NEIntSet -> IntSet Source #

O(log n). Delete the maximal element. Returns a potentially empty set (`IntSet`), because we might delete the final item in a singleton set.

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

deleteFindMin :: NEIntSet -> (Key, IntSet) Source #

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

Note that unlike `Data.IntSet.deleteFindMin` for `IntSet`, this cannot ever fail, and so is a total function. However, the result `IntSet` is potentially empty, since the original set might have contained just a single item.

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

deleteFindMax :: NEIntSet -> (Key, IntSet) Source #

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

Note that unlike `Data.IntSet.deleteFindMax` for `IntSet`, this cannot ever fail, and so is a total function. However, the result `IntSet` is potentially empty, since the original set might have contained just a single item.

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

# Conversion

## List

elems :: NEIntSet -> NonEmpty Key Source #

O(n). An alias of `toAscList`. The elements of a set in ascending order.

toList :: NEIntSet -> NonEmpty Key Source #

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

toAscList :: NEIntSet -> NonEmpty Key Source #

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

toDescList :: NEIntSet -> NonEmpty Key Source #

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

# Debugging

valid :: NEIntSet -> Bool Source #

O(n). Test if the internal set structure is valid.