Data.IntMap.NonEmpty

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.

Non-Empty IntMap Type

data NEIntMap a

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

Functor NEIntMap

Defined in Data.IntMap.NonEmpty.Internal

Methods

fmap :: (a -> b) -> NEIntMap a -> NEIntMap b

(<$) :: a -> NEIntMap b -> NEIntMap a

Foldable NEIntMap

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.

Defined in Data.IntMap.NonEmpty.Internal

Methods

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

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

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

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

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

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

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

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

toList :: NEIntMap a -> [a]

null :: NEIntMap a -> Bool

length :: NEIntMap a -> Int

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

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

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

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

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

Traversable NEIntMap

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.

Defined in Data.IntMap.NonEmpty.Internal

Methods

traverse :: Applicative f => (a -> f b) -> NEIntMap a -> f (NEIntMap b)

sequenceA :: Applicative f => NEIntMap (f a) -> f (NEIntMap a)

mapM :: Monad m => (a -> m b) -> NEIntMap a -> m (NEIntMap b)

sequence :: Monad m => NEIntMap (m a) -> m (NEIntMap a)

Eq1 NEIntMap

Defined in Data.IntMap.NonEmpty.Internal

Methods

liftEq :: (a -> b -> Bool) -> NEIntMap a -> NEIntMap b -> Bool

Ord1 NEIntMap

Defined in Data.IntMap.NonEmpty.Internal

Methods

liftCompare :: (a -> b -> Ordering) -> NEIntMap a -> NEIntMap b -> Ordering

Read1 NEIntMap

Defined in Data.IntMap.NonEmpty.Internal

Methods

liftReadsPrec :: (Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (NEIntMap a)

liftReadList :: (Int -> ReadS a) -> ReadS [a] -> ReadS [NEIntMap a]

liftReadPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec (NEIntMap a)

liftReadListPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec [NEIntMap a]

Show1 NEIntMap

Defined in Data.IntMap.NonEmpty.Internal

Methods

liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> NEIntMap a -> ShowS

liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [NEIntMap a] -> ShowS

Comonad NEIntMap

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

Defined in Data.IntMap.NonEmpty.Internal

Methods

extract :: NEIntMap a -> a

duplicate :: NEIntMap a -> NEIntMap (NEIntMap a)

extend :: (NEIntMap a -> b) -> NEIntMap a -> NEIntMap b

Traversable1 NEIntMap

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.

Defined in Data.IntMap.NonEmpty.Internal

Methods

traverse1 :: Apply f => (a -> f b) -> NEIntMap a -> f (NEIntMap b)

sequence1 :: Apply f => NEIntMap (f b) -> f (NEIntMap b)

Foldable1 NEIntMap

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.

Defined in Data.IntMap.NonEmpty.Internal

Methods

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

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

toNonEmpty :: NEIntMap a -> NonEmpty a

Eq a => Eq (NEIntMap a)

Defined in Data.IntMap.NonEmpty.Internal

Methods

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

(/=) :: NEIntMap a -> NEIntMap a -> Bool

Data a => Data (NEIntMap a)

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)

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

toConstr :: NEIntMap a -> Constr

dataTypeOf :: NEIntMap a -> DataType

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

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

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

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

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

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

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

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

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

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

Ord a => Ord (NEIntMap a)

Defined in Data.IntMap.NonEmpty.Internal

Methods

compare :: NEIntMap a -> NEIntMap a -> Ordering

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

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

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

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

max :: NEIntMap a -> NEIntMap a -> NEIntMap a

min :: NEIntMap a -> NEIntMap a -> NEIntMap a

Read e => Read (NEIntMap e)

Defined in Data.IntMap.NonEmpty.Internal

Methods

readsPrec :: Int -> ReadS (NEIntMap e)

readList :: ReadS [NEIntMap e]

readPrec :: ReadPrec (NEIntMap e)

readListPrec :: ReadPrec [NEIntMap e]

Show a => Show (NEIntMap a)

Defined in Data.IntMap.NonEmpty.Internal

Methods

showsPrec :: Int -> NEIntMap a -> ShowS

show :: NEIntMap a -> String

showList :: [NEIntMap a] -> ShowS

Semigroup (NEIntMap a)

Left-biased union

Defined in Data.IntMap.NonEmpty.Internal

Methods

(<>) :: NEIntMap a -> NEIntMap a -> NEIntMap a

sconcat :: NonEmpty (NEIntMap a) -> NEIntMap a

stimes :: Integral b => b -> NEIntMap a -> NEIntMap a

NFData a => NFData (NEIntMap a)

Defined in Data.IntMap.NonEmpty.Internal

Methods

rnf :: NEIntMap a -> ()

type Key = Int

Conversions between empty and non-empty maps

pattern IsNonEmpty :: NEIntMap a -> IntMap a

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

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)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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)

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

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

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

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

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

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)

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

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)

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

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)

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

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

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

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

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

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

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)

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)

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)

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)

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

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

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

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

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

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

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

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

Same as difference.

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

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

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

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

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

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

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

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)

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)

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)

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)

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)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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)

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

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)

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)

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)

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

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

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

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

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)

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)

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

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

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)

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)

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))

O(log n). The expression (split k map) is potentially a These containing up to two NEIntMaps 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 -> (Maybe a, Maybe (These (NEIntMap a) (NEIntMap a)))

O(log n). The expression (splitLookup k map) splits a map just like split but also returns lookup k map, as a Maybe a.

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

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

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

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

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

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

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

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)

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)

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

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

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)

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)

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

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

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

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

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

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

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

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

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)

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)

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

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