Data.Map.NonEmpty

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.

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

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

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). 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(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(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). 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 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(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). 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 (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). 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(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). 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). 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 alter that disallows deletion. Allows us to guarantee that the result is also a non-empty Map.

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). 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). 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 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). 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 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). 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). 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). Return all elements of the map in the ascending order of their keys.

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

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

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

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(n). The non-empty set of all keys of the map.

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

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

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(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(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). 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). 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(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). Variant of updateAt that disallows deletion. Allows us to guarantee that the result is also a non-empty Map.

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

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

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

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

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

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

Drop 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). 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(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 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). 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(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(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 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) 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(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(1). A version of updateMin that disallows deletion, allowing us to guarantee that the result is also non-empty.

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

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). 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). 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). A version of updateMaxWithKey that disallows deletion, allowing us to guarantee that the result is also non-empty.

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). 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(n). Test if the internal map structure is valid.