Agda.Utils.Map1

A more general type would be Null m => Map k a -> (Map1 k a -> m) -> m but this type is problematic as we do not have a general instance Applicative m => Null (m ()).

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'

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

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

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

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 Data.Map.empty.

See IsNonEmpty for more information.

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

Same as difference.

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.

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

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

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

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

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

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.

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

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

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

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 Control.Lens.At.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.

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 Control.Lens.At.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.

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

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

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

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

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

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

O(log n). Delete a key and its value from the non-empty map, returning Nothing if the result would be empty.

This is more efficient than nonEmptyMap . delete k because it avoids converting the known-minimum representation back through Map when the deleted key is not the minimum.

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 Data.Map.deleteMin.

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

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"

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"

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"

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

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

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

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

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"

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

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

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

O(1). The minimal key of the map. Note that this is total, making Data.Map.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")

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'

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.

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

For example,

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

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.

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.

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

For example,

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

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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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"

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

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

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

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"

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

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"

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"

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"

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

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

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

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)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Returns a These with potentially two non-empty maps:

• This n1 means that the results were all Left.

• That n2 means that the results were all Right.

• These n1 n2 gives n1 (the map where the results were Left) and n2 (the map where the results were Right)

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

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

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

Returns a These with potentially two non-empty maps:

• This n1 means that the results were all Left.

• That n2 means that the results were all Right.

• These n1 n2 gives n1 (the map where the results were Left) and n2 (the map where the results were Right)

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

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

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"

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

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"

O(n). Map 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 x = if x == "a" then Just "new a" else Nothing
mapMaybe f (fromList ((5,"a") :| [(3,"b")])) == Data.Map.singleton 5 "new a"

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"

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

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

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

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

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

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

Returns a These with potentially two non-empty maps:

• This n1 means that the predicate was true for all items.

• That n2 means that the predicate was false for all items.

• These n1 n2 gives n1 (all of the items that were true for the predicate) and n2 (all of the items that were false for the predicate).

See also split.

partition (> "a") (fromList ((5,"a") :| [(3,"b")])) == These (singleton 3 "b") (singleton 5 "a")
partition (< "x") (fromList ((5,"a") :| [(3,"b")])) == This  (fromList ((3, "b") :| [(5, "a")]))
partition (> "x") (fromList ((5,"a") :| [(3,"b")])) == That  (fromList ((3, "b") :| [(5, "a")]))

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

Returns a These with potentially two non-empty maps:

• This n1 means that the predicate was true for all items, returning the original map.

• That n2 means that the predicate was false for all items, returning the original map.

• These n1 n2 gives n1 (all of the items that were true for the predicate) and n2 (all of the items that were false for the predicate).

See also split.

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

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 `Set.member` s) m
m `restrictKeys` s = m `intersection` fromSet (const ()) s

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:

• This n1 means that the predicate never failed for any item, returning the original map.

• That n2 means that the predicate failed for the first item, returning the original map.

• These n1 n2 gives n1 (the map up to the point where the predicate on the keys stops holding) and n2 (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).

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

• Nothing means that k was the only key in the the original map, and so there are no items before or after it.

• Just (This n1) means k was larger than or equal to all items in the map, and n1 is the entire original map (minus k, if it was present)

• Just (That n2) means k was smaller than or equal to all items in the map, and n2 is the entire original map (minus k, if it was present)

• Just (These n1 n2) gives n1 (the map of all keys from the original map less than k) and n2 (the map of all keys from the original map greater than k)

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

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

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

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

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.

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

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)

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

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

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.

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.

O(m*log(n/m + 1)), m <= n. Left-biased union of a possibly-empty Map and a non-empty map.

O(m*log(n/m + 1)), m <= n. Left-biased union of a non-empty map and a possibly-empty Map.

O(m*log(n/m + 1)), m <= n. Union of a possibly-empty Map and a non-empty map with a combining function, given the matching key.

O(m*log(n/m + 1)), m <= n. Union of a non-empty map and a possibly-empty Map with a combining function, given the matching key.

O(m*log(n/m + 1)), m <= n. Union of a possibly-empty Map and a non-empty map with a combining function.

O(m*log(n/m + 1)), m <= n. Union of a non-empty map and a possibly-empty Map with a combining function.

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

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

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

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.

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"

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

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

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"

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"

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"

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"

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"

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

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

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

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

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.

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

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.

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.

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

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.

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.

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

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

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

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

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 Data.Map.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")]))

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

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

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

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

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

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 Data.Map.NonEmpty.IsNotEmpty pattern.

nonEmptyMap and maybe Data.Map.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")]

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)

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.

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

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

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

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

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 Data.Map.empty. There are also a few ways to construct an NEMap from a Map:

1. The nonEmptyMap smart constructor will convert a Map k a into a Maybe (NEMap k a), returning Nothing if the original Map was empty.

2. You can use the insertMap family of functions to insert a value into a Map to create a guaranteed NEMap.

3. 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.

4. 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.