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

Data.Map.NonEmpty

Contents

Non-Empty Map type
- Conversions between empty and non-empty maps
Construction
Insertion
Deletion/Update
Query
- Lookup
- Size
Combine
Traversal
- Map
Folds
- Strict folds
Conversion
- Lists
- Ordered lists
Filter
Submap
Indexed
Min/Max
Debugging

Description

Non-Empty Finite Maps (lazy interface)

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

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

This module essentially re-imports the API of Data.Map.Lazy and its Map type, along with semantics and asymptotics. In most situations, asymptotics are different only by a constant factor. In some situations, asmyptotics are even better (constant-time instead of log-time). All typeclass constraints are identical to their Data.Map counterparts.

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

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

Some functions (like mapEither, partition, spanAntitone, split) have modified return types to account for possible configurations of non-emptiness.

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

import qualified Data.Map.NonEmpty as NEM

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 NEMap k a
pattern IsNonEmpty :: NEMap k a -> Map k a
pattern IsEmpty :: Map k a
nonEmptyMap :: Map k a -> Maybe (NEMap k a)
toMap :: NEMap k a -> Map k a
withNonEmpty :: r -> (NEMap k a -> r) -> Map k a -> r
insertMap :: Ord k => k -> a -> Map k a -> NEMap k a
insertMapWith :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> NEMap k a
insertMapWithKey :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> NEMap k a
insertMapMin :: k -> a -> Map k a -> NEMap k a
insertMapMax :: k -> a -> Map k a -> NEMap k a
unsafeFromMap :: Map k a -> NEMap k a
singleton :: k -> a -> NEMap k a
fromSet :: (k -> a) -> NESet k -> NEMap k a
fromList :: Ord k => NonEmpty (k, a) -> NEMap k a
fromListWith :: Ord k => (a -> a -> a) -> NonEmpty (k, a) -> NEMap k a
fromListWithKey :: Ord k => (k -> a -> a -> a) -> NonEmpty (k, a) -> NEMap k a
fromAscList :: Eq k => NonEmpty (k, a) -> NEMap k a
fromAscListWith :: Eq k => (a -> a -> a) -> NonEmpty (k, a) -> NEMap k a
fromAscListWithKey :: Eq k => (k -> a -> a -> a) -> NonEmpty (k, a) -> NEMap k a
fromDistinctAscList :: NonEmpty (k, a) -> NEMap k a
fromDescList :: Eq k => NonEmpty (k, a) -> NEMap k a
fromDescListWith :: Eq k => (a -> a -> a) -> NonEmpty (k, a) -> NEMap k a
fromDescListWithKey :: Eq k => (k -> a -> a -> a) -> NonEmpty (k, a) -> NEMap k a
fromDistinctDescList :: NonEmpty (k, a) -> NEMap k a
insert :: Ord k => k -> a -> NEMap k a -> NEMap k a
insertWith :: Ord k => (a -> a -> a) -> k -> a -> NEMap k a -> NEMap k a
insertWithKey :: Ord k => (k -> a -> a -> a) -> k -> a -> NEMap k a -> NEMap k a
insertLookupWithKey :: Ord k => (k -> a -> a -> a) -> k -> a -> NEMap k a -> (Maybe a, NEMap k a)
delete :: Ord k => k -> NEMap k a -> Map k a
adjust :: Ord k => (a -> a) -> k -> NEMap k a -> NEMap k a
adjustWithKey :: Ord k => (k -> a -> a) -> k -> NEMap k a -> NEMap k a
update :: Ord k => (a -> Maybe a) -> k -> NEMap k a -> Map k a
updateWithKey :: Ord k => (k -> a -> Maybe a) -> k -> NEMap k a -> Map k a
updateLookupWithKey :: Ord k => (k -> a -> Maybe a) -> k -> NEMap k a -> (Maybe a, Map k a)
alter :: Ord k => (Maybe a -> Maybe a) -> k -> NEMap k a -> Map k a
alterF :: (Ord k, Functor f) => (Maybe a -> f (Maybe a)) -> k -> NEMap k a -> f (Map k a)
alter' :: Ord k => (Maybe a -> a) -> k -> NEMap k a -> NEMap k a
alterF' :: (Ord k, Functor f) => (Maybe a -> f a) -> k -> NEMap k a -> f (NEMap k a)
lookup :: Ord k => k -> NEMap k a -> Maybe a
(!?) :: Ord k => NEMap k a -> k -> Maybe a
(!) :: Ord k => NEMap k a -> k -> a
findWithDefault :: Ord k => a -> k -> NEMap k a -> a
member :: Ord k => k -> NEMap k a -> Bool
notMember :: Ord k => k -> NEMap k a -> Bool
lookupLT :: Ord k => k -> NEMap k a -> Maybe (k, a)
lookupGT :: Ord k => k -> NEMap k a -> Maybe (k, a)
lookupLE :: Ord k => k -> NEMap k a -> Maybe (k, a)
lookupGE :: Ord k => k -> NEMap k a -> Maybe (k, a)
absurdNEMap :: NEMap Void a -> b
size :: NEMap k a -> Int
union :: Ord k => NEMap k a -> NEMap k a -> NEMap k a
unionWith :: Ord k => (a -> a -> a) -> NEMap k a -> NEMap k a -> NEMap k a
unionWithKey :: Ord k => (k -> a -> a -> a) -> NEMap k a -> NEMap k a -> NEMap k a
unions :: (Foldable1 f, Ord k) => f (NEMap k a) -> NEMap k a
unionsWith :: (Foldable1 f, Ord k) => (a -> a -> a) -> f (NEMap k a) -> NEMap k a
difference :: Ord k => NEMap k a -> NEMap k b -> Map k a
(\\) :: Ord k => NEMap k a -> NEMap k b -> Map k a
differenceWith :: Ord k => (a -> b -> Maybe a) -> NEMap k a -> NEMap k b -> Map k a
differenceWithKey :: Ord k => (k -> a -> b -> Maybe a) -> NEMap k a -> NEMap k b -> Map k a
intersection :: Ord k => NEMap k a -> NEMap k b -> Map k a
intersectionWith :: Ord k => (a -> b -> c) -> NEMap k a -> NEMap k b -> Map k c
intersectionWithKey :: Ord k => (k -> a -> b -> c) -> NEMap k a -> NEMap k b -> Map k c
map :: (a -> b) -> NEMap k a -> NEMap k b
mapWithKey :: (k -> a -> b) -> NEMap k a -> NEMap k b
traverseWithKey1 :: Apply t => (k -> a -> t b) -> NEMap k a -> t (NEMap k b)
traverseWithKey :: Applicative t => (k -> a -> t b) -> NEMap k a -> t (NEMap k b)
traverseMaybeWithKey1 :: Apply t => (k -> a -> t (Maybe b)) -> NEMap k a -> t (Map k b)
traverseMaybeWithKey :: Applicative t => (k -> a -> t (Maybe b)) -> NEMap k a -> t (Map k b)
mapAccum :: (a -> b -> (a, c)) -> a -> NEMap k b -> (a, NEMap k c)
mapAccumWithKey :: (a -> k -> b -> (a, c)) -> a -> NEMap k b -> (a, NEMap k c)
mapAccumRWithKey :: (a -> k -> b -> (a, c)) -> a -> NEMap k b -> (a, NEMap k c)
mapKeys :: Ord k2 => (k1 -> k2) -> NEMap k1 a -> NEMap k2 a
mapKeysWith :: Ord k2 => (a -> a -> a) -> (k1 -> k2) -> NEMap k1 a -> NEMap k2 a
mapKeysMonotonic :: (k1 -> k2) -> NEMap k1 a -> NEMap k2 a
foldr :: (a -> b -> b) -> b -> NEMap k a -> b
foldl :: (a -> b -> a) -> a -> NEMap k b -> a
foldr1 :: (a -> a -> a) -> NEMap k a -> a
foldl1 :: (a -> a -> a) -> NEMap k a -> a
foldrWithKey :: (k -> a -> b -> b) -> b -> NEMap k a -> b
foldlWithKey :: (a -> k -> b -> a) -> a -> NEMap k b -> a
foldMapWithKey :: Semigroup m => (k -> a -> m) -> NEMap k a -> m
foldr' :: (a -> b -> b) -> b -> NEMap k a -> b
foldr1' :: (a -> a -> a) -> NEMap k a -> a
foldl' :: (a -> b -> a) -> a -> NEMap k b -> a
foldl1' :: (a -> a -> a) -> NEMap k a -> a
foldrWithKey' :: (k -> a -> b -> b) -> b -> NEMap k a -> b
foldlWithKey' :: (a -> k -> b -> a) -> a -> NEMap k b -> a
elems :: NEMap k a -> NonEmpty a
keys :: NEMap k a -> NonEmpty k
assocs :: NEMap k a -> NonEmpty (k, a)
keysSet :: NEMap k a -> NESet k
toList :: NEMap k a -> NonEmpty (k, a)
toAscList :: NEMap k a -> NonEmpty (k, a)
toDescList :: NEMap k a -> NonEmpty (k, a)
filter :: (a -> Bool) -> NEMap k a -> Map k a
filterWithKey :: (k -> a -> Bool) -> NEMap k a -> Map k a
restrictKeys :: Ord k => NEMap k a -> Set k -> Map k a
withoutKeys :: Ord k => NEMap k a -> Set k -> Map k a
partition :: (a -> Bool) -> NEMap k a -> These (NEMap k a) (NEMap k a)
partitionWithKey :: (k -> a -> Bool) -> NEMap k a -> These (NEMap k a) (NEMap k a)
takeWhileAntitone :: (k -> Bool) -> NEMap k a -> Map k a
dropWhileAntitone :: (k -> Bool) -> NEMap k a -> Map k a
spanAntitone :: (k -> Bool) -> NEMap k a -> These (NEMap k a) (NEMap k a)
mapMaybe :: (a -> Maybe b) -> NEMap k a -> Map k b
mapMaybeWithKey :: (k -> a -> Maybe b) -> NEMap k a -> Map k b
mapEither :: (a -> Either b c) -> NEMap k a -> These (NEMap k b) (NEMap k c)
mapEitherWithKey :: (k -> a -> Either b c) -> NEMap k a -> These (NEMap k b) (NEMap k c)
split :: Ord k => k -> NEMap k a -> Maybe (These (NEMap k a) (NEMap k a))
splitLookup :: Ord k => k -> NEMap k a -> These a (These (NEMap k a) (NEMap k a))
splitRoot :: NEMap k a -> NonEmpty (NEMap k a)
isSubmapOf :: (Ord k, Eq a) => NEMap k a -> NEMap k a -> Bool
isSubmapOfBy :: Ord k => (a -> b -> Bool) -> NEMap k a -> NEMap k b -> Bool
isProperSubmapOf :: (Ord k, Eq a) => NEMap k a -> NEMap k a -> Bool
isProperSubmapOfBy :: Ord k => (a -> b -> Bool) -> NEMap k a -> NEMap k b -> Bool
lookupIndex :: Ord k => k -> NEMap k a -> Maybe Int
findIndex :: Ord k => k -> NEMap k a -> Int
elemAt :: Int -> NEMap k a -> (k, a)
updateAt :: (k -> a -> Maybe a) -> Int -> NEMap k a -> Map k a
adjustAt :: (k -> a -> a) -> Int -> NEMap k a -> NEMap k a
deleteAt :: Int -> NEMap k a -> Map k a
take :: Int -> NEMap k a -> Map k a
drop :: Int -> NEMap k a -> Map k a
splitAt :: Int -> NEMap k a -> These (NEMap k a) (NEMap k a)
findMin :: NEMap k a -> (k, a)
findMax :: NEMap k a -> (k, a)
deleteMin :: NEMap k a -> Map k a
deleteMax :: NEMap k a -> Map k a
deleteFindMin :: NEMap k a -> ((k, a), Map k a)
deleteFindMax :: NEMap k a -> ((k, a), Map k a)
updateMin :: (a -> Maybe a) -> NEMap k a -> Map k a
updateMax :: (a -> Maybe a) -> NEMap k a -> Map k a
adjustMin :: (a -> a) -> NEMap k a -> NEMap k a
adjustMax :: (a -> a) -> NEMap k a -> NEMap k a
updateMinWithKey :: (k -> a -> Maybe a) -> NEMap k a -> Map k a
updateMaxWithKey :: (k -> a -> Maybe a) -> NEMap k a -> Map k a
adjustMinWithKey :: (k -> a -> a) -> NEMap k a -> NEMap k a
adjustMaxWithKey :: (k -> a -> a) -> NEMap k a -> NEMap k a
minView :: NEMap k a -> (a, Map k a)
maxView :: NEMap k a -> (a, Map k a)
valid :: Ord k => NEMap k a -> Bool

Non-Empty Map type

data NEMap k a Source #

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

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

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

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

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

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

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

Instances

Instances details

Eq2 NEMap Source #
Instance details Defined in Data.Map.NonEmpty.Internal Methods liftEq2 :: (a -> b -> Bool) -> (c -> d -> Bool) -> NEMap a c -> NEMap b d -> Bool #
Ord2 NEMap Source #
Instance details Defined in Data.Map.NonEmpty.Internal Methods liftCompare2 :: (a -> b -> Ordering) -> (c -> d -> Ordering) -> NEMap a c -> NEMap b d -> Ordering #
Show2 NEMap Source #
Instance details Defined in Data.Map.NonEmpty.Internal Methods liftShowsPrec2 :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> (Int -> b -> ShowS) -> ([b] -> ShowS) -> Int -> NEMap a b -> ShowS # liftShowList2 :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> (Int -> b -> ShowS) -> ([b] -> ShowS) -> [NEMap a b] -> ShowS #
Functor (NEMap k) Source #
Instance details Defined in Data.Map.NonEmpty.Internal Methods fmap :: (a -> b) -> NEMap k a -> NEMap k b # (<$) :: a -> NEMap k b -> NEMap k a #
Foldable (NEMap k) Source #	Traverses elements in order of ascending keys `foldr1`, `foldl1`, `minimum`, `maximum` are all total.
Instance details Defined in Data.Map.NonEmpty.Internal Methods fold :: Monoid m => NEMap k m -> m # foldMap :: Monoid m => (a -> m) -> NEMap k a -> m # foldMap' :: Monoid m => (a -> m) -> NEMap k a -> m # foldr :: (a -> b -> b) -> b -> NEMap k a -> b # foldr' :: (a -> b -> b) -> b -> NEMap k a -> b # foldl :: (b -> a -> b) -> b -> NEMap k a -> b # foldl' :: (b -> a -> b) -> b -> NEMap k a -> b # foldr1 :: (a -> a -> a) -> NEMap k a -> a # foldl1 :: (a -> a -> a) -> NEMap k a -> a # toList :: NEMap k a -> [a] # null :: NEMap k a -> Bool # length :: NEMap k a -> Int # elem :: Eq a => a -> NEMap k a -> Bool # maximum :: Ord a => NEMap k a -> a # minimum :: Ord a => NEMap k a -> a # sum :: Num a => NEMap k a -> a # product :: Num a => NEMap k a -> a #
Traversable (NEMap k) Source #	Traverses elements in order of ascending keys
Instance details Defined in Data.Map.NonEmpty.Internal Methods traverse :: Applicative f => (a -> f b) -> NEMap k a -> f (NEMap k b) # sequenceA :: Applicative f => NEMap k (f a) -> f (NEMap k a) # mapM :: Monad m => (a -> m b) -> NEMap k a -> m (NEMap k b) # sequence :: Monad m => NEMap k (m a) -> m (NEMap k a) #
Eq k => Eq1 (NEMap k) Source #
Instance details Defined in Data.Map.NonEmpty.Internal Methods liftEq :: (a -> b -> Bool) -> NEMap k a -> NEMap k b -> Bool #
Ord k => Ord1 (NEMap k) Source #
Instance details Defined in Data.Map.NonEmpty.Internal Methods liftCompare :: (a -> b -> Ordering) -> NEMap k a -> NEMap k b -> Ordering #
(Ord k, Read k) => Read1 (NEMap k) Source #
Instance details Defined in Data.Map.NonEmpty.Internal Methods liftReadsPrec :: (Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (NEMap k a) # liftReadList :: (Int -> ReadS a) -> ReadS [a] -> ReadS [NEMap k a] # liftReadPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec (NEMap k a) # liftReadListPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec [NEMap k a] #
Show k => Show1 (NEMap k) Source #
Instance details Defined in Data.Map.NonEmpty.Internal Methods liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> NEMap k a -> ShowS # liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [NEMap k a] -> ShowS #
Comonad (NEMap k) 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.Map.NonEmpty.Internal Methods extract :: NEMap k a -> a # duplicate :: NEMap k a -> NEMap k (NEMap k a) # extend :: (NEMap k a -> b) -> NEMap k a -> NEMap k b #
Traversable1 (NEMap k) Source #	Traverses elements in order of ascending keys
Instance details Defined in Data.Map.NonEmpty.Internal Methods traverse1 :: Apply f => (a -> f b) -> NEMap k a -> f (NEMap k b) # sequence1 :: Apply f => NEMap k (f b) -> f (NEMap k b) #
Foldable1 (NEMap k) Source #	Traverses elements in order of ascending keys
Instance details Defined in Data.Map.NonEmpty.Internal Methods fold1 :: Semigroup m => NEMap k m -> m # foldMap1 :: Semigroup m => (a -> m) -> NEMap k a -> m # toNonEmpty :: NEMap k a -> NonEmpty a #
(Eq k, Eq a) => Eq (NEMap k a) Source #
Instance details Defined in Data.Map.NonEmpty.Internal Methods (==) :: NEMap k a -> NEMap k a -> Bool # (/=) :: NEMap k a -> NEMap k a -> Bool #
(Data k, Data a, Ord k) => Data (NEMap k a) Source #
Instance details Defined in Data.Map.NonEmpty.Internal Methods gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> NEMap k a -> c (NEMap k a) # gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (NEMap k a) # toConstr :: NEMap k a -> Constr # dataTypeOf :: NEMap k a -> DataType # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (NEMap k a)) # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (NEMap k a)) # gmapT :: (forall b. Data b => b -> b) -> NEMap k a -> NEMap k a # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> NEMap k a -> r # gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> NEMap k a -> r # gmapQ :: (forall d. Data d => d -> u) -> NEMap k a -> [u] # gmapQi :: Int -> (forall d. Data d => d -> u) -> NEMap k a -> u # gmapM :: Monad m => (forall d. Data d => d -> m d) -> NEMap k a -> m (NEMap k a) # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> NEMap k a -> m (NEMap k a) # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> NEMap k a -> m (NEMap k a) #
(Ord k, Ord a) => Ord (NEMap k a) Source #
Instance details Defined in Data.Map.NonEmpty.Internal Methods compare :: NEMap k a -> NEMap k a -> Ordering # (<) :: NEMap k a -> NEMap k a -> Bool # (<=) :: NEMap k a -> NEMap k a -> Bool # (>) :: NEMap k a -> NEMap k a -> Bool # (>=) :: NEMap k a -> NEMap k a -> Bool # max :: NEMap k a -> NEMap k a -> NEMap k a # min :: NEMap k a -> NEMap k a -> NEMap k a #
(Ord k, Read k, Read e) => Read (NEMap k e) Source #
Instance details Defined in Data.Map.NonEmpty.Internal Methods readsPrec :: Int -> ReadS (NEMap k e) # readList :: ReadS [NEMap k e] # readPrec :: ReadPrec (NEMap k e) # readListPrec :: ReadPrec [NEMap k e] #
(Show k, Show a) => Show (NEMap k a) Source #
Instance details Defined in Data.Map.NonEmpty.Internal Methods showsPrec :: Int -> NEMap k a -> ShowS # show :: NEMap k a -> String # showList :: [NEMap k a] -> ShowS #
Ord k => Semigroup (NEMap k a) Source #	Left-biased union
Instance details Defined in Data.Map.NonEmpty.Internal Methods (<>) :: NEMap k a -> NEMap k a -> NEMap k a # sconcat :: NonEmpty (NEMap k a) -> NEMap k a # stimes :: Integral b => b -> NEMap k a -> NEMap k a #
(ToJSONKey k, ToJSON a) => ToJSON (NEMap k a) Source #
Instance details Defined in Data.Map.NonEmpty.Internal Methods toJSON :: NEMap k a -> Value # toEncoding :: NEMap k a -> Encoding # toJSONList :: [NEMap k a] -> Value # toEncodingList :: [NEMap k a] -> Encoding #
(FromJSONKey k, Ord k, FromJSON a) => FromJSON (NEMap k a) Source #
Instance details Defined in Data.Map.NonEmpty.Internal Methods parseJSON :: Value -> Parser (NEMap k a) # parseJSONList :: Value -> Parser [NEMap k a] #
(NFData k, NFData a) => NFData (NEMap k a) Source #
Instance details Defined in Data.Map.NonEmpty.Internal Methods rnf :: NEMap k a -> () #

Conversions between empty and non-empty maps

pattern IsNonEmpty :: NEMap k a -> Map k a Source #

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

For example, you can pattern match on a Map:

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

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

pattern IsEmpty :: Map k a Source #

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

Matching on IsEmpty means that the original Map 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 :: Map k a -> Maybe (NEMap k a) Source #

O(log n). Smart constructor for an NEMap from a Map. Returns Nothing if the Map was originally actually empty, and Just n with an NEMap, if the Map 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 Map being an NEMap.

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

toMap :: NEMap k a -> Map k a Source #

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

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.Map.fromList [(3,"a"), (5,"b")]

withNonEmpty Source #

Arguments

:: r	value to return if map is empty
-> (NEMap k a -> r)	function to apply if map is not empty
-> Map k a
-> r

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

nonEmptyMap == withNonEmpty Nothing Just

insertMap :: Ord k => k -> a -> Map k a -> NEMap k a Source #

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

insertMapWith :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> NEMap k a Source #

O(log n). Convert a Map into an NEMap 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.Map.fromList [(5,"a"), (3,"b")]) == fromList ((3,"b") :| [(4,"c"), (5,"a")])
insertMapWith (++) 5 "c" (Data.Map.fromList [(5,"a"), (3,"b")]) == fromList ((3,"b") :| [(5,"ca")])

insertMapWithKey :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> NEMap k a Source #

O(log n). Convert a Map into an NEMap 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.Map.fromList [(5,"a"), (3,"b")]) == fromList ((3, "b") :| [(5, "5:xxx|a")])
insertWithKey f 7 "xxx" (Data.Map.fromList [(5,"a"), (3,"b")]) == fromList ((3, "b") :| [(5, "a"), (7, "xxx")])
insertWithKey f 5 "xxx" Data.Map.empty                         == singleton 5 "xxx"

insertMapMin :: k -> a -> Map k a -> NEMap k a Source #

O(1) Convert a Map into an NEMap 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.Map.fromList [(5,"a"), (3,"b")]) == fromList ((2,"c") :| [(3,"b"), (5,"a")])
valid (insertMapMin 2 "c" (Data.Map.fromList [(5,"a"), (3,"b")])) == True
valid (insertMapMin 7 "c" (Data.Map.fromList [(5,"a"), (3,"b")])) == False
valid (insertMapMin 3 "c" (Data.Map.fromList [(5,"a"), (3,"b")])) == False

insertMapMax :: k -> a -> Map k a -> NEMap k a Source #

O(log n) Convert a Map into an NEMap 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.

While this has the same asymptotics as insertMap, it saves a constant factor for key comparison (so may be helpful if comparison is expensive) and also does not require an Ord instance for the key type.

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

unsafeFromMap :: Map k a -> NEMap k a Source #

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

Construction

singleton :: k -> a -> NEMap k a Source #

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

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

fromSet :: (k -> a) -> NESet k -> NEMap k 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 :: Ord k => NonEmpty (k, a) -> NEMap k 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 :: Ord k => (a -> a -> a) -> NonEmpty (k, a) -> NEMap k 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 :: Ord k => (k -> a -> a -> a) -> NonEmpty (k, a) -> NEMap k 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 :: Eq k => NonEmpty (k, a) -> NEMap k 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 :: Eq k => (a -> a -> a) -> NonEmpty (k, a) -> NEMap k 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 :: Eq k => (k -> a -> a -> a) -> NonEmpty (k, a) -> NEMap k 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 (k, a) -> NEMap k 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

From Descending Lists

fromDescList :: Eq k => NonEmpty (k, a) -> NEMap k a Source #

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

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

fromDescListWith :: Eq k => (a -> a -> a) -> NonEmpty (k, a) -> NEMap k a Source #

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

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

fromDescListWithKey :: Eq k => (k -> a -> a -> a) -> NonEmpty (k, a) -> NEMap k a Source #

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

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

fromDistinctDescList :: NonEmpty (k, a) -> NEMap k a Source #

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

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

Since: 0.5.8

Insertion

insert :: Ord k => k -> a -> NEMap k a -> NEMap k 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 Map.

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 :: Ord k => (a -> a -> a) -> k -> a -> NEMap k a -> NEMap k 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 insertMapWith for a version where the first argument is a Map.

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 :: Ord k => (k -> a -> a -> a) -> k -> a -> NEMap k a -> NEMap k 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 Map.

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 :: Ord k => (k -> a -> a -> a) -> k -> a -> NEMap k a -> (Maybe a, NEMap k 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 :: Ord k => k -> NEMap k a -> Map k a Source #

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

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

adjust :: Ord k => (a -> a) -> k -> NEMap k a -> NEMap k 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 :: Ord k => (k -> a -> a) -> k -> NEMap k a -> NEMap k 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 :: Ord k => (a -> Maybe a) -> k -> NEMap k a -> Map k 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 (Map), because we can't know ahead of time if the function returns Nothing and deletes the final item in the NEMap.

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

updateWithKey :: Ord k => (k -> a -> Maybe a) -> k -> NEMap k a -> Map k 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 (Map), because we can't know ahead of time if the function returns Nothing and deletes the final item in the NEMap.

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

updateLookupWithKey :: Ord k => (k -> a -> Maybe a) -> k -> NEMap k a -> (Maybe a, Map k a) Source #

O(log n). Lookup and update. See also updateWithKey. The function returns changed value, if it is updated. Returns the original key value if the map entry is deleted.

Returns a potentially empty map (Map) 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.Map.fromList ((3, "b") :| [(5, "5:new a")]))
updateLookupWithKey f 7 (fromList ((5,"a") :| [(3,"b")])) == (Nothing,  Data.Map.fromList ((3, "b") :| [(5, "a")]))
updateLookupWithKey f 3 (fromList ((5,"a") :| [(3,"b")])) == (Just "b", Data.Map.singleton 5 "a")

alter :: Ord k => (Maybe a -> Maybe a) -> k -> NEMap k a -> Map k 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 Map. In short : Data.Map.lookup k (alter f k m) = f (lookup k m).

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

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

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

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

alterF :: (Ord k, Functor f) => (Maybe a -> f (Maybe a)) -> k -> NEMap k a -> f (Map k 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 Map. In short: Data.Map.lookup k <$> alterF f k m = f (lookup k m).

Example:

interactiveAlter :: Int -> NEMap Int String -> IO (Map 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.Map.alterF for Map, 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 Map instead of an NEMap (because the function might delete the final item in the NEMap). 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 NEMap 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.Map.alterF for Map, 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' :: Ord k => (Maybe a -> a) -> k -> NEMap k a -> NEMap k a Source #

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

alterF' :: (Ord k, Functor f) => (Maybe a -> f a) -> k -> NEMap k a -> f (NEMap k a) Source #

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

Like Data.Map.alterF for Map, 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.Map. Data.Map.alterF will actually maintain the original key in the map when used with Identity; however, Data.Map.insertWith will replace the orginal key in the map. The rewrite rule for alterF' has chosen to be faithful to Data.Map.insertWith, and not Data.Map.alterF, for the sake of a cleaner implementation.

Query

Lookup

lookup :: Ord k => k -> NEMap k 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

(!?) :: Ord k => NEMap k a -> k -> 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'

(!) :: Ord k => NEMap k a -> k -> 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 :: Ord k => a -> k -> NEMap k 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 :: Ord k => k -> NEMap k 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 :: Ord k => k -> NEMap k 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 :: Ord k => k -> NEMap k a -> Maybe (k, 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 :: Ord k => k -> NEMap k a -> Maybe (k, 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 :: Ord k => k -> NEMap k a -> Maybe (k, 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 :: Ord k => k -> NEMap k a -> Maybe (k, 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

absurdNEMap :: NEMap Void a -> b Source #

Special property of non-empty maps: The type of non-empty maps over uninhabited keys is itself uninhabited.

This property also exists for values inside a non-empty container (like for NESet, NESeq, and NEIntMap); this can be witnessed using the function absurd . fold1.

Since: 0.3.1.0

Size

size :: NEMap k 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 :: Ord k => NEMap k a -> NEMap k a -> NEMap k 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 :: Ord k => (a -> a -> a) -> NEMap k a -> NEMap k a -> NEMap k 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 :: Ord k => (k -> a -> a -> a) -> NEMap k a -> NEMap k a -> NEMap k 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, Ord k) => f (NEMap k a) -> NEMap k 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, Ord k) => (a -> a -> a) -> f (NEMap k a) -> NEMap k 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 :: Ord k => NEMap k a -> NEMap k b -> Map k 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 (Map), in case the first map is a subset of the second map.

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

(\\) :: Ord k => NEMap k a -> NEMap k b -> Map k a Source #

Same as difference.

differenceWith :: Ord k => (a -> b -> Maybe a) -> NEMap k a -> NEMap k b -> Map k 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 (Map), 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.Map.singleton 3 "b:B"

differenceWithKey :: Ord k => (k -> a -> b -> Maybe a) -> NEMap k a -> NEMap k b -> Map k 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 (Map), 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.Map.singleton 3 "3:b|B"

Intersection

intersection :: Ord k => NEMap k a -> NEMap k b -> Map k 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 (Map), in case the two maps share no keys in common.

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

intersectionWith :: Ord k => (a -> b -> c) -> NEMap k a -> NEMap k b -> Map k c Source #

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

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

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

intersectionWithKey :: Ord k => (k -> a -> b -> c) -> NEMap k a -> NEMap k b -> Map k c Source #

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

Returns a potentially empty map (Map), 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.Map.singleton 5 "5:a|A"

Traversal

Map

map :: (a -> b) -> NEMap k a -> NEMap k b Source #

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

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

mapWithKey :: (k -> a -> b) -> NEMap k a -> NEMap k b Source #

O(n). Map 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 => (k -> a -> t b) -> NEMap k a -> t (NEMap k 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.

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

traverseWithKey :: Applicative t => (k -> a -> t b) -> NEMap k a -> t (NEMap k 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.

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

traverseMaybeWithKey1 :: Apply t => (k -> a -> t (Maybe b)) -> NEMap k a -> t (Map k b) Source #

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

Returns a potentially empty map (Map), our function might return Nothing on every item in the NEMap.

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

traverseMaybeWithKey :: Applicative t => (k -> a -> t (Maybe b)) -> NEMap k a -> t (Map k b) Source #

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

Returns a potentially empty map (Map), our function might return Nothing on every item in the NEMap.

Use traverseMaybeWithKey1 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.

mapAccum :: (a -> b -> (a, c)) -> a -> NEMap k b -> (a, NEMap k 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 -> k -> b -> (a, c)) -> a -> NEMap k b -> (a, NEMap k 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 -> k -> b -> (a, c)) -> a -> NEMap k b -> (a, NEMap k c) Source #

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

mapKeys :: Ord k2 => (k1 -> k2) -> NEMap k1 a -> NEMap k2 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 :: Ord k2 => (a -> a -> a) -> (k1 -> k2) -> NEMap k1 a -> NEMap k2 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 :: (k1 -> k2) -> NEMap k1 a -> NEMap k2 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 -> NEMap k 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 -> NEMap k 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) -> NEMap k 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 Map, this function is total if the input function is total.

foldl1 :: (a -> a -> a) -> NEMap k 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 Map, this function is total if the input function is total.

foldrWithKey :: (k -> a -> b -> b) -> b -> NEMap k 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 -> k -> b -> a) -> a -> NEMap k 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 => (k -> a -> m) -> NEMap k a -> m Source #

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

foldMapWithKey f = fold1 . mapWithKey f

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

Strict folds

foldr' :: (a -> b -> b) -> b -> NEMap k 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) -> NEMap k 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 -> NEMap k 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) -> NEMap k 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' :: (k -> a -> b -> b) -> b -> NEMap k 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 -> k -> b -> a) -> a -> NEMap k 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 :: NEMap k 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 :: NEMap k a -> NonEmpty k Source #

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

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

assocs :: NEMap k a -> NonEmpty (k, 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 :: NEMap k a -> NESet k 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 :: NEMap k a -> NonEmpty (k, 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 :: NEMap k a -> NonEmpty (k, 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 :: NEMap k a -> NonEmpty (k, 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) -> NEMap k a -> Map k a Source #

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

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

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

filterWithKey :: (k -> a -> Bool) -> NEMap k a -> Map k a Source #

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

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

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

restrictKeys :: Ord k => NEMap k a -> Set k -> Map k a Source #

O(m*log(n/m + 1)), m <= n. Restrict an NEMap 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 :: Ord k => NEMap k a -> Set k -> Map k a Source #

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

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

partition :: (a -> Bool) -> NEMap k a -> These (NEMap k a) (NEMap k 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).

Submap

isSubmapOf :: (Ord k, Eq a) => NEMap k a -> NEMap k a -> Bool Source #

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

isSubmapOfBy :: Ord k => (a -> b -> Bool) -> NEMap k a -> NEMap k 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 :: (Ord k, Eq a) => NEMap k a -> NEMap k 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 :: Ord k => (a -> b -> Bool) -> NEMap k a -> NEMap k 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)]))

Indexed

lookupIndex :: Ord k => k -> NEMap k a -> Maybe Int Source #

O(log n). Lookup the index of a key, which is its zero-based index in the sequence sorted by keys. The index is a number from 0 up to, but not including, the size of the map.

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

findIndex :: Ord k => k -> NEMap k a -> Int Source #

O(log n). Return the index of a key, which is its zero-based index in the sequence sorted by keys. The index is a number from 0 up to, but not including, the size of the map. Calls error when the key is not a member of the map.

findIndex 2 (fromList ((5,"a") :| [(3,"b")]))    Error: element is not in the map
findIndex 3 (fromList ((5,"a") :| [(3,"b")])) == 0
findIndex 5 (fromList ((5,"a") :| [(3,"b")])) == 1
findIndex 6 (fromList ((5,"a") :| [(3,"b")]))    Error: element is not in the map

elemAt :: Int -> NEMap k a -> (k, a) Source #

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

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

updateAt :: (k -> a -> Maybe a) -> Int -> NEMap k a -> Map k a Source #

O(log n). Update the element at index, i.e. by its zero-based index in the sequence sorted by keys. If the index is out of range (less than zero, greater or equal to size of the map), error is called.

Returns a possibly empty map (Map), because the function might end up deleting the last key in the map. See adjustAt for a version that disallows deletion, guaranteeing that the result is also a non-empty Map.

updateAt (\ _ _ -> Just "x") 0    (fromList ((5,"a") :| [(3,"b")])) == Data.Map.fromList [(3, "x"), (5, "a")]
updateAt (\ _ _ -> Just "x") 1    (fromList ((5,"a") :| [(3,"b")])) == Data.Map.fromList [(3, "b"), (5, "x")]
updateAt (\ _ _ -> Just "x") 2    (fromList ((5,"a") :| [(3,"b")]))    Error: index out of range
updateAt (\ _ _ -> Just "x") (-1) (fromList ((5,"a") :| [(3,"b")]))    Error: index out of range
updateAt (\_ _  -> Nothing)  0    (fromList ((5,"a") :| [(3,"b")])) == Data.Map.singleton 5 "a"
updateAt (\_ _  -> Nothing)  1    (fromList ((5,"a") :| [(3,"b")])) == Data.Map.singleton 3 "b"
updateAt (\_ _  -> Nothing)  2    (fromList ((5,"a") :| [(3,"b")]))    Error: index out of range
updateAt (\_ _  -> Nothing)  (-1) (fromList ((5,"a") :| [(3,"b")]))    Error: index out of range

adjustAt :: (k -> a -> a) -> Int -> NEMap k a -> NEMap k a Source #

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

deleteAt :: Int -> NEMap k a -> Map k a Source #

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

Returns a potentially empty map (Map) because of the possibility of deleting the last item in a map.

deleteAt 0  (fromList ((5,"a") :| [(3,"b")])) == Data.Map.singleton 5 "a"
deleteAt 1  (fromList ((5,"a") :| [(3,"b")])) == Data.Map.singleton 3 "b"
deleteAt 2 (fromList ((5,"a") :| [(3,"b")]))     Error: index out of range
deleteAt (-1) (fromList ((5,"a") :| [(3,"b")]))  Error: index out of range

take :: Int -> NEMap k a -> Map k a Source #

Take a given number of entries in key order, beginning with the smallest keys.

Returns a possibly empty map (Map), which can only happen if we call take 0.

take n = Data.Map.fromDistinctAscList . Data.List.NonEmpty.take n . toList

drop :: Int -> NEMap k a -> Map k a Source #

Drop a given number of entries in key order, beginning with the smallest keys.

Returns a possibly empty map (Map), in case we drop all of the elements (which can happen if we drop a number greater than or equal to the number of items in the map)

drop n = Data.Map.fromDistinctAscList . Data.List.NonEmpty.drop' n . toList

splitAt :: Int -> NEMap k a -> These (NEMap k a) (NEMap k a) Source #

O(log n). Split a map at a particular index i.

This n1 means that there are less than i items in the map, and n1 is the original map.
That n2 means i was 0; we dropped 0 items, so n2 is the original map.
These n1 n2 gives n1 (taking i items from the original map) and n2 (dropping i items from the original map))

Min/Max

findMin :: NEMap k a -> (k, 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.Map.lookupMin and Data.Map.findMin, as well.

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

findMax :: NEMap k a -> (k, 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 :: NEMap k a -> Map k a Source #

O(1). Delete the minimal key. Returns a potentially empty map (Map), 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.Map.fromList [(5,"a"), (7,"c")]
deleteMin (singleton 5 "a") == Data.Map.empty

deleteMax :: NEMap k a -> Map k a Source #

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

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

deleteFindMin :: NEMap k a -> ((k, a), Map k a) Source #

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

Note that unlike Data.Map.deleteFindMin for Map, this cannot ever fail, and so is a total function. However, the result Map 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.Map.fromList [(5,"a"), (10,"c")])

deleteFindMax :: NEMap k a -> ((k, a), Map k a) Source #

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

Note that unlike Data.Map.deleteFindMax for Map, this cannot ever fail, and so is a total function. However, the result Map 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.Map.fromList [(3,"b"), (5,"a")])

updateMin :: (a -> Maybe a) -> NEMap k a -> Map k a Source #

O(1) if delete, O(log n) otherwise. Update the value at the minimal key. Returns a potentially empty map (Map), 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.Map.fromList [(3, "Xb"), (5, "a")]
updateMin (\ _ -> Nothing)         (fromList ((5,"a") :| [(3,"b")])) == Data.Map.singleton 5 "a"

updateMax :: (a -> Maybe a) -> NEMap k a -> Map k a Source #

O(log n). Update the value at the maximal key. Returns a potentially empty map (Map), 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.Map.fromList [(3, "b"), (5, "Xa")]
updateMax (\ _ -> Nothing)         (fromList ((5,"a") :| [(3,"b")])) == Data.Map.singleton 3 "b"

adjustMin :: (a -> a) -> NEMap k a -> NEMap k 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) -> NEMap k a -> NEMap k a Source #

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

updateMinWithKey :: (k -> a -> Maybe a) -> NEMap k a -> Map k a Source #

O(1) if delete, O(log n) otherwise. Update the value at the minimal key. Returns a potentially empty map (Map), 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.Map.fromList [(3,"3:b"), (5,"a")]
updateMinWithKey (\ _ _ -> Nothing)                     (fromList ((5,"a") :| [(3,"b")])) == Data.Map.singleton 5 "a"

updateMaxWithKey :: (k -> a -> Maybe a) -> NEMap k a -> Map k a Source #

O(log n). Update the value at the maximal key. Returns a potentially empty map (Map), 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.Map.fromList [(3,"3:b"), (5,"a")]
updateMinWithKey (\ _ _ -> Nothing)                     (fromList ((5,"a") :| [(3,"b")])) == Data.Map.singleton 5 "a"

adjustMinWithKey :: (k -> a -> a) -> NEMap k a -> NEMap k 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 :: (k -> a -> a) -> NEMap k a -> NEMap k a Source #

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

minView :: NEMap k a -> (a, Map k 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.Map.minView for Map.

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

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

maxView :: NEMap k a -> (a, Map k 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.Map.maxView from Map, this cannot ever fail, so doesn't need to return in a Maybe. However, the result Map is potentially empty, since the original map might have contained just a single item.

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

Debugging

valid :: Ord k => NEMap k a -> Bool Source #

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