Copyright | (c) Justin Le 2018 |
---|---|
License | BSD3 |
Maintainer | justin@jle.im |
Stability | experimental |
Portability | non-portable |
Safe Haskell | None |
Language | Haskell2010 |
Non-Empty Finite Maps (lazy interface)
The
type represents a non-empty finite map (sometimes
called a dictionary) from keys of type NEMap
k vk
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
A non-empty (by construction) map from keys k
to values a
. At
least one key-value pair exists in an
at all times.NEMap
k v
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
into aMap
k a
, returningMaybe
(NEMap
k a)Nothing
if the originalMap
was empty. - You can use the
insertMap
family of functions to insert a value into aMap
to create a guaranteedNEMap
. - You can use the
IsNonEmpty
andIsEmpty
patterns to "pattern match" on aMap
to reveal it as either containing aNEMap
or an empty map. withNonEmpty
offers a continuation-based interface for deconstructing aMap
and treating it as if it were anNEMap
.
You can convert an NEMap
into a Map
with toMap
or
IsNonEmpty
, essentially "obscuring" the non-empty
property from the type.
Instances
Eq2 NEMap Source # | |
Ord2 NEMap Source # | |
Defined in Data.Map.NonEmpty.Internal | |
Show2 NEMap Source # | |
Functor (NEMap k) Source # | |
Foldable (NEMap k) Source # | Traverses elements in order of ascending keys |
Defined in Data.Map.NonEmpty.Internal 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 # elem :: Eq a => a -> NEMap k a -> Bool # maximum :: Ord a => NEMap k a -> a # minimum :: Ord a => NEMap k a -> a # | |
Traversable (NEMap k) Source # | Traverses elements in order of ascending keys |
Eq k => Eq1 (NEMap k) Source # | |
Ord k => Ord1 (NEMap k) Source # | |
Defined in Data.Map.NonEmpty.Internal | |
(Ord k, Read k) => Read1 (NEMap k) Source # | |
Defined in Data.Map.NonEmpty.Internal | |
Show k => Show1 (NEMap k) Source # | |
Comonad (NEMap k) Source # |
Since: 0.1.1.0 |
Traversable1 (NEMap k) Source # | Traverses elements in order of ascending keys |
Foldable1 (NEMap k) Source # | Traverses elements in order of ascending keys |
(Eq k, Eq a) => Eq (NEMap k a) Source # | |
(Data k, Data a, Ord k) => Data (NEMap k a) Source # | |
Defined in Data.Map.NonEmpty.Internal 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 # | |
Defined in Data.Map.NonEmpty.Internal | |
(Ord k, Read k, Read e) => Read (NEMap k e) Source # | |
(Show k, Show a) => Show (NEMap k a) Source # | |
Ord k => Semigroup (NEMap k a) Source # | Left-biased union |
(ToJSONKey k, ToJSON a) => ToJSON (NEMap k a) Source # | |
Defined in Data.Map.NonEmpty.Internal | |
(FromJSONKey k, Ord k, FromJSON a) => FromJSON (NEMap k a) Source # | |
(NFData k, NFData a) => NFData (NEMap k a) Source # | |
Defined in Data.Map.NonEmpty.Internal |
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
(where IsNonEmpty
nn
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, andn
is theNEMap
myFuncIsEmpty
= -- here, the user provided an empty map.
Matching on
means that the original IsNonEmpty
nMap
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
(where IsNonEmpty
nn
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
with an Just
nNEMap
, if the Map
was not empty.
nonEmptyMap
and
form an
isomorphism: they are perfect structure-preserving inverses of
eachother.maybe
empty
toMap
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
form an isomorphism: they
are perfect structure-preserving inverses of eachother.maybe
empty
toMap
toMap (fromList ((3,"a") :| [(5,"b")])) == Data.Map.fromList [(3,"a"), (5,"b")]
:: 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
.
will take a withNonEmpty
def fMap
. 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.
will insert the pair (key, value) into
insertWith
f key value mpmp
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.
will insert the pair (key,
value) into insertWithKey
f key value mpmp
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 (
) is a pair where the first
element is equal to (insertLookupWithKey
f k x map
) and the second element equal to
(lookup
k map
).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 (
) updates the value update
f k mapx
at k
(if it is in the map). If (f x
) is Nothing
, the element is
deleted. If it is (
), the key Just
yk
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 (
) updates the
value updateWithKey
f k mapx
at k
(if it is in the map). If (f k x
) is Nothing
,
the element is deleted. If it is (
), the key Just
yk
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 (
) alters the value alter
f k mapx
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 (
) alters the value alterF
f k mapx
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 (
,
or Just
value)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 (
returns
the value at key findWithDefault
def k map)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 #
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 (
) takes the left-biased union of union
t1 t2t1
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"
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 (
), the element is updated with a new value Just
yy
.
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 (
), the element is updated with a new value Just
yy
.
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).
That is, behaves exactly like a regular traverseWithKey
f m == fromList
$ traverse
((k, v) -> (,) k $ f k v) (toList
m)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).
is the map obtained by applying mapKeys
f sf
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).
is the map obtained by applying mapKeysWith
c f sf
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).
, but works only when mapKeysMonotonic
f s == mapKeys
f sf
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
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
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:
means that the predicate was true for all items.This
n1
means that the predicate was false for all items.That
n2
givesThese
n1 n2n1
(all of the items that were true for the predicate) andn2
(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 :: (k -> 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:
means that the predicate was true for all items, returning the original map.This
n1
means that the predicate was false for all items, returning the original map.That
n2
givesThese
n1 n2n1
(all of the items that were true for the predicate) andn2
(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")]))
takeWhileAntitone :: (k -> Bool) -> NEMap k a -> Map k a Source #
O(log n). Take while a predicate on the keys holds.
The user is responsible for ensuring that for all keys j
and k
in the map,
j < k ==> p j >= p k
. See note at spanAntitone
.
Returns a potentially empty map (Map
), because the predicate might
fail on the first input.
takeWhileAntitone p = Data.Map.fromDistinctAscList . Data.List.takeWhile (p . fst) . Data.Foldable.toList
takeWhileAntitone p = filterWithKey
(k _ -> p k)
dropWhileAntitone :: (k -> Bool) -> NEMap k a -> Map k a Source #
O(log n). Drop while a predicate on the keys holds.
The user is responsible for ensuring that for all keys j
and k
in the map,
j < k ==> p j >= p k
. See note at spanAntitone
.
dropWhileAntitone p = Data.Map.fromDistinctAscList . Data.List.dropWhile (p . fst) . Data.Foldable.toList
dropWhileAntitone p = filterWithKey
(k -> not (p k))
spanAntitone :: (k -> Bool) -> NEMap k a -> These (NEMap k a) (NEMap k a) Source #
O(log n). Divide a map at the point where a predicate on the keys stops holding.
The user is responsible for ensuring that for all keys j
and k
in the map,
j < k ==> p j >= p k
.
Returns a These
with potentially two non-empty maps:
means that the predicate never failed for any item, returning the original map.This
n1
means that the predicate failed for the first item, returning the original map.That
n2
givesThese
n1 n2n1
(the map up to the point where the predicate on the keys stops holding) andn2
(the map starting from the point where the predicate stops holding)
spanAntitone p xs = partitionWithKey (k _ -> p k) xs
Note: if p
is not actually antitone, then spanAntitone
will split the map
at some unspecified point where the predicate switches from holding to not
holding (where the predicate is seen to hold before the first key and to fail
after the last key).
mapMaybeWithKey :: (k -> a -> Maybe b) -> NEMap k a -> Map k b Source #
O(n). Map keys/values and collect the Just
results.
Returns a potentially empty map (Map
), because the function could
potentially return Nothing
on all items in the NEMap
.
let f k _ = if k < 5 then Just ("key : " ++ (show k)) else Nothing mapMaybeWithKey f (fromList ((5,"a") :| [(3,"b")])) == Data.Map.singleton 3 "key : 3"
mapEither :: (a -> Either b c) -> NEMap k a -> These (NEMap k b) (NEMap k c) Source #
O(n). Map values and separate the Left
and Right
results.
Returns a These
with potentially two non-empty maps:
means that the results were allThis
n1Left
.
means that the results were allThat
n2Right
.
givesThese
n1 n2n1
(the map where the results wereLeft
) andn2
(the map where the results wereRight
)
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 :: (k -> a -> Either b c) -> NEMap k a -> These (NEMap k b) (NEMap k c) Source #
O(n). Map keys/values and separate the Left
and Right
results.
Returns a These
with potentially two non-empty maps:
means that the results were allThis
n1Left
.
means that the results were allThat
n2Right
.
givesThese
n1 n2n1
(the map where the results wereLeft
) andn2
(the map where the results wereRight
)
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 :: Ord k => k -> NEMap k a -> Maybe (These (NEMap k a) (NEMap k a)) Source #
O(log n). The expression (
) is potentially a split
k mapThese
containing up to two NEMap
s based on splitting the map into maps
containing items before and after the given key k
. It will never
return a map that contains k
itself.
Nothing
means thatk
was the only key in the the original map, and so there are no items before or after it.
meansJust
(This
n1)k
was larger than or equal to all items in the map, andn1
is the entire original map (minusk
, if it was present)
meansJust
(That
n2)k
was smaller than or equal to all items in the map, andn2
is the entire original map (minusk
, if it was present)
givesJust
(These
n1 n2)n1
(the map of all keys from the original map less thank
) andn2
(the map of all keys from the original map greater thank
)
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 :: Ord k => k -> NEMap k a -> These a (These (NEMap k a) (NEMap k a)) Source #
O(log n). The expression (
) splits a map just
like splitLookup
k mapsplit
but also returns
, as the first field in
the lookup
k mapThese
:
splitLookup 2 (fromList ((5,"a") :| [(3,"b")])) == That (That (fromList ((3,"b") :| [(5,"a")]))) splitLookup 3 (fromList ((5,"a") :| [(3,"b")])) == These "b" (That (singleton 5 "a")) splitLookup 4 (fromList ((5,"a") :| [(3,"b")])) == That (These (singleton 3 "b") (singleton 5 "a")) splitLookup 5 (fromList ((5,"a") :| [(3,"b")])) == These "a" (This (singleton 3 "b")) splitLookup 6 (fromList ((5,"a") :| [(3,"b")])) == That (This (fromList ((3,"b") :| [(5,"a")]))) splitLookup 5 (singleton 5 "a") == This "a"
splitRoot :: NEMap k a -> NonEmpty (NEMap k a) Source #
O(1). Decompose a map into pieces based on the structure of the underlying tree. This function is useful for consuming a map in parallel.
No guarantee is made as to the sizes of the pieces; an internal, but deterministic process determines this. However, it is guaranteed that the pieces returned will be in ascending order (all elements in the first submap less than all elements in the second, and so on).
Note that the current implementation does not return more than four submaps, but you should not depend on this behaviour because it can change in the future without notice.
Submap
isSubmapOf :: (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 (
) returns isSubmapOfBy
f t1 t2True
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 (
) returns
isProperSubmapOfBy
f m1 m2True
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
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
.
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")