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.IntMap.NonEmpty

Contents

- Non-Empty IntMap Type
  - Conversions between empty and non-empty maps
- Construction
  - From Unordered Lists
  - From Ascending Lists
- Insertion
- Deletion/Update
- Query
  - Lookup
  - Size
- Combine
  - Union
  - Difference
  - Intersection
- Traversal
  - Map
- Folds
  - Strict folds
- Conversion
  - Lists
  - Ordered lists
- Filter
- Submap
- Min/Max
- Debugging

Description

# Non-Empty Finite Integer-Indexed Maps (lazy interface)

The ``NEIntMap` v` type represents a non-empty finite map (sometimes called a dictionary) from integer keys to values of type `v`. An `NEIntMap` is strict in its keys but lazy in its values.

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

This module essentially re-imports the API of Data.IntMap.Lazy and its `IntMap` 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 `NEIntMap` is implemented using `IntMap`, all of the caveats of using `IntMap` apply (such as the limitation of the maximum size of maps).

All functions take non-empty maps as inputs. In situations where their results can be guarunteed to also be non-empty, they also return non-empty maps. In situations where their results could potentially be empty, `IntMap` is returned instead.

Some variants of functions (like `alter'`, `alterF'`, `adjustMin`, `adjustMax`, `adjustMinWithKey`, `adjustMaxWithKey`) are provided in a way restructured to preserve guaruntees of non-empty maps being returned.

Some functions (like `mapEither`, `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.IntMap functions:

    import qualified Data.IntMap.NonEmpty as NEIM

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.

At the moment, this package does not provide a variant strict on values for these functions, like containers does. This is a planned future implementation (PR's are appreciated). For now, you can simulate a strict interface by manually forcing values before returning results.

Synopsis

- data NEIntMap a
- type Key = Int
- pattern IsNonEmpty :: NEIntMap a -> IntMap a
- pattern IsEmpty :: IntMap a
- nonEmptyMap :: IntMap a -> Maybe (NEIntMap a)
- toMap :: NEIntMap a -> IntMap a
- withNonEmpty :: r -> (NEIntMap a -> r) -> IntMap a -> r
- insertMap :: Key -> a -> IntMap a -> NEIntMap a
- insertMapWith :: (a -> a -> a) -> Key -> a -> IntMap a -> NEIntMap a
- insertMapWithKey :: (Key -> a -> a -> a) -> Key -> a -> IntMap a -> NEIntMap a
- insertMapMin :: Key -> a -> IntMap a -> NEIntMap a
- insertMapMax :: Key -> a -> IntMap a -> NEIntMap a
- unsafeFromMap :: IntMap a -> NEIntMap a
- singleton :: Key -> a -> NEIntMap a
- fromSet :: (Key -> a) -> NEIntSet -> NEIntMap a
- fromList :: NonEmpty (Key, a) -> NEIntMap a
- fromListWith :: (a -> a -> a) -> NonEmpty (Key, a) -> NEIntMap a
- fromListWithKey :: (Key -> a -> a -> a) -> NonEmpty (Key, a) -> NEIntMap a
- fromAscList :: NonEmpty (Key, a) -> NEIntMap a
- fromAscListWith :: (a -> a -> a) -> NonEmpty (Key, a) -> NEIntMap a
- fromAscListWithKey :: (Key -> a -> a -> a) -> NonEmpty (Key, a) -> NEIntMap a
- fromDistinctAscList :: NonEmpty (Key, a) -> NEIntMap a
- insert :: Key -> a -> NEIntMap a -> NEIntMap a
- insertWith :: (a -> a -> a) -> Key -> a -> NEIntMap a -> NEIntMap a
- insertWithKey :: (Key -> a -> a -> a) -> Key -> a -> NEIntMap a -> NEIntMap a
- insertLookupWithKey :: (Key -> a -> a -> a) -> Key -> a -> NEIntMap a -> (Maybe a, NEIntMap a)
- delete :: Key -> NEIntMap a -> IntMap a
- adjust :: (a -> a) -> Key -> NEIntMap a -> NEIntMap a
- adjustWithKey :: (Key -> a -> a) -> Key -> NEIntMap a -> NEIntMap a
- update :: (a -> Maybe a) -> Key -> NEIntMap a -> IntMap a
- updateWithKey :: (Key -> a -> Maybe a) -> Key -> NEIntMap a -> IntMap a
- updateLookupWithKey :: (Key -> a -> Maybe a) -> Key -> NEIntMap a -> (Maybe a, IntMap a)
- alter :: (Maybe a -> Maybe a) -> Key -> NEIntMap a -> IntMap a
- alterF :: Functor f => (Maybe a -> f (Maybe a)) -> Key -> NEIntMap a -> f (IntMap a)
- alter' :: (Maybe a -> a) -> Key -> NEIntMap a -> NEIntMap a
- alterF' :: Functor f => (Maybe a -> f a) -> Key -> NEIntMap a -> f (NEIntMap a)
- lookup :: Key -> NEIntMap a -> Maybe a
- (!?) :: NEIntMap a -> Key -> Maybe a
- (!) :: NEIntMap a -> Key -> a
- findWithDefault :: a -> Key -> NEIntMap a -> a
- member :: Key -> NEIntMap a -> Bool
- notMember :: Key -> NEIntMap a -> Bool
- lookupLT :: Key -> NEIntMap a -> Maybe (Key, a)
- lookupGT :: Key -> NEIntMap a -> Maybe (Key, a)
- lookupLE :: Key -> NEIntMap a -> Maybe (Key, a)
- lookupGE :: Key -> NEIntMap a -> Maybe (Key, a)
- size :: NEIntMap a -> Int
- union :: NEIntMap a -> NEIntMap a -> NEIntMap a
- unionWith :: (a -> a -> a) -> NEIntMap a -> NEIntMap a -> NEIntMap a
- unionWithKey :: (Key -> a -> a -> a) -> NEIntMap a -> NEIntMap a -> NEIntMap a
- unions :: Foldable1 f => f (NEIntMap a) -> NEIntMap a
- unionsWith :: Foldable1 f => (a -> a -> a) -> f (NEIntMap a) -> NEIntMap a
- difference :: NEIntMap a -> NEIntMap b -> IntMap a
- (\\) :: NEIntMap a -> NEIntMap b -> IntMap a
- differenceWith :: (a -> b -> Maybe a) -> NEIntMap a -> NEIntMap b -> IntMap a
- differenceWithKey :: (Key -> a -> b -> Maybe a) -> NEIntMap a -> NEIntMap b -> IntMap a
- intersection :: NEIntMap a -> NEIntMap b -> IntMap a
- intersectionWith :: (a -> b -> c) -> NEIntMap a -> NEIntMap b -> IntMap c
- intersectionWithKey :: (Key -> a -> b -> c) -> NEIntMap a -> NEIntMap b -> IntMap c
- map :: (a -> b) -> NEIntMap a -> NEIntMap b
- mapWithKey :: (Key -> a -> b) -> NEIntMap a -> NEIntMap b
- traverseWithKey1 :: Apply t => (Key -> a -> t b) -> NEIntMap a -> t (NEIntMap b)
- traverseWithKey :: Applicative t => (Key -> a -> t b) -> NEIntMap a -> t (NEIntMap b)
- mapAccum :: (a -> b -> (a, c)) -> a -> NEIntMap b -> (a, NEIntMap c)
- mapAccumWithKey :: (a -> Key -> b -> (a, c)) -> a -> NEIntMap b -> (a, NEIntMap c)
- mapAccumRWithKey :: (a -> Key -> b -> (a, c)) -> a -> NEIntMap b -> (a, NEIntMap c)
- mapKeys :: (Key -> Key) -> NEIntMap a -> NEIntMap a
- mapKeysWith :: (a -> a -> a) -> (Key -> Key) -> NEIntMap a -> NEIntMap a
- mapKeysMonotonic :: (Key -> Key) -> NEIntMap a -> NEIntMap a
- foldr :: (a -> b -> b) -> b -> NEIntMap a -> b
- foldl :: (a -> b -> a) -> a -> NEIntMap b -> a
- foldr1 :: (a -> a -> a) -> NEIntMap a -> a
- foldl1 :: (a -> a -> a) -> NEIntMap a -> a
- foldrWithKey :: (Key -> a -> b -> b) -> b -> NEIntMap a -> b
- foldlWithKey :: (a -> Key -> b -> a) -> a -> NEIntMap b -> a
- foldMapWithKey :: Semigroup m => (Key -> a -> m) -> NEIntMap a -> m
- foldr' :: (a -> b -> b) -> b -> NEIntMap a -> b
- foldr1' :: (a -> a -> a) -> NEIntMap a -> a
- foldl' :: (a -> b -> a) -> a -> NEIntMap b -> a
- foldl1' :: (a -> a -> a) -> NEIntMap a -> a
- foldrWithKey' :: (Key -> a -> b -> b) -> b -> NEIntMap a -> b
- foldlWithKey' :: (a -> Key -> b -> a) -> a -> NEIntMap b -> a
- elems :: NEIntMap a -> NonEmpty a
- keys :: NEIntMap a -> NonEmpty Key
- assocs :: NEIntMap a -> NonEmpty (Key, a)
- keysSet :: NEIntMap a -> NEIntSet
- toList :: NEIntMap a -> NonEmpty (Key, a)
- toAscList :: NEIntMap a -> NonEmpty (Key, a)
- toDescList :: NEIntMap a -> NonEmpty (Key, a)
- filter :: (a -> Bool) -> NEIntMap a -> IntMap a
- filterWithKey :: (Key -> a -> Bool) -> NEIntMap a -> IntMap a
- restrictKeys :: NEIntMap a -> IntSet -> IntMap a
- withoutKeys :: NEIntMap a -> IntSet -> IntMap a
- partition :: (a -> Bool) -> NEIntMap a -> These (NEIntMap a) (NEIntMap a)
- partitionWithKey :: (Key -> a -> Bool) -> NEIntMap a -> These (NEIntMap a) (NEIntMap a)
- mapMaybe :: (a -> Maybe b) -> NEIntMap a -> IntMap b
- mapMaybeWithKey :: (Key -> a -> Maybe b) -> NEIntMap a -> IntMap b
- mapEither :: (a -> Either b c) -> NEIntMap a -> These (NEIntMap b) (NEIntMap c)
- mapEitherWithKey :: (Key -> a -> Either b c) -> NEIntMap a -> These (NEIntMap b) (NEIntMap c)
- split :: Key -> NEIntMap a -> Maybe (These (NEIntMap a) (NEIntMap a))
- splitLookup :: Key -> NEIntMap a -> These a (These (NEIntMap a) (NEIntMap a))
- splitRoot :: NEIntMap a -> NonEmpty (NEIntMap a)
- isSubmapOf :: Eq a => NEIntMap a -> NEIntMap a -> Bool
- isSubmapOfBy :: (a -> b -> Bool) -> NEIntMap a -> NEIntMap b -> Bool
- isProperSubmapOf :: Eq a => NEIntMap a -> NEIntMap a -> Bool
- isProperSubmapOfBy :: (a -> b -> Bool) -> NEIntMap a -> NEIntMap b -> Bool
- findMin :: NEIntMap a -> (Key, a)
- findMax :: NEIntMap a -> (Key, a)
- deleteMin :: NEIntMap a -> IntMap a
- deleteMax :: NEIntMap a -> IntMap a
- deleteFindMin :: NEIntMap a -> ((Key, a), IntMap a)
- deleteFindMax :: NEIntMap a -> ((Key, a), IntMap a)
- updateMin :: (a -> Maybe a) -> NEIntMap a -> IntMap a
- updateMax :: (a -> Maybe a) -> NEIntMap a -> IntMap a
- adjustMin :: (a -> a) -> NEIntMap a -> NEIntMap a
- adjustMax :: (a -> a) -> NEIntMap a -> NEIntMap a
- updateMinWithKey :: (Key -> a -> Maybe a) -> NEIntMap a -> IntMap a
- updateMaxWithKey :: (Key -> a -> Maybe a) -> NEIntMap a -> IntMap a
- adjustMinWithKey :: (Key -> a -> a) -> NEIntMap a -> NEIntMap a
- adjustMaxWithKey :: (Key -> a -> a) -> NEIntMap a -> NEIntMap a
- minView :: NEIntMap a -> (a, IntMap a)
- maxView :: NEIntMap a -> (a, IntMap a)
- valid :: NEIntMap a -> Bool

# Non-Empty IntMap Type

data NEIntMap a Source #

A non-empty (by construction) map from integer keys to values `a`. At least one key-value pair exists in an ``NEIntMap` v` at all times.

Functions that take an `NEIntMap` can safely operate on it with the assumption that it has at least one key-value pair.

Functions that return an `NEIntMap` provide an assurance that the result has at least one key-value pair.

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

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

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

You can convert an `NEIntMap` into a `IntMap` with `toMap` or `IsNonEmpty`, essentially "obscuring" the non-empty property from the type.

#### Instances

Instances details

Foldable1 NEIntMap Source # | Traverses elements in order of ascending keys WARNING: `fold1` and `foldMap1` are different than `fold` and `foldMap` for the `IntMap` instance of `Foldable`. They traverse elements in order of ascending keys, while `IntMap` traverses positive keys first, then negative keys.

Instance details

Defined in Data.IntMap.NonEmpty.Internal

Methods

fold1 :: Semigroup m => NEIntMap m -> m Source #

foldMap1 :: Semigroup m => (a -> m) -> NEIntMap a -> m Source #

foldMap1' :: Semigroup m => (a -> m) -> NEIntMap a -> m Source #

toNonEmpty :: NEIntMap a -> NonEmpty a Source #

maximum :: Ord a => NEIntMap a -> a Source #

minimum :: Ord a => NEIntMap a -> a Source #

head :: NEIntMap a -> a Source #

last :: NEIntMap a -> a Source #

foldrMap1 :: (a -> b) -> (a -> b -> b) -> NEIntMap a -> b Source #

foldlMap1' :: (a -> b) -> (b -> a -> b) -> NEIntMap a -> b Source #

foldlMap1 :: (a -> b) -> (b -> a -> b) -> NEIntMap a -> b Source #

foldrMap1' :: (a -> b) -> (a -> b -> b) -> NEIntMap a -> b Source #

Eq1 NEIntMap Source # |
Instance details Defined in Data.IntMap.NonEmpty.Internal Methods liftEq :: (a -> b -> Bool) -> NEIntMap a -> NEIntMap b -> Bool Source #
Ord1 NEIntMap Source # |
Instance details Defined in Data.IntMap.NonEmpty.Internal Methods liftCompare :: (a -> b -> Ordering) -> NEIntMap a -> NEIntMap b -> Ordering Source #
Read1 NEIntMap Source # |
Instance details Defined in Data.IntMap.NonEmpty.Internal Methods liftReadsPrec :: (Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (NEIntMap a) Source # liftReadList :: (Int -> ReadS a) -> ReadS [a] -> ReadS [NEIntMap a] Source # liftReadPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec (NEIntMap a) Source # liftReadListPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec [NEIntMap a] Source #
Show1 NEIntMap Source # |
Instance details Defined in Data.IntMap.NonEmpty.Internal Methods liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> NEIntMap a -> ShowS Source # liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [NEIntMap a] -> ShowS Source #
Comonad NEIntMap Source # | `extract` gets the value at the minimal key, and `duplicate` produces a map of maps comprised of all keys from the original map greater than or equal to the current key. Since: 0.1.1.0
Instance details Defined in Data.IntMap.NonEmpty.Internal Methods extract :: NEIntMap a -> a Source # duplicate :: NEIntMap a -> NEIntMap (NEIntMap a) Source # extend :: (NEIntMap a -> b) -> NEIntMap a -> NEIntMap b Source #
Functor NEIntMap Source # |
Instance details Defined in Data.IntMap.NonEmpty.Internal Methods fmap :: (a -> b) -> NEIntMap a -> NEIntMap b Source # (<$) :: a -> NEIntMap b -> NEIntMap a Source #
Foldable NEIntMap Source # | Traverses elements in order of ascending keys. WARNING: `fold` and `foldMap` are different than for the `IntMap` instance. They traverse elements in order of ascending keys, while `IntMap` traverses positive keys first, then negative keys. `foldr1`, `foldl1`, `minimum`, `maximum` are all total.

Instance details

Defined in Data.IntMap.NonEmpty.Internal

Methods

fold :: Monoid m => NEIntMap m -> m Source #

foldMap :: Monoid m => (a -> m) -> NEIntMap a -> m Source #

foldMap' :: Monoid m => (a -> m) -> NEIntMap a -> m Source #

foldr :: (a -> b -> b) -> b -> NEIntMap a -> b Source #

foldr' :: (a -> b -> b) -> b -> NEIntMap a -> b Source #

foldl :: (b -> a -> b) -> b -> NEIntMap a -> b Source #

foldl' :: (b -> a -> b) -> b -> NEIntMap a -> b Source #

foldr1 :: (a -> a -> a) -> NEIntMap a -> a Source #

foldl1 :: (a -> a -> a) -> NEIntMap a -> a Source #

toList :: NEIntMap a -> [a] Source #

null :: NEIntMap a -> Bool Source #

length :: NEIntMap a -> Int Source #

elem :: Eq a => a -> NEIntMap a -> Bool Source #

maximum :: Ord a => NEIntMap a -> a Source #

minimum :: Ord a => NEIntMap a -> a Source #

sum :: Num a => NEIntMap a -> a Source #

product :: Num a => NEIntMap a -> a Source #

Traversable NEIntMap Source # | Traverses elements in order of ascending keys WARNING: Different than for the `IntMap` instance. They traverse elements in order of ascending keys, while `IntMap` traverses positive keys first, then negative keys.
Instance details Defined in Data.IntMap.NonEmpty.Internal Methods traverse :: Applicative f => (a -> f b) -> NEIntMap a -> f (NEIntMap b) Source # sequenceA :: Applicative f => NEIntMap (f a) -> f (NEIntMap a) Source # mapM :: Monad m => (a -> m b) -> NEIntMap a -> m (NEIntMap b) Source # sequence :: Monad m => NEIntMap (m a) -> m (NEIntMap a) Source #
Invariant NEIntMap Source # | Since: 0.3.4.4
Instance details Defined in Data.IntMap.NonEmpty.Internal Methods invmap :: (a -> b) -> (b -> a) -> NEIntMap a -> NEIntMap b Source #
Alt NEIntMap Source # | Since: 0.3.4.4
Instance details Defined in Data.IntMap.NonEmpty.Internal Methods (<!>) :: NEIntMap a -> NEIntMap a -> NEIntMap a Source # some :: Applicative NEIntMap => NEIntMap a -> NEIntMap [a] Source # many :: Applicative NEIntMap => NEIntMap a -> NEIntMap [a] Source #
Traversable1 NEIntMap Source # | Traverses elements in order of ascending keys WARNING: `traverse1` and `sequence1` are different `traverse` and `sequence` for the `IntMap` instance of `Traversable`. They traverse elements in order of ascending keys, while `IntMap` traverses positive keys first, then negative keys.
Instance details Defined in Data.IntMap.NonEmpty.Internal Methods traverse1 :: Apply f => (a -> f b) -> NEIntMap a -> f (NEIntMap b) Source # sequence1 :: Apply f => NEIntMap (f b) -> f (NEIntMap b) Source #
FromJSON a => FromJSON (NEIntMap a) Source # |
Instance details Defined in Data.IntMap.NonEmpty.Internal Methods parseJSON :: Value -> Parser (NEIntMap a) Source # parseJSONList :: Value -> Parser [NEIntMap a] Source # omittedField :: Maybe (NEIntMap a) Source #
ToJSON a => ToJSON (NEIntMap a) Source # |
Instance details Defined in Data.IntMap.NonEmpty.Internal Methods toJSON :: NEIntMap a -> Value Source # toEncoding :: NEIntMap a -> Encoding Source # toJSONList :: [NEIntMap a] -> Value Source # toEncodingList :: [NEIntMap a] -> Encoding Source # omitField :: NEIntMap a -> Bool Source #
NFData a => NFData (NEIntMap a) Source # |
Instance details Defined in Data.IntMap.NonEmpty.Internal Methods rnf :: NEIntMap a -> () Source #
Semigroup (NEIntMap a) Source # | Left-biased union
Instance details Defined in Data.IntMap.NonEmpty.Internal Methods (<>) :: NEIntMap a -> NEIntMap a -> NEIntMap a Source # sconcat :: NonEmpty (NEIntMap a) -> NEIntMap a Source # stimes :: Integral b => b -> NEIntMap a -> NEIntMap a Source #
Data a => Data (NEIntMap a) Source # |

Instance details

Defined in Data.IntMap.NonEmpty.Internal

Methods

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

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

toConstr :: NEIntMap a -> Constr Source #

dataTypeOf :: NEIntMap a -> DataType Source #

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

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

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

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

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

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

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

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

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

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

Read e => Read (NEIntMap e) Source # |
Instance details Defined in Data.IntMap.NonEmpty.Internal Methods readsPrec :: Int -> ReadS (NEIntMap e) Source # readList :: ReadS [NEIntMap e] Source # readPrec :: ReadPrec (NEIntMap e) Source # readListPrec :: ReadPrec [NEIntMap e] Source #
Show a => Show (NEIntMap a) Source # |
Instance details Defined in Data.IntMap.NonEmpty.Internal Methods showsPrec :: Int -> NEIntMap a -> ShowS Source # show :: NEIntMap a -> String Source # showList :: [NEIntMap a] -> ShowS Source #
Eq a => Eq (NEIntMap a) Source # |
Instance details Defined in Data.IntMap.NonEmpty.Internal Methods (==) :: NEIntMap a -> NEIntMap a -> Bool Source # (/=) :: NEIntMap a -> NEIntMap a -> Bool Source #
Ord a => Ord (NEIntMap a) Source # |

Instance details

Defined in Data.IntMap.NonEmpty.Internal

Methods

compare :: NEIntMap a -> NEIntMap a -> Ordering Source #

(<) :: NEIntMap a -> NEIntMap a -> Bool Source #

(<=) :: NEIntMap a -> NEIntMap a -> Bool Source #

(>) :: NEIntMap a -> NEIntMap a -> Bool Source #

(>=) :: NEIntMap a -> NEIntMap a -> Bool Source #

max :: NEIntMap a -> NEIntMap a -> NEIntMap a Source #

min :: NEIntMap a -> NEIntMap a -> NEIntMap a Source #

type Key = Int Source #

## Conversions between empty and non-empty maps

pattern IsNonEmpty :: NEIntMap a -> IntMap a Source #

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

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

    myFunc :: IntMap K X -> Y
    myFunc (IsNonEmpty n) =  -- here, the user provided a non-empty map, and n is the NEIntMap
    myFunc IsEmpty        =  -- here, the user provided an empty map.

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

pattern IsEmpty :: IntMap a Source #

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

Matching on `IsEmpty` means that the original `IntMap` 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.

nonEmptyMap :: IntMap a -> Maybe (NEIntMap a) Source #

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

`nonEmptyMap` and ``maybe` `empty` `toMap`` 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 `IntMap` being an `NEIntMap`.

    nonEmptyMap (Data.IntMap.fromList [(3,"a"), (5,"b")]) == Just (fromList ((3,"a") :| [(5,"b")]))

toMap :: NEIntMap a -> IntMap a Source #

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

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

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

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

withNonEmpty Source #

Arguments

:: r | value to return if map is empty
-> (NEIntMap a -> r) | function to apply if map is not empty
-> IntMap a |
-> r |

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

    nonEmptyMap == withNonEmpty Nothing Just

insertMap :: Key -> a -> IntMap a -> NEIntMap a Source #

O(log n). Convert a `IntMap` into an `NEIntMap` by adding a key-value pair. Because of this, we know that the map must have at least one element, and so therefore cannot be empty. If key is already present, will overwrite the original value.

See `insertMapMin` for a version that is constant-time if the new key is strictly smaller than all keys in the original map.

    insertMap 4 "c" (Data.IntMap.fromList [(5,"a"), (3,"b")]) == fromList ((3,"b") :| [(4,"c"), (5,"a")])
    insertMap 4 "c" Data.IntMap.empty == singleton 4 "c"

insertMapWith :: (a -> a -> a) -> Key -> a -> IntMap a -> NEIntMap a Source #

O(log n). Convert a `IntMap` into an `NEIntMap` by adding a key-value pair. Because of this, we know that the map must have at least one element, and so therefore cannot be empty. Uses a combining function with the new value as the first argument if the key is already present.

    insertMapWith (++) 4 "c" (Data.IntMap.fromList [(5,"a"), (3,"b")]) == fromList ((3,"b") :| [(4,"c"), (5,"a")])
    insertMapWith (++) 5 "c" (Data.IntMap.fromList [(5,"a"), (3,"b")]) == fromList ((3,"b") :| [(5,"ca")])

insertMapWithKey :: (Key -> a -> a -> a) -> Key -> a -> IntMap a -> NEIntMap a Source #

O(log n). Convert a `IntMap` into an `NEIntMap` by adding a key-value pair. Because of this, we know that the map must have at least one element, and so therefore cannot be empty. Uses a combining function with the key and new value as the first and second arguments if the key is already present.

    let f key new_value old_value = (show key) ++ ":" ++ new_value ++ "|" ++ old_value
    insertWithKey f 5 "xxx" (Data.IntMap.fromList [(5,"a"), (3,"b")]) == fromList ((3, "b") :| [(5, "5:xxx|a")])
    insertWithKey f 7 "xxx" (Data.IntMap.fromList [(5,"a"), (3,"b")]) == fromList ((3, "b") :| [(5, "a"), (7, "xxx")])
    insertWithKey f 5 "xxx" Data.IntMap.empty                         == singleton 5 "xxx"

insertMapMin :: Key -> a -> IntMap a -> NEIntMap a Source #

O(1) Convert a `IntMap` into an `NEIntMap` by adding a key-value pair where the key is strictly less than all keys in the input map. The keys in the original map must all be strictly greater than the new key. The precondition is not checked.

    insertMapMin 2 "c" (Data.IntMap.fromList [(5,"a"), (3,"b")]) == fromList ((2,"c") :| [(3,"b"), (5,"a")])
    valid (insertMapMin 2 "c" (Data.IntMap.fromList [(5,"a"), (3,"b")])) == True
    valid (insertMapMin 7 "c" (Data.IntMap.fromList [(5,"a"), (3,"b")])) == False
    valid (insertMapMin 3 "c" (Data.IntMap.fromList [(5,"a"), (3,"b")])) == False

insertMapMax :: Key -> a -> IntMap a -> NEIntMap a Source #

O(log n) Convert a `IntMap` into an `NEIntMap` by adding a key-value pair where the key is strictly greater than all keys in the input map. The keys in the original map must all be strictly less than the new key. The precondition is not checked.

At the current moment, this is identical simply `insertMap`; 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.

    insertMap 7 "c" (Data.IntMap.fromList [(5,"a"), (3,"b")]) == fromList ((3,"b") :| [(5,"a"), (7,"c")])

unsafeFromMap :: IntMap a -> NEIntMap a Source #

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

# Construction

singleton :: Key -> a -> NEIntMap a Source #

O(1). A map with a single element.

    singleton 1 'a'        == fromList ((1, 'a') :| [])
    size (singleton 1 'a') == 1

fromSet :: (Key -> a) -> NEIntSet -> NEIntMap a Source #

O(n). Build a non-empty map from a non-empty set of keys and a function which for each key computes its value.

    fromSet (\k -> replicate k 'a') (Data.Set.NonEmpty.fromList (3 :| [5])) == fromList ((5,"aaaaa") :| [(3,"aaa")])

## From Unordered Lists

fromList :: NonEmpty (Key, a) -> NEIntMap a Source #

O(n*log n). Build a non-empty map from a non-empty list of key/value pairs. See also `fromAscList`. If the list contains more than one value for the same key, the last value for the key is retained.

    fromList ((5,"a") :| [(3,"b"), (5, "c")]) == fromList ((5,"c") :| [(3,"b")])
    fromList ((5,"c") :| [(3,"b"), (5, "a")]) == fromList ((5,"a") :| [(3,"b")])

fromListWith :: (a -> a -> a) -> NonEmpty (Key, a) -> NEIntMap a Source #

O(n*log n). Build a map from a non-empty list of key/value pairs with a combining function. See also `fromAscListWith`.

    fromListWith (++) ((5,"a") :| [(5,"b"), (3,"b"), (3,"a"), (5,"a")]) == fromList ((3, "ab") :| [(5, "aba")])

fromListWithKey :: (Key -> a -> a -> a) -> NonEmpty (Key, a) -> NEIntMap a Source #

O(n*log n). Build a map from a non-empty list of key/value pairs with a combining function. See also `fromAscListWithKey`.

    let f k a1 a2 = (show k) ++ a1 ++ a2
    fromListWithKey f ((5,"a") :| [(5,"b"), (3,"b"), (3,"a"), (5,"a")]) == fromList ((3, "3ab") :| [(5, "5a5ba")])

## From Ascending Lists

fromAscList :: NonEmpty (Key, a) -> NEIntMap a Source #

O(n). Build a map from an ascending non-empty list in linear time. The precondition (input list is ascending) is not checked.

    fromAscList ((3,"b") :| [(5,"a")])          == fromList ((3, "b") :| [(5, "a")])
    fromAscList ((3,"b") :| [(5,"a"), (5,"b")]) == fromList ((3, "b") :| [(5, "b")])
    valid (fromAscList ((3,"b") :| [(5,"a"), (5,"b")])) == True
    valid (fromAscList ((5,"a") :| [(3,"b"), (5,"b")])) == False

fromAscListWith :: (a -> a -> a) -> NonEmpty (Key, a) -> NEIntMap a Source #

O(n). Build a map from an ascending non-empty list in linear time with a combining function for equal keys. /The precondition (input list is ascending) is not checked./

    fromAscListWith (++) ((3,"b") :| [(5,"a"), (5,"b")]) == fromList ((3, "b") :| [(5, "ba")])
    valid (fromAscListWith (++) ((3,"b") :| [(5,"a"), (5,"b"))]) == True
    valid (fromAscListWith (++) ((5,"a") :| [(3,"b"), (5,"b"))]) == False

fromAscListWithKey :: (Key -> a -> a -> a) -> NonEmpty (Key, a) -> NEIntMap a Source #

O(n). Build a map from an ascending non-empty list in linear time with a combining function for equal keys. /The precondition (input list is ascending) is not checked./

    let f k a1 a2 = (show k) ++ ":" ++ a1 ++ a2
    fromAscListWithKey f ((3,"b") :| [(5,"a"), (5,"b"), (5,"b")]) == fromList ((3, "b") :| [(5, "5:b5:ba")])
    valid (fromAscListWithKey f ((3,"b") :| [(5,"a"), (5,"b"), (5,"b")])) == True
    valid (fromAscListWithKey f ((5,"a") :| [(3,"b"), (5,"b"), (5,"b")])) == False

fromDistinctAscList :: NonEmpty (Key, a) -> NEIntMap a Source #

O(n). Build a map from an ascending non-empty list of distinct elements in linear time. The precondition is not checked.

    fromDistinctAscList ((3,"b") :| [(5,"a")]) == fromList ((3, "b") :| [(5, "a")])
    valid (fromDistinctAscList ((3,"b") :| [(5,"a")]))          == True
    valid (fromDistinctAscList ((3,"b") :| [(5,"a"), (5,"b")])) == False

# Insertion

insert :: Key -> a -> NEIntMap a -> NEIntMap a Source #

O(log n). Insert a new key and value in the map. If the key is already present in the map, the associated value is replaced with the supplied value. `insert` is equivalent to ``insertWith` `const``.

See `insertMap` for a version where the first argument is a `IntMap`.

    insert 5 'x' (fromList ((5,'a') :| [(3,'b')])) == fromList ((3, 'b') :| [(5, 'x')])
    insert 7 'x' (fromList ((5,'a') :| [(3,'b')])) == fromList ((3, 'b') :| [(5, 'a'), (7, 'x')])

insertWith :: (a -> a -> a) -> Key -> a -> NEIntMap a -> NEIntMap a Source #

O(log n). Insert with a function, combining new value and old value. ``insertWith` f key value mp` will insert the pair (key, value) into `mp` if key does not exist in the map. If the key does exist, the function will insert the pair `(key, f new_value old_value)`.

See `insertIntMapWith` for a version where the first argument is a `IntMap`.

    insertWith (++) 5 "xxx" (fromList ((5,"a") :| [(3,"b")])) == fromList ((3, "b") :| [(5, "xxxa")])
    insertWith (++) 7 "xxx" (fromList ((5,"a") :| [(3,"b")])) == fromList ((3, "b") :| [(5, "a"), (7, "xxx")])

insertWithKey :: (Key -> a -> a -> a) -> Key -> a -> NEIntMap a -> NEIntMap a Source #

O(log n). Insert with a function, combining key, new value and old value. ``insertWithKey` f key value mp` will insert the pair (key, value) into `mp` if key does not exist in the map. If the key does exist, the function will insert the pair `(key,f key new_value old_value)`. Note that the key passed to f is the same key passed to `insertWithKey`.

See `insertMapWithKey` for a version where the first argument is a `IntMap`.

    let f key new_value old_value = (show key) ++ ":" ++ new_value ++ "|" ++ old_value
    insertWithKey f 5 "xxx" (fromList ((5,"a") :| [(3,"b")])) == fromList ((3, "b") :| [(5, "5:xxx|a")])
    insertWithKey f 7 "xxx" (fromList ((5,"a") :| [(3,"b")])) == fromList ((3, "b") :| [(5, "a"), (7, "xxx")])

insertLookupWithKey :: (Key -> a -> a -> a) -> Key -> a -> NEIntMap a -> (Maybe a, NEIntMap a) Source #

O(log n). Combines insert operation with old value retrieval. The expression (``insertLookupWithKey` f k x map`) is a pair where the first element is equal to (``lookup` k map`) and the second element equal to (``insertWithKey` f k x map`).

    let f key new_value old_value = (show key) ++ ":" ++ new_value ++ "|" ++ old_value
    insertLookupWithKey f 5 "xxx" (fromList ((5,"a") :| [(3,"b")])) == (Just "a", fromList ((3, "b") :| [(5, "5:xxx|a")]))
    insertLookupWithKey f 7 "xxx" (fromList ((5,"a") :| [(3,"b")])) == (Nothing,  fromList ((3, "b") :| [(5, "a"), (7, "xxx")]))

This is how to define `insertLookup` using `insertLookupWithKey`:

    let insertLookup kx x t = insertLookupWithKey (\_ a _ -> a) kx x t
    insertLookup 5 "x" (fromList ((5,"a") :| [(3,"b")])) == (Just "a", fromList ((3, "b") :| [(5, "x")]))
    insertLookup 7 "x" (fromList ((5,"a") :| [(3,"b")])) == (Nothing,  fromList ((3, "b") :| [(5, "a"), (7, "x")]))

# Deletion/Update

delete :: Key -> NEIntMap a -> IntMap a Source #

O(log n). Delete a key and its value from the non-empty map. A potentially empty map (`IntMap`) is returned, since this might delete the last item in the `NEIntMap`. When the key is not a member of the map, is equivalent to `toMap`.

    delete 5 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 3 "b"
    delete 7 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.Singleton [(3, "b"), (5, "a")]

adjust :: (a -> a) -> Key -> NEIntMap a -> NEIntMap a Source #

O(log n). Update a value at a specific key with the result of the provided function. When the key is not a member of the map, the original map is returned.

    adjust ("new " ++) 5 (fromList ((5,"a") :| [(3,"b")])) == fromList ((3, "b") :| [(5, "new a")])
    adjust ("new " ++) 7 (fromList ((5,"a") :| [(3,"b")])) == fromList ((3, "b") :| [(5, "a")])

adjustWithKey :: (Key -> a -> a) -> Key -> NEIntMap a -> NEIntMap a Source #

O(log n). Adjust a value at a specific key. When the key is not a member of the map, the original map is returned.

    let f key x = (show key) ++ ":new " ++ x
    adjustWithKey f 5 (fromList ((5,"a") :| [(3,"b")])) == fromList ((3, "b") :| [(5, "5:new a")])
    adjustWithKey f 7 (fromList ((5,"a") :| [(3,"b")])) == fromList ((3, "b") :| [(5, "a")])

update :: (a -> Maybe a) -> Key -> NEIntMap a -> IntMap a Source #

O(log n). The expression (``update` f k map`) updates the value `x` at `k` (if it is in the map). If (`f x`) is `Nothing`, the element is deleted. If it is (``Just` y`), the key `k` is bound to the new value `y`.

Returns a potentially empty map (`IntMap`), because we can't know ahead of time if the function returns `Nothing` and deletes the final item in the `NEIntMap`.

    let f x = if x == "a" then Just "new a" else Nothing
    update f 5 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.fromList [(3, "b"), (5, "new a")]
    update f 7 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.fromList [(3, "b"), (5, "a")]
    update f 3 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 5 "a"

updateWithKey :: (Key -> a -> Maybe a) -> Key -> NEIntMap a -> IntMap a Source #

O(log n). The expression (``updateWithKey` f k map`) updates the value `x` at `k` (if it is in the map). If (`f k x`) is `Nothing`, the element is deleted. If it is (``Just` y`), the key `k` is bound to the new value `y`.

Returns a potentially empty map (`IntMap`), because we can't know ahead of time if the function returns `Nothing` and deletes the final item in the `NEIntMap`.

    let f k x = if x == "a" then Just ((show k) ++ ":new a") else Nothing
    updateWithKey f 5 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.fromList [(3, "b"), (5, "5:new a")]
    updateWithKey f 7 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.fromList [(3, "b"), (5, "a")]
    updateWithKey f 3 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 5 "a"

updateLookupWithKey :: (Key -> a -> Maybe a) -> Key -> NEIntMap a -> (Maybe a, IntMap a) Source #

O(min(n,W)). Lookup and update. The function returns original value, if it is updated. This is different behavior than `Data.Map.NonEmpty.updateLookupWithKey`. Returns the original key value if the map entry is deleted.

Returns a potentially empty map (`IntMap`) in the case that we delete the final key of a singleton map.

    let f k x = if x == "a" then Just ((show k) ++ ":new a") else Nothing
    updateLookupWithKey f 5 (fromList ((5,"a") :| [(3,"b")])) == (Just "5:new a", Data.IntMap.fromList ((3, "b") :| [(5, "5:new a")]))
    updateLookupWithKey f 7 (fromList ((5,"a") :| [(3,"b")])) == (Nothing,  Data.IntMap.fromList ((3, "b") :| [(5, "a")]))
    updateLookupWithKey f 3 (fromList ((5,"a") :| [(3,"b")])) == (Just "b", Data.IntMap.singleton 5 "a")

alter :: (Maybe a -> Maybe a) -> Key -> NEIntMap a -> IntMap a Source #

O(log n). The expression (``alter` f k map`) alters the value `x` at `k`, or absence thereof. `alter` can be used to insert, delete, or update a value in a `IntMap`. In short : `Data.IntMap.lookup k (`alter` f k m) = f (`lookup` k m)`.

Returns a potentially empty map (`IntMap`), because we can't know ahead of time if the function returns `Nothing` and deletes the final item in the `NEIntMap`.

See `alterF'` for a version that disallows deletion, and so therefore can return `NEIntMap`.

    let f _ = Nothing
    alter f 7 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.fromList [(3, "b"), (5, "a")]
    alter f 5 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 3 "b"

    let f _ = Just "c"
    alter f 7 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.fromList [(3, "b"), (5, "a"), (7, "c")]
    alter f 5 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.fromList [(3, "b"), (5, "c")]

alterF :: Functor f => (Maybe a -> f (Maybe a)) -> Key -> NEIntMap a -> f (IntMap a) Source #

O(log n). The expression (``alterF` f k map`) alters the value `x` at `k`, or absence thereof. `alterF` can be used to inspect, insert, delete, or update a value in a `IntMap`. In short: `Data.IntMap.lookup k <$> `alterF` f k m = f (`lookup` k m)`.

Example:

    interactiveAlter :: Int -> NEIntMap Int String -> IO (IntMap Int String)
    interactiveAlter k m = alterF f k m where
      f Nothing = do
         putStrLn $ show k ++
             " was not found in the map. Would you like to add it?"
         getUserResponse1 :: IO (Maybe String)
      f (Just old) = do
         putStrLn $ "The key is currently bound to " ++ show old ++
             ". Would you like to change or delete it?"
         getUserResponse2 :: IO (Maybe String)

Like `Data.IntMap.alterF` for `IntMap`, `alterF` can be considered to be a unifying generalization of `lookup` and `delete`; however, as a constrast, it cannot be used to implement `insert`, because it must return a `IntMap` instead of an `NEIntMap` (because the function might delete the final item in the `NEIntMap`). When used with trivial functors like `Identity` and `Const`, it is often slightly slower than specialized `lookup` and `delete`. However, when the functor is non-trivial and key comparison is not particularly cheap, it is the fastest way.

See `alterF'` for a version that disallows deletion, and so therefore can return `NEIntMap` and be used to implement `insert`

Note on rewrite rules:

This module includes GHC rewrite rules to optimize `alterF` for the `Const` and `Identity` functors. In general, these rules improve performance. The sole exception is that when using `Identity`, deleting a key that is already absent takes longer than it would without the rules. If you expect this to occur a very large fraction of the time, you might consider using a private copy of the `Identity` type.

Note: Unlike `Data.IntMap.alterF` for `IntMap`, `alterF` is not a flipped version of the `at` combinator from Control.Lens.At. However, it match the shape expected from most functions expecting lenses, getters, and setters, so can be thought of as a "psuedo-lens", with virtually the same practical applications as a legitimate lens.

alter' :: (Maybe a -> a) -> Key -> NEIntMap a -> NEIntMap a Source #

O(log n). Variant of `alter` that disallows deletion. Allows us to guarantee that the result is also a non-empty IntMap.

alterF' :: Functor f => (Maybe a -> f a) -> Key -> NEIntMap a -> f (NEIntMap a) Source #

O(log n). Variant of `alterF` that disallows deletion. Allows us to guarantee that the result is also a non-empty IntMap.

Like `Data.IntMap.alterF` for `IntMap`, can be used to generalize and unify `lookup` and `insert`. However, because it disallows deletion, it cannot be used to implement `delete`.

See `alterF` for usage information and caveats.

Note: Neither `alterF` nor `alterF'` can be considered flipped versions of the `at` combinator from Control.Lens.At. However, this can match the shape expected from most functions expecting lenses, getters, and setters, so can be thought of as a "psuedo-lens", with virtually the same practical applications as a legitimate lens.

WARNING: The rewrite rule for `Identity` exposes an inconsistency in undefined behavior for Data.IntMap. `Data.IntMap.alterF` will actually maintain the original key in the map when used with `Identity`; however, `Data.IntMap.insertWith` will replace the orginal key in the map. The rewrite rule for `alterF'` has chosen to be faithful to `Data.IntMap.insertWith`, and not `Data.IntMap.alterF`, for the sake of a cleaner implementation.

# Query

## Lookup

lookup :: Key -> NEIntMap a -> Maybe a Source #

O(log n). Lookup the value at a key in the map.

The function will return the corresponding value as `(`Just` value)`, or `Nothing` if the key isn't in the map.

An example of using `lookup`:

    import Prelude hiding (lookup)
    import Data.Map.NonEmpty

    employeeDept = fromList (("John","Sales") :| [("Bob","IT")])
    deptCountry = fromList (("IT","USA") :| [("Sales","France")])
    countryCurrency = fromList (("USA", "Dollar") :| [("France", "Euro")])

    employeeCurrency :: String -> Maybe String
    employeeCurrency name = do
        dept <- lookup name employeeDept
        country <- lookup dept deptCountry
        lookup country countryCurrency

    main = do
        putStrLn $ "John's currency: " ++ (show (employeeCurrency "John"))
        putStrLn $ "Pete's currency: " ++ (show (employeeCurrency "Pete"))

The output of this program:

      John's currency: Just "Euro"
      Pete's currency: Nothing

(!?) :: NEIntMap a -> Key -> Maybe a infixl 9 Source #

O(log n). Find the value at a key. Returns `Nothing` when the element can not be found.

    fromList ((5, 'a') :| [(3, 'b')]) !? 1 == Nothing

    fromList ((5, 'a') :| [(3, 'b')]) !? 5 == Just 'a'

(!) :: NEIntMap a -> Key -> a infixl 9 Source #

O(log n). Find the value at a key. Calls `error` when the element can not be found.

    fromList ((5,'a') :| [(3,'b')]) ! 1    Error: element not in the map
    fromList ((5,'a') :| [(3,'b')]) ! 5 == 'a'

findWithDefault :: a -> Key -> NEIntMap a -> a Source #

O(log n). The expression `(`findWithDefault` def k map)` returns the value at key `k` or returns default value `def` when the key is not in the map.

    findWithDefault 'x' 1 (fromList ((5,'a') :| [(3,'b')])) == 'x'
    findWithDefault 'x' 5 (fromList ((5,'a') :| [(3,'b')])) == 'a'

member :: Key -> NEIntMap a -> Bool Source #

O(log n). Is the key a member of the map? See also `notMember`.

    member 5 (fromList ((5,'a') :| [(3,'b')])) == True
    member 1 (fromList ((5,'a') :| [(3,'b')])) == False

notMember :: Key -> NEIntMap a -> Bool Source #

O(log n). Is the key not a member of the map? See also `member`.

    notMember 5 (fromList ((5,'a') :| [(3,'b')])) == False
    notMember 1 (fromList ((5,'a') :| [(3,'b')])) == True

lookupLT :: Key -> NEIntMap a -> Maybe (Key, a) Source #

O(log n). Find largest key smaller than the given one and return the corresponding (key, value) pair.

    lookupLT 3 (fromList ((3,'a') :| [(5,'b')])) == Nothing
    lookupLT 4 (fromList ((3,'a') :| [(5,'b')])) == Just (3, 'a')

lookupGT :: Key -> NEIntMap a -> Maybe (Key, a) Source #

O(log n). Find smallest key greater than the given one and return the corresponding (key, value) pair.

    lookupGT 4 (fromList ((3,'a') :| [(5,'b')])) == Just (5, 'b')
    lookupGT 5 (fromList ((3,'a') :| [(5,'b')])) == Nothing

lookupLE :: Key -> NEIntMap a -> Maybe (Key, a) Source #

O(log n). Find largest key smaller or equal to the given one and return the corresponding (key, value) pair.

    lookupLE 2 (fromList ((3,'a') :| [(5,'b')])) == Nothing
    lookupLE 4 (fromList ((3,'a') :| [(5,'b')])) == Just (3, 'a')
    lookupLE 5 (fromList ((3,'a') :| [(5,'b')])) == Just (5, 'b')

lookupGE :: Key -> NEIntMap a -> Maybe (Key, a) Source #

O(log n). Find smallest key greater or equal to the given one and return the corresponding (key, value) pair.

    lookupGE 3 (fromList ((3,'a') :| [(5,'b')])) == Just (3, 'a')
    lookupGE 4 (fromList ((3,'a') :| [(5,'b')])) == Just (5, 'b')
    lookupGE 6 (fromList ((3,'a') :| [(5,'b')])) == Nothing

## Size

size :: NEIntMap a -> Int Source #

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

    size (singleton 1 'a')                          == 1
    size (fromList ((1,'a') :| [(2,'c'), (3,'b')])) == 3

# Combine

## Union

union :: NEIntMap a -> NEIntMap a -> NEIntMap a Source #

O(m*log(n/m + 1)), m <= n. The expression (``union` t1 t2`) takes the left-biased union of `t1` and `t2`. It prefers `t1` when duplicate keys are encountered, i.e. (``union` == `unionWith` `const``).

    union (fromList ((5, "a") :| [(3, "b")])) (fromList ((5, "A") :| [(7, "C")])) == fromList ((3, "b") :| [(5, "a"), (7, "C")])

unionWith :: (a -> a -> a) -> NEIntMap a -> NEIntMap a -> NEIntMap a Source #

O(m*log(n/m + 1)), m <= n. Union with a combining function.

    unionWith (++) (fromList ((5, "a") :| [(3, "b")])) (fromList ((5, "A") :| [(7, "C")])) == fromList ((3, "b") :| [(5, "aA"), (7, "C")])

unionWithKey :: (Key -> a -> a -> a) -> NEIntMap a -> NEIntMap a -> NEIntMap a Source #

O(m*log(n/m + 1)), m <= n. Union with a combining function, given the matching key.

    let f key left_value right_value = (show key) ++ ":" ++ left_value ++ "|" ++ right_value
    unionWithKey f (fromList ((5, "a") :| [(3, "b")])) (fromList ((5, "A") :| [(7, "C")])) == fromList ((3, "b") :| [(5, "5:a|A"), (7, "C")])

unions :: Foldable1 f => f (NEIntMap a) -> NEIntMap a Source #

The left-biased union of a non-empty list of maps.

    unions (fromList ((5, "a") :| [(3, "b")]) :| [fromList ((5, "A") :| [(7, "C")]), fromList ((5, "A3") :| [(3, "B3")])])
        == fromList [(3, "b"), (5, "a"), (7, "C")]
    unions (fromList ((5, "A3") :| [(3, "B3")]) :| [fromList ((5, "A") :| [(7, "C")]), fromList ((5, "a") :| [(3, "b")])])
        == fromList ((3, "B3") :| [(5, "A3"), (7, "C")])

unionsWith :: Foldable1 f => (a -> a -> a) -> f (NEIntMap a) -> NEIntMap a Source #

The union of a non-empty list of maps, with a combining operation: (``unionsWith` f == `foldl1` (`unionWith` f)`).

    unionsWith (++) (fromList ((5, "a") :| [(3, "b")]) :| [fromList ((5, "A") :| [(7, "C")]), fromList ((5, "A3") :| [(3, "B3")])])
        == fromList ((3, "bB3") :| [(5, "aAA3"), (7, "C")])

## Difference

difference :: NEIntMap a -> NEIntMap b -> IntMap a Source #

O(m*log(n/m + 1)), m <= n. Difference of two maps. Return elements of the first map not existing in the second map.

Returns a potentially empty map (`IntMap`), in case the first map is a subset of the second map.

    difference (fromList ((5, "a") :| [(3, "b")])) (fromList ((5, "A") :| [(7, "C")])) == Data.IntMap.singleton 3 "b"

(\\) :: NEIntMap a -> NEIntMap b -> IntMap a Source #

Same as `difference`.

differenceWith :: (a -> b -> Maybe a) -> NEIntMap a -> NEIntMap b -> IntMap a Source #

O(n+m). Difference with a combining function. When two equal keys are encountered, the combining function is applied to the values of these keys. If it returns `Nothing`, the element is discarded (proper set difference). If it returns (``Just` y`), the element is updated with a new value `y`.

Returns a potentially empty map (`IntMap`), in case the first map is a subset of the second map and the function returns `Nothing` for every pair.

    let f al ar = if al == "b" then Just (al ++ ":" ++ ar) else Nothing
    differenceWith f (fromList ((5, "a") :| [(3, "b")])) (fromList ((5, "A") :| [(3, "B"), (7, "C")]))
        == Data.IntMap.singleton 3 "b:B"

differenceWithKey :: (Key -> a -> b -> Maybe a) -> NEIntMap a -> NEIntMap b -> IntMap a Source #

O(n+m). Difference with a combining function. When two equal keys are encountered, the combining function is applied to the key and both values. If it returns `Nothing`, the element is discarded (proper set difference). If it returns (``Just` y`), the element is updated with a new value `y`.

Returns a potentially empty map (`IntMap`), in case the first map is a subset of the second map and the function returns `Nothing` for every pair.

    let f k al ar = if al == "b" then Just ((show k) ++ ":" ++ al ++ "|" ++ ar) else Nothing
    differenceWithKey f (fromList ((5, "a") :| [(3, "b")])) (fromList ((5, "A") :| [(3, "B"), (10, "C")]))
        == Data.IntMap.singleton 3 "3:b|B"

## Intersection

intersection :: NEIntMap a -> NEIntMap b -> IntMap a Source #

O(m*log(n/m + 1)), m <= n. Intersection of two maps. Return data in the first map for the keys existing in both maps. (``intersection` m1 m2 == `intersectionWith` `const` m1 m2`).

Returns a potentially empty map (`IntMap`), in case the two maps share no keys in common.

    intersection (fromList ((5, "a") :| [(3, "b")])) (fromList ((5, "A") :| [(7, "C")])) == Data.IntMap.singleton 5 "a"

intersectionWith :: (a -> b -> c) -> NEIntMap a -> NEIntMap b -> IntMap c Source #

O(m*log(n/m + 1)), m <= n. Intersection with a combining function.

Returns a potentially empty map (`IntMap`), in case the two maps share no keys in common.

    intersectionWith (++) (fromList ((5, "a") :| [(3, "b")])) (fromList ((5, "A") :| [(7, "C")])) == Data.IntMap.singleton 5 "aA"

intersectionWithKey :: (Key -> a -> b -> c) -> NEIntMap a -> NEIntMap b -> IntMap c Source #

O(m*log(n/m + 1)), m <= n. Intersection with a combining function.

Returns a potentially empty map (`IntMap`), in case the two maps share no keys in common.

    let f k al ar = (show k) ++ ":" ++ al ++ "|" ++ ar
    intersectionWithKey f (fromList ((5, "a") :| [(3, "b")])) (fromList ((5, "A") :| [(7, "C")])) == Data.IntMap.singleton 5 "5:a|A"

# Traversal

## Map

map :: (a -> b) -> NEIntMap a -> NEIntMap b Source #

O(n). IntMap a function over all values in the map.

    map (++ "x") (fromList ((5,"a") :| [(3,"b")])) == fromList ((3, "bx") :| [(5, "ax")])

mapWithKey :: (Key -> a -> b) -> NEIntMap a -> NEIntMap b Source #

O(n). IntMap a function over all values in the map.

    let f key x = (show key) ++ ":" ++ x
    mapWithKey f (fromList ((5,"a") :| [(3,"b")])) == fromList ((3, "3:b") :| [(5, "5:a")])

traverseWithKey1 :: Apply t => (Key -> a -> t b) -> NEIntMap a -> t (NEIntMap b) Source #

O(n). ``traverseWithKey1` f m == `fromList` $ `traverse1` ((k, v) -> (,) k $ f k v) (`toList` m)`

That is, behaves exactly like a regular `traverse1` except that the traversing function also has access to the key associated with a value.

WARNING: Differs from `Data.IntMap.traverseWithKey`, which traverses positive items first, then negative items.

Is more general than `traverseWithKey`, since works with all `Apply`, and not just `Applicative`.

traverseWithKey :: Applicative t => (Key -> a -> t b) -> NEIntMap a -> t (NEIntMap b) Source #

O(n). ``traverseWithKey` f m == `fromList` $ `traverse` ((k, v) -> (,) k $ f k v) (`toList` m)` That is, behaves exactly like a regular `traverse` except that the traversing function also has access to the key associated with a value.

Use `traverseWithKey1` whenever possible (if your `Applicative` also has `Apply` instance). This version is provided only for types that do not have `Apply` instance, since `Apply` is not at the moment (and might not ever be) an official superclass of `Applicative`.

WARNING: Differs from `Data.IntMap.traverseWithKey`, which traverses positive items first, then negative items.

    traverseWithKey f = unwrapApplicative . traverseWithKey1 (\k -> WrapApplicative . f k)

mapAccum :: (a -> b -> (a, c)) -> a -> NEIntMap b -> (a, NEIntMap c) Source #

O(n). The function `mapAccum` threads an accumulating argument through the map in ascending order of keys.

    let f a b = (a ++ b, b ++ "X")
    mapAccum f "Everything: " (fromList ((5,"a") :| [(3,"b")])) == ("Everything: ba", fromList ((3, "bX") :| [(5, "aX")]))

mapAccumWithKey :: (a -> Key -> b -> (a, c)) -> a -> NEIntMap b -> (a, NEIntMap c) Source #

O(n). The function `mapAccumWithKey` threads an accumulating argument through the map in ascending order of keys.

    let f a k b = (a ++ " " ++ (show k) ++ "-" ++ b, b ++ "X")
    mapAccumWithKey f "Everything:" (fromList ((5,"a") :| [(3,"b")])) == ("Everything: 3-b 5-a", fromList ((3, "bX") :| [(5, "aX")]))

mapAccumRWithKey :: (a -> Key -> b -> (a, c)) -> a -> NEIntMap b -> (a, NEIntMap c) Source #

O(n). The function `mapAccumRWithKey` threads an accumulating argument through the map in descending order of keys.

mapKeys :: (Key -> Key) -> NEIntMap a -> NEIntMap a Source #

O(n*log n). ``mapKeys` f s` is the map obtained by applying `f` to each key of `s`.

The size of the result may be smaller if `f` maps two or more distinct keys to the same new key. In this case the value at the greatest of the original keys is retained.

While the size of the result map may be smaller than the input map, the output map is still guaranteed to be non-empty if the input map is non-empty.

    mapKeys (+ 1) (fromList ((5,"a") :| [(3,"b")]))                        == fromList ((4, "b") :| [(6, "a")])
    mapKeys (\ _ -> 1) (fromList ((1,"b") :| [(2,"a"), (3,"d"), (4,"c")])) == singleton 1 "c"
    mapKeys (\ _ -> 3) (fromList ((1,"b") :| [(2,"a"), (3,"d"), (4,"c")])) == singleton 3 "c"

mapKeysWith :: (a -> a -> a) -> (Key -> Key) -> NEIntMap a -> NEIntMap a Source #

O(n*log n). ``mapKeysWith` c f s` is the map obtained by applying `f` to each key of `s`.

The size of the result may be smaller if `f` maps two or more distinct keys to the same new key. In this case the associated values will be combined using `c`. The value at the greater of the two original keys is used as the first argument to `c`.

While the size of the result map may be smaller than the input map, the output map is still guaranteed to be non-empty if the input map is non-empty.

    mapKeysWith (++) (\ _ -> 1) (fromList ((1,"b") :| [(2,"a"), (3,"d"), (4,"c")])) == singleton 1 "cdab"
    mapKeysWith (++) (\ _ -> 3) (fromList ((1,"b") :| [(2,"a"), (3,"d"), (4,"c")])) == singleton 3 "cdab"

mapKeysMonotonic :: (Key -> Key) -> NEIntMap a -> NEIntMap a Source #

O(n). ``mapKeysMonotonic` f s == `mapKeys` f s`, but works only when `f` is strictly monotonic. That is, for any values `x` and `y`, if `x` < `y` then `f x` < `f y`. The precondition is not checked. Semi-formally, we have:

    and [x < y ==> f x < f y | x <- ls, y <- ls]
                        ==> mapKeysMonotonic f s == mapKeys f s
        where ls = keys s

This means that `f` maps distinct original keys to distinct resulting keys. This function has better performance than `mapKeys`.

While the size of the result map may be smaller than the input map, the output map is still guaranteed to be non-empty if the input map is non-empty.

    mapKeysMonotonic (\ k -> k * 2) (fromList ((5,"a") :| [(3,"b")])) == fromList ((6, "b") :| [(10, "a")])
    valid (mapKeysMonotonic (\ k -> k * 2) (fromList ((5,"a") :| [(3,"b")]))) == True
    valid (mapKeysMonotonic (\ _ -> 1)     (fromList ((5,"a") :| [(3,"b")]))) == False

# Folds

foldr :: (a -> b -> b) -> b -> NEIntMap a -> b Source #

O(n). Fold the values in the map using the given right-associative binary operator, such that ``foldr` f z == `foldr` f z . `elems``.

    elemsList map = foldr (:) [] map

    let f a len = len + (length a)
    foldr f 0 (fromList ((5,"a") :| [(3,"bbb")])) == 4

foldl :: (a -> b -> a) -> a -> NEIntMap b -> a Source #

O(n). Fold the values in the map using the given left-associative binary operator, such that ``foldl` f z == `foldl` f z . `elems``.

    elemsList = reverse . foldl (flip (:)) []

    let f len a = len + (length a)
    foldl f 0 (fromList ((5,"a") :| [(3,"bbb")])) == 4

foldr1 :: (a -> a -> a) -> NEIntMap a -> a Source #

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

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

foldl1 :: (a -> a -> a) -> NEIntMap a -> a Source #

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

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

foldrWithKey :: (Key -> a -> b -> b) -> b -> NEIntMap a -> b Source #

O(n). Fold the keys and values in the map using the given right-associative binary operator, such that ``foldrWithKey` f z == `foldr` (`uncurry` f) z . `toAscList``.

For example,

    keysList map = foldrWithKey (\k x ks -> k:ks) [] map

foldlWithKey :: (a -> Key -> b -> a) -> a -> NEIntMap b -> a Source #

O(n). Fold the keys and values in the map using the given left-associative binary operator, such that ``foldlWithKey` f z == `foldl` (\z' (kx, x) -> f z' kx x) z . `toAscList``.

For example,

    keysList = reverse . foldlWithKey (\ks k x -> k:ks) []

foldMapWithKey :: Semigroup m => (Key -> a -> m) -> NEIntMap a -> m Source #

O(n). Fold the keys and values in the map using the given semigroup, such that

    foldMapWithKey f = fold1 . mapWithKey f

WARNING: Differs from `Data.IntMap.foldMapWithKey`, which traverses positive items first, then negative items.

This can be an asymptotically faster than `foldrWithKey` or `foldlWithKey` for some monoids.

## Strict folds

foldr' :: (a -> b -> b) -> b -> NEIntMap 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.

foldr1' :: (a -> a -> a) -> NEIntMap 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.

foldl' :: (a -> b -> a) -> a -> NEIntMap 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.

foldl1' :: (a -> a -> a) -> NEIntMap 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.

foldrWithKey' :: (Key -> a -> b -> b) -> b -> NEIntMap a -> b Source #

O(n). A strict version of `foldrWithKey`. Each application of the operator is evaluated before using the result in the next application. This function is strict in the starting value.

foldlWithKey' :: (a -> Key -> b -> a) -> a -> NEIntMap b -> a Source #

O(n). A strict version of `foldlWithKey`. Each application of the operator is evaluated before using the result in the next application. This function is strict in the starting value.

# Conversion

elems :: NEIntMap a -> NonEmpty a Source #

O(n). Return all elements of the map in the ascending order of their keys.

    elems (fromList ((5,"a") :| [(3,"b")])) == ("b" :| ["a"])

keys :: NEIntMap a -> NonEmpty Key Source #

O(n). Return all keys of the map in ascending order.

    keys (fromList ((5,"a") :| [(3,"b")])) == (3 :| [5])

assocs :: NEIntMap a -> NonEmpty (Key, a) Source #

O(n). An alias for `toAscList`. Return all key/value pairs in the map in ascending key order.

    assocs (fromList ((5,"a") :| [(3,"b")])) == ((3,"b") :| [(5,"a")])

keysSet :: NEIntMap a -> NEIntSet Source #

O(n). The non-empty set of all keys of the map.

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

## Lists

toList :: NEIntMap a -> NonEmpty (Key, a) Source #

O(n). Convert the map to a non-empty list of key/value pairs.

    toList (fromList ((5,"a") :| [(3,"b")])) == ((3,"b") :| [(5,"a")])

## Ordered lists

toAscList :: NEIntMap a -> NonEmpty (Key, a) Source #

O(n). Convert the map to a list of key/value pairs where the keys are in ascending order.

    toAscList (fromList ((5,"a") :| [(3,"b")])) == ((3,"b") :| [(5,"a")])

toDescList :: NEIntMap a -> NonEmpty (Key, a) Source #

O(n). Convert the map to a list of key/value pairs where the keys are in descending order.

    toDescList (fromList ((5,"a") :| [(3,"b")])) == ((5,"a") :| [(3,"b")])

# Filter

filter :: (a -> Bool) -> NEIntMap a -> IntMap a Source #

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

Returns a potentially empty map (`IntMap`), because we could potentailly filter out all items in the original `NEIntMap`.

    filter (> "a") (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 3 "b"
    filter (> "x") (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.empty
    filter (< "a") (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.empty

filterWithKey :: (Key -> a -> Bool) -> NEIntMap a -> IntMap a Source #

O(n). Filter all keys/values that satisfy the predicate.

Returns a potentially empty map (`IntMap`), because we could potentailly filter out all items in the original `NEIntMap`.

    filterWithKey (\k _ -> k > 4) (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 5 "a"

restrictKeys :: NEIntMap a -> IntSet -> IntMap a Source #

O(m*log(n/m + 1)), m <= n. Restrict an `NEIntMap` to only those keys found in a `Set`.

    m `restrictKeys` s = filterWithKey (k _ -> k `member` s) m
    m `restrictKeys` s = m `intersection` fromSet (const ()) s

withoutKeys :: NEIntMap a -> IntSet -> IntMap a Source #

O(m*log(n/m + 1)), m <= n. Remove all keys in a `Set` from an `NEIntMap`.

    m `withoutKeys` s = filterWithKey (k _ -> k `notMember` s) m
    m `withoutKeys` s = m `difference` fromSet (const ()) s

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

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

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

- ``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 (> "a") (fromList ((5,"a") :| [(3,"b")])) == These (singleton 3 "b") (singleton 5 "a")
    partition (< "x") (fromList ((5,"a") :| [(3,"b")])) == This  (fromList ((3, "b") :| [(5, "a")]))
    partition (> "x") (fromList ((5,"a") :| [(3,"b")])) == That  (fromList ((3, "b") :| [(5, "a")]))

partitionWithKey :: (Key -> a -> Bool) -> NEIntMap a -> These (NEIntMap a) (NEIntMap a) Source #

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

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

- ``This` n1` means that the predicate was true for all items, returning the original map.
- ``That` n2` means that the predicate was false for all items, returning the original map.
- ``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`.

    partitionWithKey (\ k _ -> k > 3) (fromList ((5,"a") :| [(3,"b")])) == These (singleton 5 "a") (singleton 3 "b")
    partitionWithKey (\ k _ -> k < 7) (fromList ((5,"a") :| [(3,"b")])) == This  (fromList ((3, "b") :| [(5, "a")]))
    partitionWithKey (\ k _ -> k > 7) (fromList ((5,"a") :| [(3,"b")])) == That  (fromList ((3, "b") :| [(5, "a")]))

mapMaybe :: (a -> Maybe b) -> NEIntMap a -> IntMap b Source #

O(n). Map values and collect the `Just` results.

Returns a potentially empty map (`IntMap`), because the function could potentially return `Nothing` on all items in the `NEIntMap`.

    let f x = if x == "a" then Just "new a" else Nothing
    mapMaybe f (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 5 "new a"

mapMaybeWithKey :: (Key -> a -> Maybe b) -> NEIntMap a -> IntMap b Source #

O(n). Map keys/values and collect the `Just` results.

Returns a potentially empty map (`IntMap`), because the function could potentially return `Nothing` on all items in the `NEIntMap`.

    let f k _ = if k < 5 then Just ("key : " ++ (show k)) else Nothing
    mapMaybeWithKey f (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 3 "key : 3"

mapEither :: (a -> Either b c) -> NEIntMap a -> These (NEIntMap b) (NEIntMap c) Source #

O(n). Map values and separate the `Left` and `Right` results.

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

- ``This` n1` means that the results were all `Left`.
- ``That` n2` means that the results were all `Right`.
- ``These` n1 n2` gives `n1` (the map where the results were `Left`) and `n2` (the map where the results were `Right`)

    let f a = if a < "c" then Left a else Right a
    mapEither f (fromList ((5,"a") :| [(3,"b"), (1,"x"), (7,"z")]))
        == These (fromList ((3,"b") :| [(5,"a")])) (fromList ((1,"x") :| [(7,"z")]))

    mapEither (\ a -> Right a) (fromList ((5,"a") :| [(3,"b"), (1,"x"), (7,"z")]))
        == That (fromList ((5,"a") :| [(3,"b"), (1,"x"), (7,"z")]))

mapEitherWithKey :: (Key -> a -> Either b c) -> NEIntMap a -> These (NEIntMap b) (NEIntMap c) Source #

O(n). Map keys/values and separate the `Left` and `Right` results.

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

- ``This` n1` means that the results were all `Left`.
- ``That` n2` means that the results were all `Right`.
- ``These` n1 n2` gives `n1` (the map where the results were `Left`) and `n2` (the map where the results were `Right`)

    let f k a = if k < 5 then Left (k * 2) else Right (a ++ a)
    mapEitherWithKey f (fromList ((5,"a") :| [(3,"b"), (1,"x"), (7,"z")]))
        == These (fromList ((1,2) :| [(3,6)])) (fromList ((5,"aa") :| [(7,"zz")]))

    mapEitherWithKey (\_ a -> Right a) (fromList ((5,"a") :| [(3,"b"), (1,"x"), (7,"z")]))
        == That (fromList ((1,"x") :| [(3,"b"), (5,"a"), (7,"z")]))

split :: Key -> NEIntMap a -> Maybe (These (NEIntMap a) (NEIntMap a)) Source #

O(log n). The expression (``split` k map`) is potentially a `These` containing up to two `NEIntMap`s based on splitting the map into maps containing items before and after the given key `k`. It will never return a map that contains `k` itself.

- `Nothing` means that `k` was the only key in the the original map, and so there are no items before or after it.
- ``Just` (`This` n1)` means `k` was larger than or equal to all items in the map, and `n1` is the entire original map (minus `k`, if it was present)
- ``Just` (`That` n2)` means `k` was smaller than or equal to all items in the map, and `n2` is the entire original map (minus `k`, if it was present)
- ``Just` (`These` n1 n2)` gives `n1` (the map of all keys from the original map less than `k`) and `n2` (the map of all keys from the original map greater than `k`)

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

splitLookup :: Key -> NEIntMap a -> These a (These (NEIntMap a) (NEIntMap a)) Source #

O(log n). The expression (``splitLookup` k map`) splits a map just like `split` but also returns ``lookup` k map`, as the first field in the `These`:

    splitLookup 2 (fromList ((5,"a") :| [(3,"b")])) == That      (That  (fromList ((3,"b") :| [(5,"a")])))
    splitLookup 3 (fromList ((5,"a") :| [(3,"b")])) == These "b" (That  (singleton 5 "a"))
    splitLookup 4 (fromList ((5,"a") :| [(3,"b")])) == That      (These (singleton 3 "b") (singleton 5 "a"))
    splitLookup 5 (fromList ((5,"a") :| [(3,"b")])) == These "a" (This  (singleton 3 "b"))
    splitLookup 6 (fromList ((5,"a") :| [(3,"b")])) == That      (This  (fromList ((3,"b") :| [(5,"a")])))
    splitLookup 5 (singleton 5 "a")                 == This  "a"

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

O(1). Decompose a map into pieces based on the structure of the underlying tree. This function is useful for consuming a map 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 submap less than all elements in the second, and so on).

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

# Submap

isSubmapOf :: Eq a => NEIntMap a -> NEIntMap a -> Bool Source #

O(m*log(n/m + 1)), m <= n. This function is defined as (``isSubmapOf` = `isSubmapOfBy` (==)`).

isSubmapOfBy :: (a -> b -> Bool) -> NEIntMap a -> NEIntMap b -> Bool Source #

O(m*log(n/m + 1)), m <= n. The expression (``isSubmapOfBy` f t1 t2`) returns `True` if all keys in `t1` are in tree `t2`, and when `f` returns `True` when applied to their respective values. For example, the following expressions are all `True`:

    isSubmapOfBy (==) (singleton 'a' 1) (fromList (('a',1) :| [('b',2)]))
    isSubmapOfBy (<=) (singleton 'a' 1) (fromList (('a',1) :| [('b',2)]))
    isSubmapOfBy (==) (fromList (('a',1) :| [('b',2)])) (fromList (('a',1) :| [('b',2)]))

But the following are all `False`:

    isSubmapOfBy (==) (singleton 'a' 2) (fromList (('a',1) :| [('b',2)]))
    isSubmapOfBy (<)  (singleton 'a' 1) (fromList (('a',1) :| [('b',2)]))
    isSubmapOfBy (==) (fromList (('a',1) :| [('b',2)])) (singleton 'a' 1)

isProperSubmapOf :: Eq a => NEIntMap a -> NEIntMap a -> Bool Source #

O(m*log(n/m + 1)), m <= n. Is this a proper submap? (ie. a submap but not equal). Defined as (``isProperSubmapOf` = `isProperSubmapOfBy` (==)`).

isProperSubmapOfBy :: (a -> b -> Bool) -> NEIntMap a -> NEIntMap b -> Bool Source #

O(m*log(n/m + 1)), m <= n. Is this a proper submap? (ie. a submap but not equal). The expression (``isProperSubmapOfBy` f m1 m2`) returns `True` when `m1` and `m2` are not equal, all keys in `m1` are in `m2`, and when `f` returns `True` when applied to their respective values. For example, the following expressions are all `True`:

    isProperSubmapOfBy (==) (singleton 1 1) (fromList ((1,1) :| [(2,2)]))
    isProperSubmapOfBy (<=) (singleton 1 1) (fromList ((1,1) :| [(2,2)]))

But the following are all `False`:

    isProperSubmapOfBy (==) (fromList ((1,1) :| [(2,2)])) (fromList ((1,1) :| [(2,2)]))
    isProperSubmapOfBy (==) (fromList ((1,1) :| [(2,2)])) (singleton 1 1))
    isProperSubmapOfBy (<)  (singleton 1 1)               (fromList ((1,1) :| [(2,2)]))

# Min/Max

findMin :: NEIntMap a -> (Key, a) Source #

O(1). The minimal key of the map. Note that this is total, making `lookupMin` obsolete. It is constant-time, so has better asymptotics than `Data.IntMap.lookupMin` and `Data.IntMap.findMin`, as well.

    findMin (fromList ((5,"a") :| [(3,"b")])) == (3,"b")

findMax :: NEIntMap a -> (Key, a) Source #

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

    findMax (fromList ((5,"a") :| [(3,"b")])) == (5,"a")

deleteMin :: NEIntMap a -> IntMap a Source #

O(1). Delete the minimal key. Returns a potentially empty map (`IntMap`), because we might end up deleting the final key in a singleton map. It is constant-time, so has better asymptotics than `deleteMin`.

    deleteMin (fromList ((5,"a") :| [(3,"b"), (7,"c")])) == Data.IntMap.fromList [(5,"a"), (7,"c")]
    deleteMin (singleton 5 "a") == Data.IntMap.empty

deleteMax :: NEIntMap a -> IntMap a Source #

O(log n). Delete the maximal key. Returns a potentially empty map (`IntMap`), because we might end up deleting the final key in a singleton map.

    deleteMax (fromList ((5,"a") :| [(3,"b"), (7,"c")])) == Data.IntMap.fromList [(3,"b"), (5,"a")]
    deleteMax (singleton 5 "a") == Data.IntMap.empty

deleteFindMin :: NEIntMap a -> ((Key, a), IntMap a) Source #

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

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

    deleteFindMin (fromList ((5,"a") :| [(3,"b"), (10,"c")])) == ((3,"b"), Data.IntMap.fromList [(5,"a"), (10,"c")])

deleteFindMax :: NEIntMap a -> ((Key, a), IntMap a) Source #

O(log n). Delete and find the minimal key-value pair.

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

    deleteFindMax (fromList ((5,"a") :| [(3,"b"), (10,"c")])) == ((10,"c"), Data.IntMap.fromList [(3,"b"), (5,"a")])

updateMin :: (a -> Maybe a) -> NEIntMap a -> IntMap a Source #

O(1) if delete, O(log n) otherwise. Update the value at the minimal key. Returns a potentially empty map (`IntMap`), because we might end up deleting the final key in the map if the function returns `Nothing`. See `adjustMin` for a version that can guaruntee that we return a non-empty map.

    updateMin (\ a -> Just ("X" ++ a)) (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.fromList [(3, "Xb"), (5, "a")]
    updateMin (\ _ -> Nothing)         (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 5 "a"

updateMax :: (a -> Maybe a) -> NEIntMap a -> IntMap a Source #

O(log n). Update the value at the maximal key. Returns a potentially empty map (`IntMap`), because we might end up deleting the final key in the map if the function returns `Nothing`. See `adjustMax` for a version that can guarantee that we return a non-empty map.

    updateMax (\ a -> Just ("X" ++ a)) (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.fromList [(3, "b"), (5, "Xa")]
    updateMax (\ _ -> Nothing)         (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 3 "b"

adjustMin :: (a -> a) -> NEIntMap a -> NEIntMap a Source #

O(1). A version of `updateMin` that disallows deletion, allowing us to guarantee that the result is also non-empty.

adjustMax :: (a -> a) -> NEIntMap a -> NEIntMap a Source #

O(log n). A version of `updateMax` that disallows deletion, allowing us to guarantee that the result is also non-empty.

updateMinWithKey :: (Key -> a -> Maybe a) -> NEIntMap a -> IntMap a Source #

O(1) if delete, O(log n) otherwise. Update the value at the minimal key. Returns a potentially empty map (`IntMap`), because we might end up deleting the final key in the map if the function returns `Nothing`. See `adjustMinWithKey` for a version that guaruntees a non-empty map.

    updateMinWithKey (\ k a -> Just ((show k) ++ ":" ++ a)) (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.fromList [(3,"3:b"), (5,"a")]
    updateMinWithKey (\ _ _ -> Nothing)                     (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 5 "a"

updateMaxWithKey :: (Key -> a -> Maybe a) -> NEIntMap a -> IntMap a Source #

O(log n). Update the value at the maximal key. Returns a potentially empty map (`IntMap`), because we might end up deleting the final key in the map if the function returns `Nothing`. See `adjustMaxWithKey` for a version that guaruntees a non-empty map.

    updateMinWithKey (\ k a -> Just ((show k) ++ ":" ++ a)) (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.fromList [(3,"3:b"), (5,"a")]
    updateMinWithKey (\ _ _ -> Nothing)                     (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 5 "a"

adjustMinWithKey :: (Key -> a -> a) -> NEIntMap a -> NEIntMap a Source #

O(1). A version of `adjustMaxWithKey` that disallows deletion, allowing us to guarantee that the result is also non-empty. Note that it also is able to have better asymptotics than `updateMinWithKey` in general.

adjustMaxWithKey :: (Key -> a -> a) -> NEIntMap a -> NEIntMap a Source #

O(log n). A version of `updateMaxWithKey` that disallows deletion, allowing us to guarantee that the result is also non-empty.

minView :: NEIntMap a -> (a, IntMap a) Source #

O(1). Retrieves the value associated with minimal key of the map, and the map stripped of that element. It is constant-time, so has better asymptotics than `Data.IntMap.minView` for `IntMap`.

Note that unlike `Data.IntMap.minView` for `IntMap`, this cannot ever fail, so doesn't need to return in a `Maybe`. However, the result `IntMap` is potentially empty, since the original map might have contained just a single item.

    minView (fromList ((5,"a") :| [(3,"b")])) == ("b", Data.IntMap.singleton 5 "a")

maxView :: NEIntMap a -> (a, IntMap a) Source #

O(log n). Retrieves the value associated with maximal key of the map, and the map stripped of that element.

Note that unlike `Data.IntMap.maxView` from `IntMap`, this cannot ever fail, so doesn't need to return in a `Maybe`. However, the result `IntMap` is potentially empty, since the original map might have contained just a single item.

    maxView (fromList ((5,"a") :| [(3,"b")])) == ("a", Data.IntMap.singleton 3 "b")

# Debugging

valid :: NEIntMap a -> Bool Source #

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